MarkDown 源代码中的正则表达式惰性量词和否定类

Question

我正在查看 MarkDown John Gruber 用 Perl 编写的代码，有一个名为 _Detab 的子程序，可以将制表符转换为空格，同时保留文本的缩进。有问题的代码行是 Markdown.pl 中的 1314:

$text =~ s{(.*?)\t}{$1.(' ' x ($g_tab_width - length($1) % $g_tab_width))}ge;

这不会导致不必要的回溯吗？下面的模式不是会执行得更高效吗？

/([^\t\n]*)\t/

或者我错过了什么？谢谢。

顺便说一句，我只是否定 \n 而不是 \r 因为所有换行符都预先标准化为 \n 。

Answer 1

不要猜测何时可以进行基准测试:

use Benchmark 'cmpthese';

my $source = "\t\thello\n\t\t\tworld\n" x 100;
my $g_tab_width = 8;

my ($textU, $textN);

cmpthese(-3, {
  ungreedy => sub {
    $textU = $source;
    $textU =~ s{(.*?)\t}{$1.(' ' x ($g_tab_width - length($1) % $g_tab_width))}ge;
  },

 negated => sub {
    $textN = $source;
    $textN =~ s{([^\n\t]*)\t}{$1.(' ' x ($g_tab_width - length($1) % $g_tab_width))}ge;
  },
});

die "whoops" unless $textN eq $textU; # ensure they do the same thing

我发现非贪婪版本(如 Markdown 源代码中所示)比您建议的否定字符类快大约 40%:

           Rate  negated ungreedy
negated  1204/s       --     -30%
ungreedy 1718/s      43%       --

我的猜测是匹配 . 比否定字符类更有效，这弥补了额外的回溯。需要更多测试来证实这一点。