Почему так /? (.+) +Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXX?) Занимает так много времени?
Когда я запустил
/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX")
в Chrome или IE, требуется ~ 10 секунд. (Firefox может оценить его почти мгновенно.)
Почему так долго? (И почему/как Firefox может сделать это так быстро?)
(Конечно, я никогда не буду запускать это конкретное регулярное выражение, но я сталкиваюсь с аналогичной проблемой с URL-адресом regex в http://daringfireball.net/2010/07/improved_regex_for_matching_urls, и, похоже, сводятся к этому, т.е. есть определенные 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")
Ответы
Ответ 1
Как указано в thg435, это звучит как катастрофическое обратное отслеживание. Там отличная статья об этом, Регулярное соответствие выражению может быть простым и быстрым.
В нем описывается эффективный подход, известный как NOM Томпсон. Как уже отмечалось, это не поддерживает все функции современных регулярных выражений. Например, он не может делать обратные ссылки. Однако, как было предложено в статье:
"Несмотря на это, было бы разумно использовать имитацию Thompson NFA для большинство регулярных выражений, и только вывести назад, когда это необходимо. Особенно умная реализация могла бы объединить два, прибегая к отступлению только для размещения обратных ссылок".
Я подозреваю, что Firefox может это сделать.
