On Fri, 18 Jul 2003 15:49:04 -0400, Vivek Khera <[EMAIL PROTECTED]> writes:
> SAC> 2 '[EMAIL PROTECTED](?:[\-.0-9A-Z_a-z]+\.)+\w+'
>
> SAC> Feed it a bunch of dot's followed by a non-word...
>
> SAC> Say... '[EMAIL PROTECTED]'
>
> SAC> and, on some regexp interpreters, that line will take a few minutes to
> SAC> fail to match. I've not tested perl; you can if you wish.
>
> Well, perl eats thru that one faster than you can blink. On a dual
> 1.25GHz G4 powermac running perl 5.8.0 with this script:
About 4 years ago, a patch by Ilya went in that introduced a cache
that makes this expression take O(n^2) instead of exponential time. So
in the case of perl, this issue is less of a problem. On other
interpreters, such as python this will take exponential time.
Even in the case of perl, O(n^2) is noticable. Here, I show the number
of '.''s and the corresponding runtime. Observe:
1000 elapsed 0.17
2000 elapsed 0.7
3000 elapsed 1.55
4000 elapsed 2.74
5000 elapsed 4.3
6000 elapsed 6.21
7000 elapsed 8.41
8000 elapsed 11.01
9000 elapsed 13.95
10000 elapsed 17.27
11000 elapsed 20.85
12000 elapsed 24.68
13000 elapsed 28.97
14000 elapsed 33.77
15000 elapsed 38.94
You can observe that each time the number of .'s doubles, the runtime
quadruples.
Scott
#!/usr/bin/perl -wT
use strict;
for (my $n=0 ; $n < 1000000 ; $n += 500) {
my $str = '[EMAIL PROTECTED]' . ('.' x $n ) . '#';
my ($userst,$system,$cuser,$csystem) = times;
$str =~ m/[EMAIL PROTECTED](?:[\-.0-9A-Z_a-z]+\.)+\w+/;
my ($useret,$system,$cuser,$csystem) = times;
print "$n elapsed ".($useret-$userst)."\n";
}
-------------------------------------------------------
This SF.Net email sponsored by: Free pre-built ASP.NET sites including
Data Reports, E-commerce, Portals, and Forums are available now.
Download today and enter to win an XBOX or Visual Studio .NET.
http://aspnet.click-url.com/go/psa00100003ave/direct;at.aspnet_072303_01/01
_______________________________________________
Spamassassin-talk mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/spamassassin-talk
