[ruby-talk:9130] Re: Regexp for matching Ruby reg exps?

Dave Thomas <[e-mail]> wrote:
>
>"Ben Tilly" <[e-mail]> writes:
>
> > Performance may be fine for your application, but that is
> > basically the trick I saw Abigail use.  It is O(n*m) where
> > n is the length of the string, and m the number of nested
> > structures.  In a deeply nested string m is O(n), so in
> > general that scales like O(n*n).
>
>I'd be interested in a practical example where the nesting depth is
>O(n). In practical applications (processing latex and so on) I'd guess
>that the depth rarely exceeds 4 or 5.

(Reads more carefully.)

Missed the /g.  D'oh.  You are right, in practice that will
depend on nesting depth, not the number of nested structures.
Unless you are dealing with Lisp*, that should perform just
fine. :-)

(Perhaps I really do need more sleep.)

> > Also there is a bug.  You assume that the string !!O:50:
> > does not already appear in the text.  If it does you are
> > likely to be confused.  Using a real data structure you
> > will not have that problem.  Of course it won't happen by
> > accident, and for your own text that is something you can
> > know to avoid.  (Whatever gets the job done.)   But I
> > would be dubious of that kind of code if security was an
> > issue.
>
>Actually, the line of code above this one checks that the string
>doesn't contain two !'s and aborts if it does.

Ah. :-)

>I'm not disagreeing that this is something of a hack. But from my
>experience doing this in Perl, processing Latex and XML, this actually
>runs faster than writing an explicit parse in Perl itself.
>
>I'm sure you milage varies ;-)

Not really.  As soon as you take work out of the RE engine
and move to the interpreted language you get an immediate
and large performance hit.  Then scale better.

Personally when I face things like this I try to find ways
to solve the problem in a single scan of the string without
having to read it into a data structure and process that
structure.

Cheers,
Ben

* Joke.  (In case it wasn't obvious.)
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com