c# - 正则表达式性能问题 - 谁能解释这个正则表达式很慢

Question

我正在尝试String.Contains()使用regex. 我注意到这种模式@".\*foo.\*"需要的时间比 this 长得多@"\A.\*foo.\*\Z"。

谁能解释为什么？

score 4 · Accepted Answer

因为没有锚，正则表达式引擎必须进行更多尝试匹配才能断定匹配是不可能的。考虑一个带有锚的例子：

Regex: \A.*foo.*\Z
Input: 123456789abcdef

正则表达式看到输入锚的开始并将其考虑在内。它现在尝试匹配第一个.*模式，并且由于它是贪婪的，它尝试匹配所有输入。然后它尝试匹配foo并失败，因此它f从.*匹配中释放并再次尝试。e它再次失败，从比赛中释放.*，再次尝试，失败等。

最终结果是，直到整个表达式无法匹配之前所进行的尝试次数与输入的长度成线性关系。

现在考虑非锚定情况：

Regex: .*foo.*
Input: 123456789abcdef

这一次，正则表达式引擎尝试从字符串的开头进行匹配，如上（使尝试次数与字符串的长度成线性关系）。但是当失败时，它会从 input 的第二个字符开始再次开始该过程。

也就是说，它尝试将第一个.*连续匹配：

123456789abcdef
123456789abcde
123456789abcd
...
1
                  (empty string due to the * quantifier)

到目前为止，这与锚定正则表达式相同。但是，虽然此时锚点会导致匹配失败，但非锚定正则表达式会继续尝试

23456789abcdef
23456789abcde
23456789abcd
...
2
                  (empty string due to the * quantifier)

如您所见，这一次在整个表达式无法匹配之前所进行的尝试次数是输入长度的二次方。

score 1 · Accepted Answer

\A 和 \Z 表示字符串的开头和结尾。因此，正则表达式更受限制，需要做的搜索更少。例如，如果您的文本中有换行符，则第二个正则表达式要快得多，因为它只搜索第一个正则表达式不断搜索的第一个新行

2 回答 2