根据perlre的说法,执行以下代码需要几秒钟的时间:
$ time perl -E '$_="((()" . ("a") x 18; say "ok" if m{ (([^()]+|( [^()]* ))+)}x;'
real 0m0.006s
user 0m0.000s
sys 0m0.005s
文档说:
考虑上面的模式如何检测no-match on
((()aaaaaaaaaaaaaaaaaa
在几秒钟内,但每额外这次字母翻倍了。
如所见,在我的笔记本电脑上只需要几分之一秒。即使运行100万个a
也可以在半秒内完成:
$ time perl -E '$_="((()" . ("a") x 1000000; say "ok" if m{ (([^()]+|( [^()]* ))+)}x;'
real 0m0.454s
user 0m0.446s
sys 0m0.008s
我在这里错过了什么?
要弄清楚正则表达式引擎在做什么,你可以做的一个技巧是:
use re 'debug';
例如:
use strict;
use warnings;
use re 'debug';
my $str = "a" x 18;
$str =~ m{ (([^()]+|( [^()]* ))+)}x;
这将打印出regex引擎实际在做什么:
Compiling REx " (([^()]+|( [^()]* ))+)"
Final program:
1: EXACT <(> (3)
3: CURLYX[0] {1,32767} (40)
5: OPEN1 (7)
7: BRANCH (20)
8: PLUS (37)
9: ANYOF[^()][{above_bitmap_all}] (0)
20: BRANCH (FAIL)
21: EXACT <(> (23)
23: STAR (35)
24: ANYOF[^()][{above_bitmap_all}] (0)
35: EXACT <)> (37)
37: CLOSE1 (39)
39: WHILEM[1/3] (0)
40: NOTHING (41)
41: EXACT <)> (43)
43: END (0)
anchored "(" at 0 floating ")" at 2..2147483647 (checking floating) minlen 3
Matching REx " (([^()]+|( [^()]* ))+)" against "aaaaaaaaaaaaaaaaaa"
Intuit: trying to determine minimum start position...
doing 'check' fbm scan, [2..18] gave -1
Did not find floating substr ")"...
Match rejected by optimizer
Freeing REx: " (([^()]+|( [^()]* ))+)"
如果你把括号加回去,你会得到一个不同的结果——我大约需要2000步来处理正则表达式。每增加一个字母,这个步骤就会变长——大约300步。
所以我会说是的-灾难性的回溯正在发生,但你可能会发现处理器(和正则表达式引擎优化)意味着时间大大缩短。
use strict;
use warnings;
use re 'debug';
my $str = "((()"."a" x 100_000;
$str =~ m{ (([^()]+|( [^()]* ))+)}x;
运行时间相当长,但至少有一部分原因是将文本打印到屏幕上实际上相当"昂贵"。
我的测试表明("a"的数量)
10 : 1221 lines of output (broadly correlated with regex steps)
11 : 1324 (+103)
12 : 1467 (+143)
13 : 1590 (+129)
14 : 1728 (+138)
15 : 1852 (+124)
20 : 2630 (approx +155/extra)
30 : 4536 (+190/extra)
40 : 6940 (+240/extra)
50 : 9846 (+290/extra)
100 - 31,846 (+440/extra letter)
所以当然看起来像指数行为-但在两种情况下,处理时间仍然相当快,我认为这是更快的cpu(也许更好的优化正则表达式引擎)
考虑上面的模式如何在几秒钟内检测到
((()aaaaaaaaaaaaaaaaaa
上的不匹配。
这句话至少可以追溯到2001年4月,当时perl 5.6.1刚刚发布。您可以在search.cpan.org/~gsar/perl-5.6.1/pod/perlre.pod上看到该版本的perlre手册页。
这可能是在编写软件文档时需要吸取的教训。要小心你写的东西,因为即使经过多年的改进和别人的多次修改,你写出来的东西也不会改变。