在正则表达式中使用回溯比预期的更快。

Question

在正则表达式中使用回溯比预期的更快。

8

根据 perlre 的说明，以下代码应该需要几秒钟才能执行完毕：

$ time perl -E '$_="((()" . ("a") x 18;  say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;'

real    0m0.006s
user    0m0.000s
sys 0m0.005s

文档中提到:

考虑上面的模式在几秒钟内无法检测出 ((()aaaaaaaaaaaaaaaaaa 的不匹配, 但是每增加一个字符则检测时间翻倍.

如所见，在我的笔记本电脑上仅需一小部分时间. 即使运行一百万个a，也只需要半秒钟完成.

$ time perl -E '$_="((()" . ("a") x 1000000;  say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;'

real    0m0.454s
user    0m0.446s
sys 0m0.008s

我在这里缺少什么？

- Håkon Hægland

Perl编译器可能已经为您修复了这个问题。尝试将((()aaaaaa导入标准输入。 - Zan Lynx

@ZanLynx 你是指 echo "((()aaaaaaaaaaaaaaaaaa" | perl -nE 'say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;' 吗？ - Håkon Hægland

是的。或者从另一个Perl脚本输出它，这样您就可以使用“x 10000”。 - Zan Lynx

@ZanLynx perl -E 'say "((()" . ("a") x 1000000;' | perl -nE 'say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;' 半秒钟内运行完成 - Håkon Hægland

3

使用 use re 'debug' 命令，它会告诉你处理 re 的步骤。请注意，我已经对原文进行了翻译，不含解释和其他内容。 - Sobrique

2个回答

2

考虑一下上面的模式在几秒钟内如何检测到((()aaaaaaaaaaaaaaaaaa中的无匹配项。这句话最早可以追溯到至少2001年4月，当时发布了perl 5.6.1。您可以查看该版本的perlre man页面，网址为search.cpan.org/~gsar/perl-5.6.1/pod/perlre.pod。也许在记录软件方面，我们可以从中吸取教训。请注意您所写的内容，因为尽管经过多年的改进和他人的多次分支，但您的书面文字将保持不变。

- David Hammen

效率点仍然有效 - 这样做非常低效，可能会具有欺骗性。 - Sobrique

@Sobrique - 没错。一个人可以很容易地编写一个需要很长时间才能执行的正则表达式。 - David Hammen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sobrique · Accepted Answer

你可以使用以下技巧来了解正则表达式引擎的工作方式：

use re 'debug';

E.g.:

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)

显然存在指数增长的趋势 - 不过无论哪种情况，处理时间仍然相当快。我认为这归功于更快的 CPU（也许正则表达式引擎优化得更好）。