regex - 为什么Perl回溯比赛失败似乎比比赛成功花费更少的时间？

我有一个巨大的文件aab.txt，其内容为aaa ... aab。

令我惊讶的是

perl -ne '/a*bb/' < aab.txt

运行(匹配失败)的速度快于

perl -ne '/a*b/' < aab.txt

(比赛成功)。为什么？？？？两者都应首先吞噬所有a，然后第二个立即成功，而第一个则必须一遍又一遍地回溯以失败。

最佳答案

对Perl正则表达式进行了优化，使其尽可能早地失败，而不是尽可能快地成功。遍历大型日志文件时，这很有意义。

有一种优化方法，该优化方法首先查找字符串的恒定部分，在这种情况下为“ float ” b或bb。这可以非常有效地进行检查，而不必跟踪回溯状态。找不到bb，比赛在那里中止。
b并非如此。找到该 float 子字符串，并从那里构造匹配项。这是正则表达式匹配项的调试输出(程序为"aaab" =~ /a*b/):

Compiling REx "a*b"
synthetic stclass "ANYOF_SYNTHETIC[ab][]".
Final program:
   1: STAR (4)
   2:   EXACT <a> (0)
   4: EXACT <b> (6)
   6: END (0)
floating "b" at 0..2147483647 (checking floating) stclass ANYOF_SYNTHETIC[ab][] minlen 1
Guessing start of match in sv for REx "a*b" against "aaab"
Found floating substr "b" at offset 3...
start_shift: 0 check_at: 3 s: 0 endpos: 4 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "a*b" against "aaab"
Matching stclass ANYOF_SYNTHETIC[ab][] against "aaab" (4 bytes)
   0 <> <aaab>               |  1:STAR(4)
                                  EXACT <a> can match 3 times out of 2147483647...
   3 <aaa> <b>               |  4:  EXACT <b>(6)
   4 <aaab> <>               |  6:  END(0)
Match successful!
Freeing REx: "a*b"

您可以使用debug编译指示的re选项获得此类输出。

从严格意义上讲，无需查找b或bb，但它可以使匹配更早地失败。

关于regex - 为什么Perl回溯比赛失败似乎比比赛成功花费更少的时间？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19578512/