javascript - 你能解释一下为什么这些正则表达式很慢吗

Question

最近我在代码中发现了以下正则表达式。由于它正在检查的字符串非常大，因此它卡住了浏览器。运行一些实验，我使用以下代码测量了时间

var s = 'Lorem ipsum dolor sit amet, rhoncus nam sem feugiat, vel vel, viverra ultrices interdum. Volutpat ac congue. Lacinia sit donec quis facilisi, magna cubilia volutpat lectus fusce ligula quis, sit sed vivamus eget mauris quisque, aenean aenean nec litora litora massa, malesuada turpis pretium. Magnis metus nulla mauris dictum ligula, odio facilisis nullam laoreet. Aliquam tincidunt enim sit dolor mi. Duis malesuada pede, tortor consectetuer facilisis massa et leo vel. Eget fames tellus mi. Suscipit tincidunt fusce lacus convallis, ornare eu sed eu gravida interdum. Vivamus ipsum, maecenas penatibus, lacus posuere, eu cum, mauris ea libero elit. Libero blandit mattis mi sapien, iaculis wisi sit convallis, est in libero, elementum cras in a cum a vestibulum';

for (var i = 0; i < 3; i++) {
  s += s;
}

start = new Date().getTime();
s.match(/AAA/i)
stop = new Date().getTime();
console.log("AAA took " + (stop - start) + " ms")

start = new Date().getTime();
s.match(/BBB/i)
stop = new Date().getTime();
console.log("BBB took " + (stop - start) + " ms")

start = new Date().getTime();
s.match(/CCC/i)
stop = new Date().getTime();
console.log("CCC took " + (stop - start) + " ms")

start = new Date().getTime();
s.match(/.*(AAA|BBB|CCC).*/i)
stop = new Date().getTime();
console.log("Combined took " + (stop - start) + " ms")

上面的打印

AAA took 0 ms
BBB took 1 ms
CCC took 0 ms
Combined took 53 ms

您能否用通俗易懂的语言解释为什么这个正则表达式如此缓慢，而检查各个部分几乎不需要时间？ 是否有另一种编写单行正则表达式的方法来检查多个字符串的出现，从而更快地产生结果？

Answer 1

/AAA/i, /BBB/i, /CCC/i 不同于/.*(AAA| BBB|CCC).*/i 不仅在交替捕获组的使用上，而且在.* 模式中。

/.*(AAA|BBB|CCC).*/i 模式由于第一个 .* 是一个贪婪的点模式而减慢了匹配速度。它以下列方式工作:

• 它抓取它可以匹配的所有字符(除换行字符外的 0 个或多个 chsrs)，因此，基本上，它抓取整行
• 然后它必须匹配 AAA 或 BBB 或 CCC，因此回溯开始:引擎从匹配结束时产生一个字符并尝试匹配其中一种选择
• 如果备选项丢失，或者如果它们位于一个很长的字符串的开头，引擎将徒劳地尝试为捕获组匹配容纳字符串的一部分。

参见 this regex debugger具有可视化的回溯步骤。

因此，查找一行/字符串是否包含 3 个备选方案中的任何一个的最佳方法就是使用

/(?:AAA|BBB|CCC)/i

因为此正则表达式可以找到部分 匹配(它不需要像 Java 的 String#match() 中那样的完整字符串匹配)。

如果您需要在多行字符串中查找具有其中一种选择的行，最好逐行处理(例如，用 \n 分割)，然后是 。过滤器(x =>/(?:AAA|BBB|CCC)/i.test(x))。

注意 (?:...) 是一个非捕获组，它不会创建子匹配，并且由于引擎不必分配，因此开销较小用于捕获的额外内存。