为什么/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"）需要这么长时间？ [英] Why does /^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX") take so long?

问题描述

当我跑步时

/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX")

在Chrome或IE中，完成需要约10秒钟。 （Firefox几乎可以立即对其进行评估。）

in Chrome or IE, it takes ~10 seconds to complete. (Firefox is able to evaluate it almost instantly.)

为什么需要这么长时间？ （以及为什么Firefox如何能够如此快速地完成它？）

Why does it take so long? (And why/how is Firefox able to do it so quickly?)

（当然，我从来没有运行过这个特殊的正则表达式，但是我打的是类似的在 http://daringfireball.net/2010/07/improved_regex_for_matching_urls 上使用网址正则表达式的问题，它似乎归结为这个，即有某些URL会导致浏览器锁定）

(Of course, I'd never run this particular regex, but I'm hitting a similar issue with the URL regex at http://daringfireball.net/2010/07/improved_regex_for_matching_urls and it seems to boil down to this, i.e. there are certain URLs which will cause the browser to lock up)

例如：

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»""‘’]))/i;
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA")

推荐答案

如thg435所示，它听起来像灾难性的回溯。有一篇很好的文章，正则表达式匹配可以简单快速。

As indicated by thg435, it sounds like catastrophic back-tracking. There's an excellent article on this, Regular Expression Matching Can Be Simple And Fast.

它描述了一种称为Thompson NFA的有效方法。但是，如上所述，这并不支持现代正则表达式的所有功能。例如，它无法进行反向引用。但是，正如文章中所建议的那样：

It describes an efficient approach known as Thompson NFA. As noted, though, this does not support all features of modern regexes. For instance, it can't do backreferences. However, as suggested in the article:

即便如此，使用Thompson的NFA模拟对于
最常规也是合理的表达式，只有在需要
时才会出现回溯。一个特别聪明的实现可以将两个结合起来，
只需要回溯以适应后向引用。

"Even so, it would be reasonable to use Thompson's NFA simulation for most regular expressions, and only bring out backtracking when it is needed. A particularly clever implementation could combine the two, resorting to backtracking only to accommodate the backreferences."

我怀疑Firefox可能会这样做。

I suspect Firefox may be doing this.

这篇关于为什么/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"）需要这么长时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！