develooper Front page | perl.perl5.porters | Postings from May 2004

Re: slow regex?

Thread Previous | Thread Next
From:
Dave Mitchell
Date:
May 30, 2004 14:45
Subject:
Re: slow regex?
Message ID:
20040530215141.GC1901@iabyn.com
On Tue, May 25, 2004 at 11:59:18AM +0100, hv@crypt.org wrote:
> Dave Mitchell <davem@iabyn.com> wrote:
> :This regex takes 2.5 secs on my machine to fail to match (5.8.4 and
> :bleed):
> :
> :    $_ = <<'EOF';
> :    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
> :    BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
> :    EOF
> :
> :    print "matched\n" if /.*?A.*?B+\s+X/s;
> :
> :While I can see that it may need to backtrack 70x70 times, this still
> :seems quite slow. (This is a stripped-down version of a regex I wrote
> :for production code that basically  ground to a halt).
> :
> :Is this is bug, or do I have unrealistic expectations?
> 
> Testing C<< join '', 'A' x $n, ' ', 'B' x $n, ' ' >> against that
> regexp, and grepping the resulting -Dr output for 'Setting an EVAL scope',
> the number of scopes set as a function of $len is:
>   (n^4 + 4n^3 + 5n^2 + 10n) / 4
> .. which gives 6,351,800 for n=70.

Ah yes, I hadn't really thought it through - I can see now why its O(n^4)
not O(n^2).

Thanks.

PS folks - I wouldn't *really* start a regex with .*? - this was only a
by-product of stripping down the real regex. Honest!

-- 
To collect all the latest movies, simply place an unprotected ftp server
on the Internet, and wait for the disk to fill....

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About