正则表达式性能问题

本文关键字：问题 性能 正则表达式 | 更新日期: 2023-09-27 18:31:14

我们在以下正则表达式方面遇到了问题：

(.*?)'|'*'|([0-9]+)'*'|'*(.*?)

它应该匹配以下内容：|*25 *|

我们正在使用.Net Framework 4 RegEx类，代码如下：

string expression = "(.*?)" + 
       Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
       "([0-9]+)" + 
       Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END) + 
       "(.*?)";
Regex r = new Regex(expression);
r.Matches(contentText)
对于

40.000 个字符的文本，花费的时间太长（例如 60 秒）。

但是对于 180.000 的文本，速度非常可以接受（3 秒或更短）

文本

之间的唯一区别是第一个文本（慢文本）它都包含在一行中，没有换行符。这会是一个问题吗？这会影响性能？

谢谢

正则表达式性能问题

@David Gorsline的解决方案（来自评论）是正确的：

string expression =
    Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
    "([0-9]+)" + 
    Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END);

具体来说，是一开始的(.*?)在帮你。 它所做的是接管正则表达式引擎自己应该做的事情 - 扫描下一个正则表达式可以匹配的地方 - 并且效率低得多。 在每个位置，(.*?)有效地执行前瞻，以确定正则表达式的下一部分是否可以匹配，并且只有在失败时，它才会继续使用下一个字符。

但即使你使用了更有效的东西，比如[^|]*，你仍然会减慢它的速度。 但是，忽略该部分，正则表达式引擎可以扫描正则表达式的第一个常量部分，可能使用Boyer-Moore或Knuth-Morris-Pratt等算法。 所以不要担心你想要匹配的位周围有什么;只需告诉正则表达式引擎您正在寻找什么并摆脱它。

另一方面，尾随(.*?)几乎没有影响，因为它从来没有真正做任何事情。 ?让.*变得不情愿，那么如何才能让它继续消耗下一个角色呢？ 只有当正则表达式中有一些东西迫使它这样做时，它才会这样做。 例如，foo.*?bar消耗从下一个"foo"到下一个"bar"的所有内容，但一旦消耗"foo"，foo.*?就会停止。 将一个不情愿的量词作为正则表达式中的最后一件事是没有意义的。

您已经回答了您的问题：问题是.无法匹配换行符（默认情况下不匹配），这会导致许多失败的尝试 - 几乎 40000 个字符字符串的每个位置都有一个。
在长但单行的文件上，引擎可以在文件的单次传递中匹配模式（假设存在成功的匹配 - 如果没有，我怀疑需要很长时间才能失败......
在较短的文件中，有很多行，引擎会尝试从第一个字符开始匹配。它.*?匹配直到第一行的末尾（这是一个惰性匹配，所以正在发生更多的事情，但让我们忽略它），并失败。现在，它再次从第二个字符统计，而不是第二行！这甚至在匹配数字之前就会导致 n² 复杂性。

一个简单的解决方案是使.匹配换行符：

Regex r = new Regex(expression, RegexOptions.Singleline);

您还可以确保使用绝对开始和结束锚点从头到尾匹配，'A和'z：

string expression = "''A(.*?)" + 
   Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
   "([0-9]+)" + 
   Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END) + 
   "(.*?)''z";

另一个注意事项：正如大卫在评论中建议的那样，'|'*'|([0-9]+)'*'|'*应该足够好。即使您需要在比赛前后"捕获"所有文本，您也可以使用比赛位置轻松获取它。

相关文章：