Re: Regular-Expressions Problem/Bug

On Wed, 19 Jul 2006, Reto Schuettel wrote:

> After some experiments I could even simplify the problem:
> LENGTH = 20000
> text = "x" * LENGTH + "ABC" + "y" * 10
> re = /(.*)ABC[y]#/
> -> takes forever...

Here, forever takes 3657 ms.

With LENGTH=40000, it's 14551 ms. The ratio of those suggests that it's a 
O(LENGTH^2) situation. Trying with more cases of LENGTH confirms this, for 
sufficiently large LENGTHs.

This shouldn't happen, because (.*) should just match all of the string 
and then retry with smaller strings until the rest of the regexp matches 
on the rest of the string.

O(LENGTH^2) suggests that there might be O(LENGTH) steps of duration 
O(LENGTH) each, which I could speculate to be string copying operations of 
the $1 prematurely. What perplexes me is that (?:.*) is just as slow as 
(.*) ... After that, I don't know what to say.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - t駘:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montr饌l QC Canada