11

私が走るとき

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

ChromeまたはIEでは、完了するまでに最大10秒かかります。（Firefoxはほぼ瞬時に評価できます。）

なぜそんなに時間がかかるのですか？（そして、なぜ/どのようにFirefoxがこれほど迅速にそれを行うことができるのですか？）

（もちろん、私はこの特定の正規表現を実行したことはありませんが、http： //daringfireball.net/2010/07/improved_regex_for_matching_urlsのURL正規表現で同様の問題が発生しており、要約すると、ブラウザをロックアップさせる特定のURLです）

例えば：

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")
4

1 に答える 1

8

thg435 で示されているように、壊滅的なバックトラッキングのように聞こえます。これについては、 Regular Expression Matching Can Be Simple And Fastという優れた記事があります。

これは、トンプソン NFA として知られる効率的なアプローチについて説明しています。ただし、前述のとおり、これは最新の正規表現のすべての機能をサポートしているわけではありません。たとえば、後方参照はできません。ただし、記事で提案されているように：

「それでも、ほとんどの正規表現に Thompson の NFA シミュレーションを使用し、必要な場合にのみバックトラッキングを行うのが合理的です。特に巧妙な実装では、2 つを組み合わせて、後方参照に対応するためだけにバックトラッキングに頼ることができます。」

Firefoxがこれを行っているのではないかと思います。

于 2012-04-18T21:29:58.690 に答える