rjh*_*rjh 56 regex perl regex-greedy
为什么更换\s*(或甚至\s\s*)\s+导致此输入的加速？
use Benchmark qw(:all);
$x=(" " x 100000) . "_\n";
$count = 100;
timethese($count, {
'/\s\s*\n/' => sub { $x =~ /\s\s*\n/ },
'/\s+\n/' => sub { $x =~ /\s+\n/ },
});
我注意到s/\s*\n\s*/\n/g我的代码中有一个缓慢的正则表达式- 当给出一个450KB的输入文件,其中包含大量空格,其中有一些非空格,最后一个换行符 - 正则表达式挂起并且从未完成.
我直观地取代了正则表达式,s/\s+\n/\n/g; s/\n\s+/\n/g;一切都很顺利.
但为什么它这么快？使用后re Debug => "EXECUTE"我注意到\s+版本以某种方式优化,只在一次迭代中运行:http://pastebin.com/0Ug6xPiQ
Matching REx "\s*\n" against " _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{non-utf8-latin1-all}{unicode_all}] against " _%n" (9 bytes)
0 <> < _%n> | 1:STAR(3)
SPACE can match 7 times out of 2147483647...
failed...
1 < > < _%n> | 1:STAR(3)
SPACE can match 6 times out of 2147483647...
failed...
2 < > < _%n> | 1:STAR(3)
SPACE can match 5 times out of 2147483647...
failed...
3 < > < _%n> | 1:STAR(3)
SPACE can match 4 times out of 2147483647...
failed...
4 < > < _%n> | 1:STAR(3)
SPACE can match 3 times out of 2147483647...
failed...
5 < > < _%n> | 1:STAR(3)
SPACE can match 2 times out of 2147483647...
failed...
6 < > < _%n> | 1:STAR(3)
SPACE can match 1 times out of 2147483647...
failed...
8 < _> <%n> | 1:STAR(3)
SPACE can match 1 times out of 2147483647...
8 < _> <%n> | 3: EXACT <\n>(5)
9 < _%n> <> | 5: END(0)
Match successful!
Matching REx "\s+\n" against " _%n"
Matching stclass SPACE against " _" (8 bytes)
0 <> < _%n> | 1:PLUS(3)
SPACE can match 7 times out of 2147483647...
failed...
我知道如果不存在换行符,Perl 5.10+将立即失败正则表达式(不运行它).我怀疑它正在使用换行符的位置来减少搜索量.对于上面的所有情况,它似乎巧妙地减少了所涉及的回溯(通常/\s*\n/对一串空格将采用指数时间).任何人都可以深入了解为什么\s+版本更快？
另请注意,\s*?不提供任何加速.
Tho*_*oub 28
首先,即使最终的正则表达式不会保持相同的含义,让我们减少了对正则表达式\s*0,并\s+0和使用(" " x 4) . "_0"作为输入.对于持怀疑态度的,你可以看到这里的滞后仍然存在.
现在让我们考虑以下代码:
$x = (" " x 4) . "_ 0";
$x =~ /\s*0/; # The slow line
$x =~ /\s+0/; # The fast line
挖一点用use re debugcolor;,我们得到以下的输出:
Guessing start of match in sv for REx "\s*0" against " _0"
Found floating substr "0" at offset 5...
start_shift: 0 check_at: 5 s: 0 endpos: 6 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s*0" against " _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against " _0" (6 bytes)
0 < _0>| 1:STAR(3)
POSIXD[\s] can match 4 times out of 2147483647...
failed...
1 < _0>| 1:STAR(3)
POSIXD[\s] can match 3 times out of 2147483647...
failed...
2 < _0>| 1:STAR(3)
POSIXD[\s] can match 2 times out of 2147483647...
failed...
3 < _0>| 1:STAR(3)
POSIXD[\s] can match 1 times out of 2147483647...
failed...
5 < _0>| 1:STAR(3)
POSIXD[\s] can match 0 times out of 2147483647...
5 < _0>| 3: EXACT <0>(5)
6 < _0>| 5: END(0)
Match successful!
-----------------------
Guessing start of match in sv for REx "\s+0" against " _0"
Found floating substr "0" at offset 5...
start_shift: 1 check_at: 5 s: 0 endpos: 5 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+0" against " _0"
Matching stclass POSIXD[\s] against " _" (5 bytes)
0 < _0>| 1:PLUS(3)
POSIXD[\s] can match 4 times out of 2147483647...
failed...
Contradicts stclass... [regexec_flags]
Match failed
Perl似乎针对失败进行了优化.它将首先查找常量字符串(仅消耗O(N)).在这里,它会寻找0:Found floating substr "0" at offset 5...
然后,它会与开始变正则表达式,respectivly的一部分\s*和\s+,对整个最小字符串进行检查:
Matching REx "\s*0" against " _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against " _0" (6 bytes)
Matching REx "\s+0" against " _0"
Matching stclass POSIXD[\s] against " _" (5 bytes) # Only 5 bytes because there should be at least 1 "\s" char
之后,它将寻找符合stclass要求的第一个位置,位于0位置.
\s*0:
0\s+0:
如果您想获得Perl正则表达式优化的乐趣,您可以考虑以下正则表达式/ *\n和/ * \n.乍一看,它们看起来一样,具有相同的意义......但如果你对抗(" " x 40000) . "_\n"第一个将检查所有可能性,而第二个将" \n"立即寻找并失败.
在一个普通的,非优化的正则表达式引擎中,两个正则表达式都可能导致灾难性的回溯,因为它们需要在碰撞时重试模式.但是,在上面的示例中,第二个不会因Perl而失败,因为它已经过优化find floating substr "0%n"
您可以在Jeff Atwood的博客上看到另一个例子.
还要注意问题不是\s考虑问题,而是使用任何模式xx*而不是x+参见0s的示例以及正则表达式爆炸量词
使用这样的简短示例,行为是"可查找的",但如果您开始使用复杂的模式,那么很难发现,例如:正则表达式挂起程序(100%CPU使用率)
Thi*_*Not 20
当\s+在模式的开头存在"加"节点(例如)并且节点不匹配时,正则表达式引擎向前跳到故障点并再次尝试; 用\s*,而另一方面,发动机只前进一次一个字符.
Yves Orton 在这里很好地解释了这个优化:
起始类优化有两种模式,"尝试每个有效的起始位置"(doevery)和"触发器模式"(!doevery),其中它仅尝试序列中的第一个有效起始位置.
考虑/(\ d +)X /和字符串"123456Y",现在我们知道如果我们在匹配"123456"后未能匹配X,那么我们也将在"23456"之后无法匹配(假设没有邪恶的技巧,无论如何都禁用了优化),所以我们知道我们可以跳到检查/失败/然后才开始寻找真正的匹配.这是触发器模式.
/\s+/触发触发模式; /\s*/,/\s\s*/和/\s\s+/没有.此优化不能应用于"星形"节点,\s*因为它们可以匹配零个字符,因此序列中某一点的失败并不表示稍后在同一序列中失败.
您可以在每个正则表达式的调试输出中看到这一点.我已经突出显示了跳过的字符^.比较一下(一次跳过四个字符):
$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d+x/'
...
0 <> <123 456 78> | 1:PLUS(3)
POSIXD[\d] can match 3 times out of 2147483647...
failed...
4 <123 > <456 789 x> | 1:PLUS(3)
^^^^
POSIXD[\d] can match 3 times out of 2147483647...
failed...
8 <23 456 > <789 x> | 1:PLUS(3)
^^^^
POSIXD[\d] can match 3 times out of 2147483647...
failed...
对此(一次跳过一个或两个字符):
$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d*x/'
...
0 <> <123 456 78> | 1:STAR(3)
POSIXD[\d] can match 3 times out of 2147483647...
failed...
1 <1> <23 456 789> | 1:STAR(3)
^
POSIXD[\d] can match 2 times out of 2147483647...
failed...
2 <12> <3 456 789 > | 1:STAR(3)
^
POSIXD[\d] can match 1 times out of 2147483647...
failed...
4 <123 > <456 789 x> | 1:STAR(3)
^^
POSIXD[\d] can match 3 times out of 2147483647...
failed...
5 <123 4> <56 789 x> | 1:STAR(3)
^
POSIXD[\d] can match 2 times out of 2147483647...
failed...
6 <23 45> <6 789 x> | 1:STAR(3)
^
POSIXD[\d] can match 1 times out of 2147483647...
failed...
8 <23 456 > <789 x> | 1:STAR(3)
^^
POSIXD[\d] can match 3 times out of 2147483647...
failed...
9 <23 456 7> <89 x> | 1:STAR(3)
^
POSIXD[\d] can match 2 times out of 2147483647...
failed...
10 <23 456 78> <9 x> | 1:STAR(3)
^
POSIXD[\d] can match 1 times out of 2147483647...
failed...
12 <23 456 789 > <x> | 1:STAR(3)
^^
POSIXD[\d] can match 0 times out of 2147483647...
12 <23 456 789 > <x> | 3: EXACT <x>(5)
13 <23 456 789 x> <> | 5: END(0)
请注意,优化不适用于/\s\s+/,因为\s+不在模式的开头.但是,两者/\s\s+/(逻辑上相当于/\s{2,}/)和/\s\s*/(逻辑上相当于/\s+/)可能都可以被优化; 询问perl5-porters是否值得付出努力可能是有道理的.
如果您感兴趣,可以通过PREGf_SKIP在编译时在正则表达式上设置标志来启用"触发器模式" .看到周围线7344和7405中的代码regcomp.c在和线1585 regexec.c在5.24.0源.
zdi*_*dim 14
的\s+\n要求之前的字符\n是一个SPACE.
根据use re qw(debug)编译确定它需要一个已知数量的空格的直字符串,直到子字符串\n,首先在输入中检查.然后它会针对输入的剩余部分检查固定长度的仅空格子字符串,但是它会失败_.无论输入有多少空格,都可以检查它.(如果_\n发现每个更多,则每个调试输出都会直接失败.)
以这种方式看待它,这是一个你几乎所期望的优化,利用一个相当具体的搜索模式,并幸运地输入.除了与其他引擎相比时,显然不做这种分析.
有了\s*\n这个情况并非如此.一旦\n找到并且前一个字符不是空格,搜索就没有失败,因为\s*什么都不允许(零个字符).也没有固定长度的子串,它在回溯游戏中.
我不知道正则表达式引擎的内部的,但它看起来像它不承认\s+在某些方面相同的\s\s*,因为在第二个它的空间相匹配,然后尝试匹配的空间不断增长的数字,在第一次,它立即得出结论,没有匹配.
输出使用use re qw( Debug );清楚地显示了这一点,使用更短的字符串:
test_re.pl
#!/usr/bin/env perl
use re qw(debug);
$x=(" " x 10) . "_\n";
print '-'x50 . "\n";
$x =~ /\s+\n/;
print '-'x50 . "\n";
$x =~ /\s\s*\n/;
print '-'x50 . "\n";
产量
Compiling REx "\s+\n"
Final program:
1: PLUS (3)
2: SPACE (0)
3: EXACT <\n> (5)
5: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE plus minlen 2
Compiling REx "\s\s*\n"
Final program:
1: SPACE (2)
2: STAR (4)
3: SPACE (0)
4: EXACT <\n> (6)
6: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE minlen 2
--------------------------------------------------
Guessing start of match in sv for REx "\s+\n" against " _%n"
Found floating substr "%n" at offset 11...
start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+\n" against " _%n"
Matching stclass SPACE against " _" (11 bytes)
0 <> < > | 1:PLUS(3)
SPACE can match 10 times out of 2147483647...
failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Guessing start of match in sv for REx "\s\s*\n" against " _%n"
Found floating substr "%n" at offset 11...
start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s\s*\n" against " _%n"
Matching stclass SPACE against " _" (11 bytes)
0 <> < > | 1:SPACE(2)
1 < > < _> | 2:STAR(4)
SPACE can match 9 times out of 2147483647...
failed...
1 < > < _> | 1:SPACE(2)
2 < > < _> | 2:STAR(4)
SPACE can match 8 times out of 2147483647...
failed...
2 < > < _> | 1:SPACE(2)
3 < > < _%n> | 2:STAR(4)
SPACE can match 7 times out of 2147483647...
failed...
3 < > < _%n> | 1:SPACE(2)
4 < > < _%n> | 2:STAR(4)
SPACE can match 6 times out of 2147483647...
failed...
4 < > < _%n> | 1:SPACE(2)
5 < > < _%n> | 2:STAR(4)
SPACE can match 5 times out of 2147483647...
failed...
5 < > < _%n> | 1:SPACE(2)
6 < > < _%n> | 2:STAR(4)
SPACE can match 4 times out of 2147483647...
failed...
6 < > < _%n> | 1:SPACE(2)
7 < > < _%n> | 2:STAR(4)
SPACE can match 3 times out of 2147483647...
failed...
7 < > < _%n> | 1:SPACE(2)
8 < > < _%n> | 2:STAR(4)
SPACE can match 2 times out of 2147483647...
failed...
8 < > < _%n> | 1:SPACE(2)
9 < > < _%n> | 2:STAR(4)
SPACE can match 1 times out of 2147483647...
failed...
9 < > < _%n> | 1:SPACE(2)
10 < > <_%n> | 2:STAR(4)
SPACE can match 0 times out of 2147483647...
failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Freeing REx: "\s+\n"
Freeing REx: "\s\s*\n"