regex - 在正则表达式中使用替换是否比后续替换更快

Question

我有一个很直接的问题。在我工作的地方，我看到很多正则表达式出现。它们在 Perl 中用于替换和/或删除文本中的某些字符串，例如：

$string=~s/^.+\///;
$string=~s/\.shtml//;
$string=~s/^ph//;

我知道您不能连接第一个和最后一个替换，因为您可能只想ph在第一次替换后替换字符串的开头。但是，我会将第一个和第二个正则表达式与交替放在一起：$string=~s/(^.+\/|\.shtml)//;因为我们正在处理数千个文件（+500,000），所以我想知道哪种方法最有效。

score 10 · Accepted Answer

你的表达不等价

这个：

$string=~s/^.+\///;
$string=~s/\.shtml//;

替换文本.shtml 和直到并包括最后一个斜杠的所有内容。

这个：

$string=~s/(^.+\/|\.shtml)//;

替换文本或直到并包括最后一个斜杠的所有内容.shtml 。

这是组合正则表达式的一个问题：一个复杂的正则表达式比几个简单的正则表达式更难编写、更难理解和更难调试。

哪个更快可能并不重要

即使您的表达式是等价的，使用其中一个也可能不会对您的程序速度产生重大影响。像这样的内存操作s///比文件 I/O 快得多，并且您已经表明您正在执行大量文件 I/O。

您应该使用诸如Devel::NYTProf 之类的东西来分析您的应用程序，以查看这些特定替换是否实际上是一个瓶颈（我怀疑它们是）。不要浪费时间优化已经很快的东西。

交替阻碍优化器

请记住，您是在比较苹果和橙子，但如果您仍然对性能感到好奇，您可以查看 perl 如何使用repragma评估特定的正则表达式：

$ perl -Mre=debug -e'$_ = "foobar"; s/^.+\///; s/\.shtml//;'
...
Guessing start of match in sv for REx "^.+/" against "foobar"
Did not find floating substr "/"...
Match rejected by optimizer
Guessing start of match in sv for REx "\.shtml" against "foobar"
Did not find anchored substr ".shtml"...
Match rejected by optimizer
Freeing REx: "^.+/"
Freeing REx: "\.shtml"

正则表达式引擎有一个优化器。优化器搜索必须出现在目标字符串中的子字符串；如果找不到这些子字符串，则匹配立即失败，而不检查正则表达式的其他部分。

使用/^.+\//，优化器知道$string必须包含至少一个斜线才能匹配；当它没有找到斜线时，它会立即拒绝匹配而不调用完整的正则表达式引擎。类似的优化发生在/\.shtml/.

下面是 perl 对组合正则表达式的作用：

$ perl -Mre=debug -e'$_ = "foobar"; s/(?:^.+\/|\.shtml)//;'
...
Matching REx "(?:^.+/|\.shtml)" against "foobar"
   0 <> <foobar>             |  1:BRANCH(7)
   0 <> <foobar>             |  2:  BOL(3)
   0 <> <foobar>             |  3:  PLUS(5)
                                    REG_ANY can match 6 times out of 2147483647...
                                    failed...
   0 <> <foobar>             |  7:BRANCH(11)
   0 <> <foobar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   1 <f> <oobar>             |  1:BRANCH(7)
   1 <f> <oobar>             |  2:  BOL(3)
                                    failed...
   1 <f> <oobar>             |  7:BRANCH(11)
   1 <f> <oobar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   2 <fo> <obar>             |  1:BRANCH(7)
   2 <fo> <obar>             |  2:  BOL(3)
                                    failed...
   2 <fo> <obar>             |  7:BRANCH(11)
   2 <fo> <obar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   3 <foo> <bar>             |  1:BRANCH(7)
   3 <foo> <bar>             |  2:  BOL(3)
                                    failed...
   3 <foo> <bar>             |  7:BRANCH(11)
   3 <foo> <bar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   4 <foob> <ar>             |  1:BRANCH(7)
   4 <foob> <ar>             |  2:  BOL(3)
                                    failed...
   4 <foob> <ar>             |  7:BRANCH(11)
   4 <foob> <ar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   5 <fooba> <r>             |  1:BRANCH(7)
   5 <fooba> <r>             |  2:  BOL(3)
                                    failed...
   5 <fooba> <r>             |  7:BRANCH(11)
   5 <fooba> <r>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
Match failed
Freeing REx: "(?:^.+/|\.shtml)"

注意输出有多长。由于交替，优化器不会启动，而是执行完整的正则表达式引擎。在最坏的情况下（不匹配），交替的每个部分都针对字符串中的每个字符进行测试。这不是很有效。

所以，交替更慢，对吧？没有为什么...

这取决于您的数据

同样，我们正在比较苹果和橙子，但是：

$string = 'a/really_long_string';

组合的正则表达式实际上可能更快，因为使用s/\.shtml//时，优化器必须在拒绝匹配之前扫描大部分字符串，而组合的正则表达式匹配得很快。

您可以对此进行基准测试以获取乐趣，但这基本上没有意义，因为您正在比较不同的事物。

score 3 · Accepted Answer

在 Perl 中如何实现正则表达式交替在中得到了很好的解释perldoc perlre

匹配这个或那个

我们可以用交替元字符匹配不同的字符串'|'。为了匹配dogor cat，我们形成了正则表达式dog|cat。和以前一样，Perl 将尝试在字符串中尽可能早的点匹配正则表达式。在每个字符位置，Perl 将首先尝试匹配第一个替代项，dog. 如果dog不匹配，Perl 将尝试下一个替代方案，cat. 如果cat两者都不匹配，则匹配失败，Perl 移动到字符串中的下一个位置。一些例子：
"cats and dogs" =~ /cat|dog|bird/;  # matches "cat"
"cats and dogs" =~ /dog|cat|bird/;  # matches "cat" 
即使dog是第二个正则表达式中的第一个替代方案，cat也能够在字符串中更早地匹配。
"cats"          =~ /c|ca|cat|cats/; # matches "c"
"cats"          =~ /cats|cat|ca|c/; # matches "cats" 
在这里，所有备选方案都在第一个字符串位置匹配，所以第一个备选方案是匹配的。如果某些替代方案是其他替代方案的截断，则将最长的替代方案放在首位，以使它们有机会匹配。
"cab" =~ /a|b|c/ # matches "c"
                 # /a|b|c/ == /[abc]/ 
最后一个例子指出，字符类就像字符的交替。在给定的字符位置，允许正则表达式匹配成功的第一个替代方案将是匹配的那个。

所以这应该解释你在正则表达式中使用交替时所付出的代价。

将简单的正则表达式放在一起时，您不会付出这样的代价。在 SO的另一个相关问题中对此进行了很好的解释。当直接搜索常量字符串或问题中的一组字符时，可以进行优化并且不需要回溯，这意味着可能更快的代码。

在定义正则表达式交替时，只需选择一个好的顺序（将最常见的结果放在首位）就可以影响性能。在两个选项或二十个选项之间进行选择是不一样的。与往常一样，过早的优化是万恶之源，如果有问题或需要改进，您应该对代码 ( Devel::NYTProf )进行检测。但作为一般规则，交替应保持在最低限度，并尽可能避免，因为：

它们很容易使正则表达式变得过于复杂。我们喜欢简单、易于理解/调试/维护正则表达式。
可变性和输入相关。它们可能是问题的意外来源，因为它们会回溯，并可能导致意外的性能不足，具体取决于您的输入。据我了解，没有任何情况下它们会更快。
从概念上讲，您正在尝试匹配两种不同的事物，因此我们可以争辩说两种不同的陈述比一个更正确和清晰。

希望这个答案更接近您的期望。

score 1 · Accepted Answer

首先，根据您的真实数据衡量各种选项，因为再多的理论都无法胜过实验（如果可以做到的话）。CPAN 上有许多计时模块可以帮助您。

其次，如果你决定优化正则表达式，不要用手把它们挤成一个巨大的怪物，试着用代码组装“主”正则表达式。否则没有人能够破译密码。

score 1 · Accepted Answer

组合不是你的最佳选择

如果您有三个运行良好的正则表达式，那么将它们组合起来没有任何好处。重写它们不仅为错误打开了大门，而且使程序员和引擎都更难阅读正则表达式。

此页面建议改为：

while (<FILE>) {
    next if (/^(?:select|update|drop|insert|alter)\b/);     
    ...  
}

你应该使用：

while (<FILE>) {
    next if (/^select/);
    next if (/^update/);
    ...
}

您可以进一步优化您的正则表达式

您可以使用正则表达式对象，这将确保您的正则表达式不会在循环中重新编译：

my $query = qr/foo$bar/; #compiles here
@matches = (  );
...
while (<FILE>) {
    push @matches, $_ if /$query/i;
}

您也许还可以优化.+. 它会吃掉整个文件，然后必须逐个字符地回溯，直到找到 a/才能匹配。如果每个文件只有一个/，请尝试使用否定字符类，例如：（[^/]转义：）[^\/]。您希望/在文件中的哪里找到？知道这将使您的正则表达式变得更快。

更换速度取决于其他因素

如果您有性能问题（目前，使用 3 个正则表达式），它可能是您程序的不同部分。虽然计算机的处理速度呈指数级增长，但读写速度却几乎没有增长。

可能有更快的引擎来搜索和替换文件中的文本

Perl 使用 NFA，它比 DFA 引擎 sed 更慢但更强大。NFA 回溯（尤其是更改）并且具有最坏情况的指数运行时间。DFA 具有线性执行时间。您的模式不需要 NFA 引擎，因此您可以非常轻松地在 DFA 引擎（如 sed）中使用您的正则表达式。

根据这里sed 可以以每秒处理8210 万个字符的速度进行搜索和替换（请注意，此测试是写入/dev/null，因此硬盘写入速度并不是真正的因素）。

score 0 · Accepted Answer

可能有点跑题了，但是如果实际替换很少，相对于compares的数量（10％-20％？），您可以先使用索引匹配来获得一些速度

$string=~s/\.shtml//
    if index($string, ".shtml");

score -2 · Accepted Answer

第二种方法最好将第一个和第二个正则表达式与交替放在一起。因为在该方法中，perl 会遍历一次，并检查两个表达式。

如果您使用 perl 必须为两个表达式单独遍历的第一种方法。

因此，第二种方法中的循环数减少了。