MarkDown源中的正则表达式懒惰量词与否定类

Question

我正在查看John Gruber在Perl中编写的MarkDown代码,并且有一个子命令_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%       --

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