From: Dave Thomas <Dave@...>
Date: 2001-01-11T13:48:57+09:00
Subject: [ruby-talk:9104] Re: Regexp for matching Ruby reg exps?

"Ben Tilly" <ben_tilly@hotmail.com> 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.

> 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.

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 ;-)


Dave