在正则表达式中使用交替比后续替换更快吗
Is it faster to use alternation than subsequent replacements in regular expressions
我有一个很简单的问题。在我工作的地方，我看到很多正则表达式。它们在 Perl 中用于替换 and/or 去除文本中的一些字符串，例如：
$string=~s/^.+\///;
$string=~s/\.shtml//;
$string=~s/^ph//;
我知道您不能连接第一个和最后一个替换，因为您可能只想在执行第一个替换后替换字符串开头的 ph。但是，我会将第一个和第二个正则表达式交替放置：$string=~s/(^.+\/|\.shtml)//; 因为我们正在处理数千个文件 (+500,000) 我想知道哪种方法最有效。
首先，根据您的真实数据衡量各种选项，因为再多的理论也无法战胜实验（如果可以的话）。 CPAN上有很多计时模块可以帮到你。
其次，如果您决定优化正则表达式，请不要手动将它们压成一个巨大的怪物，尝试使用代码 assemble “大师”正则表达式。否则没有人能够破译密码。
第二种方法最好，您可以交替使用第一个和第二个正则表达式。
因为在那个方法中，perl 会遍历一次，并检查两个表达式。
如果您使用第一种方法，其中 perl 必须分别遍历两个表达式。
因此在第二种方法中减少了循环数。
中很好地解释了如何在 Perl 中实现正则表达式交替
Matching this or that
We can match different character strings with the alternation
metacharacter '|' . To match dog or cat , we form the regex dog|cat .
As before, Perl will try to match the regex at the earliest possible
point in the string. At each character position, Perl will first try
to match the first alternative, dog . If dog doesn't match, Perl will
then try the next alternative, cat . If cat doesn't match either, then
the match fails and Perl moves to the next position in the string.
Some examples:
"cats and dogs" =~ /cat|dog|bird/; # matches "cat"
"cats and dogs" =~ /dog|cat|bird/; # matches "cat"
Even though dog is the first alternative in the second regex, cat is able to match
earlier in the string.
"cats" =~ /c|ca|cat|cats/; # matches "c"
"cats" =~ /cats|cat|ca|c/; # matches "cats"
Here, all the alternatives match at the first string position, so the
first alternative is the one that matches. If some of the alternatives
are truncations of the others, put the longest ones first to give them
a chance to match.
"cab" =~ /a|b|c/ # matches "c"
# /a|b|c/ == /[abc]/
The last example points out
that character classes are like alternations of characters. At a given
character position, the first alternative that allows the regexp match
to succeed will be the one that matches.
所以这应该可以解释您在正则表达式中使用交替项时支付的价格。
将简单的正则表达式放在一起时，您不会付出这样的代价。它在 SO 中的另一个相关 question 中得到了很好的解释。当直接搜索常量字符串或问题中的一组字符时，可以进行优化并且不需要回溯，这意味着可能更快的代码。
定义正则表达式交替时，只需选择良好顺序（将最常见的结果放在首位）即可影响性能。在两个选项或二十个选项之间进行选择是不一样的。一如既往，过早的优化是万恶之源，你应该instrumentiate 你编码（Devel::NYTProf）想要改进。但作为一般规则，交替应保持在最低限度，并尽可能避免，因为：
- 他们很容易使正则表达式变得太大而复杂。我们喜欢简单、易于理解/调试/维护正则表达式。
- 可变性和输入相关。它们可能是意想不到的问题来源，因为它们 backtrack 并且可能导致性能意外下降，具体取决于您的输入。据我了解，它们不会更快。
- 从概念上讲，您正在尝试匹配两个不同的事物，因此我们可以争辩说，两个不同的陈述比一个更正确、更清楚。
希望这个答案更接近您的预期。
你的表达方式不对等
这个：
$string=~s/^.+\///;
$string=~s/\.shtml//;
替换文本 .shtml 和 直到并包括最后一个斜杠的所有内容。
这个：
$string=~s/(^.+\/|\.shtml)//;
替换 文本 .shtml 或 直到并包括最后一个斜杠的所有内容。
这是组合正则表达式的一个问题：与几个简单的正则表达式相比，单个复杂的正则表达式更难编写、更难理解和更难调试。
哪个更快可能并不重要
即使您的表达式 是 等价的，使用一个或另一个可能不会对您的程序速度产生重大影响。 s/// 之类的内存操作比文件 I/O 快得多，并且您已经表示您正在执行大量文件 I/O.
您应该使用 Devel::NYTProf 之类的东西来分析您的应用程序，看看这些特定的替换是否真的是瓶颈（我怀疑它们是）。不要浪费时间优化已经很快的东西。
交替阻碍优化器
请记住，您是在比较苹果和橘子，但如果您仍然对性能感到好奇，您可以查看 perl 如何使用 re pragma:
评估特定的正则表达式
$ 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//，优化器必须在拒绝匹配之前扫描大部分字符串，而组合正则表达式匹配速度很快。
你可以 benchmark 这只是为了好玩，但它本质上是没有意义的，因为你在比较不同的东西。
组合不是您的最佳选择
如果您有三个运行良好的正则表达式，则将它们组合起来没有任何好处。重写它们不仅为错误打开了大门，还使程序员和引擎更难阅读正则表达式。
This page 建议改为：
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;
}
您也许还可以优化 .+。它会吃掉整个文件，然后必须逐个字符回溯，直到找到 / 才能匹配。如果每个文件只有一个 /，请尝试使用否定字符 class，例如：[^/]（转义：[^\/]）。您希望在文件中的什么位置找到 /？知道这一点将使您的正则表达式变得更快。
替换速度取决于其他因素
如果您有性能问题（目前，有 3 个正则表达式），它可能是您程序的不同部分。在计算机的处理速度呈指数级增长的同时，读写速度却几乎没有增长。
可能会有更快的引擎来搜索和替换文件中的文本
Perl 使用 NFA，它比 sed 的 DFA 引擎更慢但更强大。 NFA 回溯（尤其是有改动的）并且有一个最坏情况的指数 运行 时间。 DFA 具有线性执行时间。您的模式不需要 NFA 引擎，因此您可以非常轻松地在 DFA 引擎（如 sed）中使用正则表达式。
根据 here sed 可以以每秒处理 8210 万 个字符的速度进行搜索和替换（请注意，此测试正在写入 /dev/null, 所以硬盘写入速度并不是一个真正的因素）。
可能有点偏离主题，但如果实际替换很少见，相对于比较数（10%-20%？），首先使用索引匹配可能会提高一些速度
$string=~s/\.shtml//
if index($string, ".shtml");
我有一个很简单的问题。在我工作的地方，我看到很多正则表达式。它们在 Perl 中用于替换 and/or 去除文本中的一些字符串，例如：
$string=~s/^.+\///;
$string=~s/\.shtml//;
$string=~s/^ph//;
我知道您不能连接第一个和最后一个替换，因为您可能只想在执行第一个替换后替换字符串开头的 ph。但是，我会将第一个和第二个正则表达式交替放置：$string=~s/(^.+\/|\.shtml)//; 因为我们正在处理数千个文件 (+500,000) 我想知道哪种方法最有效。
首先，根据您的真实数据衡量各种选项，因为再多的理论也无法战胜实验（如果可以的话）。 CPAN上有很多计时模块可以帮到你。
其次，如果您决定优化正则表达式，请不要手动将它们压成一个巨大的怪物，尝试使用代码 assemble “大师”正则表达式。否则没有人能够破译密码。
第二种方法最好，您可以交替使用第一个和第二个正则表达式。 因为在那个方法中，perl 会遍历一次，并检查两个表达式。
如果您使用第一种方法，其中 perl 必须分别遍历两个表达式。
因此在第二种方法中减少了循环数。
Matching this or that
We can match different character strings with the alternation metacharacter
'|'. To matchdogorcat, we form the regexdog|cat. As before, Perl will try to match the regex at the earliest possible point in the string. At each character position, Perl will first try to match the first alternative,dog. Ifdogdoesn't match, Perl will then try the next alternative,cat. Ifcatdoesn't match either, then the match fails and Perl moves to the next position in the string. Some examples:"cats and dogs" =~ /cat|dog|bird/; # matches "cat" "cats and dogs" =~ /dog|cat|bird/; # matches "cat"Even though
dogis the first alternative in the second regex,catis able to match earlier in the string."cats" =~ /c|ca|cat|cats/; # matches "c" "cats" =~ /cats|cat|ca|c/; # matches "cats"Here, all the alternatives match at the first string position, so the first alternative is the one that matches. If some of the alternatives are truncations of the others, put the longest ones first to give them a chance to match.
"cab" =~ /a|b|c/ # matches "c" # /a|b|c/ == /[abc]/The last example points out that character classes are like alternations of characters. At a given character position, the first alternative that allows the regexp match to succeed will be the one that matches.
所以这应该可以解释您在正则表达式中使用交替项时支付的价格。
将简单的正则表达式放在一起时，您不会付出这样的代价。它在 SO 中的另一个相关 question 中得到了很好的解释。当直接搜索常量字符串或问题中的一组字符时，可以进行优化并且不需要回溯，这意味着可能更快的代码。
定义正则表达式交替时，只需选择良好顺序（将最常见的结果放在首位）即可影响性能。在两个选项或二十个选项之间进行选择是不一样的。一如既往，过早的优化是万恶之源，你应该instrumentiate 你编码（Devel::NYTProf）想要改进。但作为一般规则，交替应保持在最低限度，并尽可能避免，因为：
- 他们很容易使正则表达式变得太大而复杂。我们喜欢简单、易于理解/调试/维护正则表达式。
- 可变性和输入相关。它们可能是意想不到的问题来源，因为它们 backtrack 并且可能导致性能意外下降，具体取决于您的输入。据我了解，它们不会更快。
- 从概念上讲，您正在尝试匹配两个不同的事物，因此我们可以争辩说，两个不同的陈述比一个更正确、更清楚。
希望这个答案更接近您的预期。
你的表达方式不对等
这个：
$string=~s/^.+\///;
$string=~s/\.shtml//;
替换文本 .shtml 和 直到并包括最后一个斜杠的所有内容。
这个：
$string=~s/(^.+\/|\.shtml)//;
替换 文本 .shtml 或 直到并包括最后一个斜杠的所有内容。
这是组合正则表达式的一个问题：与几个简单的正则表达式相比，单个复杂的正则表达式更难编写、更难理解和更难调试。
哪个更快可能并不重要
即使您的表达式 是 等价的，使用一个或另一个可能不会对您的程序速度产生重大影响。 s/// 之类的内存操作比文件 I/O 快得多，并且您已经表示您正在执行大量文件 I/O.
您应该使用 Devel::NYTProf 之类的东西来分析您的应用程序，看看这些特定的替换是否真的是瓶颈（我怀疑它们是）。不要浪费时间优化已经很快的东西。
交替阻碍优化器
请记住，您是在比较苹果和橘子，但如果您仍然对性能感到好奇，您可以查看 perl 如何使用 re pragma:
$ 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//，优化器必须在拒绝匹配之前扫描大部分字符串，而组合正则表达式匹配速度很快。
你可以 benchmark 这只是为了好玩，但它本质上是没有意义的，因为你在比较不同的东西。
组合不是您的最佳选择
如果您有三个运行良好的正则表达式，则将它们组合起来没有任何好处。重写它们不仅为错误打开了大门，还使程序员和引擎更难阅读正则表达式。
This page 建议改为：
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;
}
您也许还可以优化 .+。它会吃掉整个文件，然后必须逐个字符回溯，直到找到 / 才能匹配。如果每个文件只有一个 /，请尝试使用否定字符 class，例如：[^/]（转义：[^\/]）。您希望在文件中的什么位置找到 /？知道这一点将使您的正则表达式变得更快。
替换速度取决于其他因素
如果您有性能问题（目前，有 3 个正则表达式），它可能是您程序的不同部分。在计算机的处理速度呈指数级增长的同时，读写速度却几乎没有增长。
可能会有更快的引擎来搜索和替换文件中的文本
Perl 使用 NFA，它比 sed 的 DFA 引擎更慢但更强大。 NFA 回溯（尤其是有改动的）并且有一个最坏情况的指数 运行 时间。 DFA 具有线性执行时间。您的模式不需要 NFA 引擎，因此您可以非常轻松地在 DFA 引擎（如 sed）中使用正则表达式。
根据 here sed 可以以每秒处理 8210 万 个字符的速度进行搜索和替换（请注意，此测试正在写入 /dev/null, 所以硬盘写入速度并不是一个真正的因素）。
可能有点偏离主题，但如果实际替换很少见，相对于比较数（10%-20%？），首先使用索引匹配可能会提高一些速度
$string=~s/\.shtml//
if index($string, ".shtml");