regexp中的回溯速度比预期的要快
根据
perlre,以下代码应该花几秒钟执行:
$time perl -E '$_="((()" . ("a") x 18; say "ok" if m{ (([^()]+|( [^()]* ))+)}x;' real 0m0.006s user 0m0.000s sys 0m0.005s 文件说:
如图所示,我的笔记本电脑只需要几分之一秒. $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; 然后,这将打印正则表达式引擎实际执行的操作: 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) 所以肯定看起来像是指数行为 – 但在这两种情况下,处理时间仍然相当快,我将其归因于更快的cpus(并且可能更好地优化正则表达式引擎) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |