0

执行以下代码需要很长时间：

"Hello there, very best wishes, from Syria...".match(/^((?:, |[\w ]+)+)$/)

在执行以下操作时，花费的时间比以往少一点，但比十秒多一点！

"Hello there, best wishes, from Syria...".match(/^((?:, |[\w ]+)+)$/)

...然后它返回null

在我的 Ubuntu 12.04 64 位机器、Archlinux 32 位服务器和 Debian Wheezy 32 位服务器上进行了尝试，所有这些都运行节点 v0.10.18。

编辑：显然行为是从 V8 继承的，相同的代码使 Chrome 的控制台挂起，mongo shell（也使用 V8）也挂起！

4

2 回答 2

1

这个正则表达式是等效的并且运行速度很快：

/^([\w, ]+)$/

问题在于您的正则表达式，而不是 V8。其他引擎只是在尝试一段时间后报告没有匹配（这不一定是正确的结果），V8 尝试获得正确的结果，即使它需要很长时间。您需要注意如何编写正则表达式，它就像任何其他代码一样 - 它不能神奇地防止程序员错误。

于 2013-09-16T06:26:40.100 回答
1

我很确定这里发生的事情是灾难性的回溯。例如在我的机器上：

  • 对于“ Hello there, best wishes, from Syria...”中的 39 个字符，大约需要 13-14 秒。
  • “”中的 40 个字符Hello there, vbest wishes, from Syria...需要 27-28 秒。
  • " " 中的 41 个字符Hello there, vebest wishes, from Syria...需要 56 秒。

您可以看到所花费的时间呈指数增长。为了解释正则表达式引擎如何通过回溯匹配字符串，我将引用上面链接中的示例。它(x+x+)+y在字符串上应用正则表达式xxxxxxxxxxy：

让我们看看当您将此正则表达式应用于 xxxxxxxxxxy 时会发生什么。第一个 x+ 将匹配所有 10 个 x 字符。第二个 x+ 失败。第一个 x+ 然后回溯到 9 个匹配，第二个拾取剩余的 x。该组现已匹配一次。该组重复，但在第一个 x+ 处失败。由于重复一次就足够了，因此小组匹配。y 匹配 y 并找到整体匹配。正则表达式被声明为有效，代码被发送给客户，他的计算机爆炸了。几乎。

当主题字符串中缺少 y 时，上述正则表达式变得难看。当 y 失败时，正则表达式引擎回溯。该组有一个可以回溯到的迭代。第二个 x+ 只匹配一个 x，所以它不能回溯。但是第一个 x+ 可以放弃一个 x。第二个 x+ 立即匹配 xx。该组再次进行一次迭代，下一次失败，并且 y 失败。再次回溯，第二个 x+ 现在有一个回溯位置，减少自身以匹配 x。该小组尝试第二次迭代。第一个 x+ 匹配，但第二个被卡在字符串的末尾。再次回溯，该组第一次迭代中的第一个 x+ 将自身减少到 7 个字符。第二个 x+ 匹配 xxx。如果 y 失败，则第二个 x+ 减少为 xx，然后是 x。现在，该组可以匹配第二次迭代，每个 x+ 对应一个 x。但是这个 (7,1),(1,1) 组合也失败了。所以它去 (6,4) 然后是 (6,2)(1,1) 然后是 (6,1),(2,1) 然后是 (6,1),(1,2) 然后我认为你开始得到漂移。

请参阅Jeff 关于正则表达式性能的此页面，该页面使用相同的示例。故事的寓意：不要只匹配东西，改进正则表达式。嵌套重复运算符时，请绝对确保只有一种方法可以匹配相同的匹配项。对于我引用的示例xx+y效果更好。对于您的正则表达式，Esailija 给出的答案会更好/^([\w, ]+)$/

于 2013-09-16T08:51:05.560 回答