On Mon, 28 Jan 2013 18:22:42 +0100, Joerg Sonnenberger
<jo...@britannica.bec.de> wrote:
On Mon, Jan 28, 2013 at 06:09:57PM +0100, j. van den hoff wrote:
On Mon, 28 Jan 2013 17:34:44 +0100, Joerg Sonnenberger
<jo...@britannica.bec.de> wrote:
>On Mon, Jan 28, 2013 at 08:50:56AM -0500, Richard Hipp wrote:
>>The regular expression matching in
>>www.fossil-scm.org/fossil/artifact/c8fb75a1615f is also
>>lightweight and it
>>supports | and it is usually as fast or faster than grep in my tests
>>(though there are some cases for which grep is faster). The regexp.c
in
>>fossil uses a NFA which gives worst case performance of O(NM) where N
is
>>the size of the input text to be matched and M is the size of
>>the regular
>>expression. Perl regular expressions and lua-regexp.c take
exponential
>>time for some (admittedly obscure) regular expressions. On the
>>other hand,
>>Perl regular expressions are more complete, and both Lua and
>>Perl allow you
>>to do substitutions, which the regexp.c file in Fossil does not.
>
>The Lua implementation starts to perform very badly as soon as you have
>wild cards at the beginning of the pattern. Those aren't even
obscure...
just a guess: you did not "anchor" the pattern, i.e. you used
something like ".*foo" instead of "^.*foo"?
Anchoring doesn't help if you want to explicitly match wild card chars
at or near the beginning. With a NFA or DFA based implementation, it
I'm too slow: could you give an example where anchoring would come in the
way of what you really want to match?
j.
will add some processing time, but the linear performance is still
guaranteed.
Joerg
_______________________________________________
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
--
Using Opera's revolutionary email client: http://www.opera.com/mail/
_______________________________________________
fossil-users mailing list
fossil-users@lists.fossil-scm.org
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
