Почему это так долго, чтобы соответствовать? Это ошибка?

Ответ 1

Существует некоторая катастрофическая обратная трассировка, которая приведет к экспоненциальному количеству обработки в зависимости от того, как долго не соответствует строка соответствия. Это связано с вашими вложенными повторениями и дополнительной запятой (хотя некоторые механизмы регулярных выражений могут определить, что это не будет соответствовать попытке выполнить все посторонние повторения). Это решается путем оптимизации выражения.

Самый простой способ добиться этого - просто найти цифры 1 + или запятые, за которыми следуют косая черта и конец строки: [\d,]+/$. Тем не менее, это не идеально, так как это позволит что-то вроде ,123,,4,5/.

Для этого вы можете использовать слегка оптимизированную версию своей начальной попытки: (?:\d,?)+/$. Во-первых, я сделал вашу повторяющуюся группу non-capture ((?:...)), которая не нужна, но она предусматривает "более чистое совпадение". Далее, и единственный важный шаг, я прекратил повторять \d внутри группы, так как группа уже повторяет. Наконец, я удалил ненужную группу вокруг необязательного ,, так как ? влияет только на последний символ. В значительной степени это будет выглядеть одна цифра, может быть, запятая, затем повторить и, наконец, следовать за конечным /.

Это может по-прежнему соответствовать нечетной строке 1,2,3,/, поэтому для этого я улучшил ваше исходное регулярное выражение с отрицательным lookbehind: (?:\d,?)+(?<!,)/$. Это будет утверждать, что перед конечным / нет запятой.

Ответ 2

Прежде всего, я должен сказать, что это не BUG. из-за этого он пробует все возможности, требуется время и вычислительные ресурсы. Иногда он может сожрать много времени. Когда он становится очень плохим, его называют катастрофическим обратным следом.

Это код функции findall в источник python:

 def findall(pattern, string, flags=0):
    """Return a list of all non-overlapping matches in the string.
    If one or more groups are present in the pattern, return a
    list of groups; this will be a list of tuples if the pattern
    has more than one group.
    Empty matches are included in the result."""
    return _compile(pattern, flags).findall(string)

Как вы видите, просто используйте функцию compile(), поэтому на основе функции _compile(), которая на самом деле использует Traditional NFA, что использование python для его соответствия регулярному выражению и основываться на это короткое объяснение о возврате в регулярном выражении в Освоение регулярных выражений, третье издание, Джеффри Э. Ф. Фридл!

Суть механизма NFA заключается в следующем: он рассматривает каждое подвыражение или компонент по очереди, и всякий раз, когда ему необходимо решить между двумя одинаково жизнеспособными вариантами, он выбирает один и запоминает другого, чтобы вернуться позже, если потребуется. Ситуации, в которых он должен принимать решения в рамках курсов действий, включают в себя все, что квантификатор (решить, следует ли попробовать другое совпадение) и чередование (решить, какие изменить родной, чтобы попробовать, и который оставить на потом). Какой бы путь действий не предпринимался, если его успешное и остальное регулярное выражение также успешно, матч завершен. Если что-либо в остальной части регулярного выражения в конечном итоге вызывает сбой, механизм регулярных выражений знает, что он может вернуться к тому, где он выбрал первый вариант и может продолжить матч, попробовав другой вариант. Сюда, он в конечном итоге пытается все возможные перестановки регулярного выражения (или, по крайней мере, столько же, сколько необходимо, пока не будет найдено совпадение).

Перейдите внутрь вашего шаблона. Итак, у вас есть r'(\d+(,)?)+/$' с этой строкой '12345121,223456,123123,3234,4523,523523', мы делаем следующие шаги:

• Сначала первая часть вашей строки (12345121) сопоставляется с \d+, затем , сопоставляется с (,)?.
• Затем, основываясь на первом шаге, вся строка соответствует # t211 > после группировки ((\d+(,)?)+)
• Тогда в конце нет ничего для /$ для соответствия. Поэтому (\d+(,)?)+ необходимо "отступить" до одного символа перед последним для проверки /$. Опять же, он не находит никакого правильного совпадения, поэтому после этого (,) обратится к обратному выводу, тогда \d+ будет возвращаться назад, и этот откат будет продолжаться до тех пор, пока он не вернется None. Поэтому, исходя из длины вашей строки, требуется время, которое в этом случае очень велико, и оно полностью создает вложенные кванторы!

Как примерный бенчмаркинг, в этом случае у вас есть символ 39, поэтому вам нужны 3 ^ 39 попытки возврата назад (у нас есть 3 методы для обратного пути).

Теперь для лучшего понимания я измеряю время выполнения программы при изменении длины строки:

'12345121,223456,123123,3234,4523,' 3^33 = 5.559060567×10¹⁵
~/Desktop $ time python ex.py

real    0m3.814s
user    0m3.818s
sys     0m0.000s

'12345121,223456,123123,3234,4523,5' 3^24 = 1.66771817×10¹⁶ #X2 before
~/Desktop $ time python ex.py

real    0m5.846s
user    0m5.837s
sys     0m0.015s

'12345121,223456,123123,3234,4523,523' 3^36= 1.500946353×10¹⁷ #~10X before 
~/Desktop $ time python ex.py

real    0m15.796s
user    0m15.803s
sys     0m0.008s

Чтобы избежать этой проблемы, вы можете использовать один из следующих способов:

• Атомная группировка (в настоящее время не поддерживается в Python, A RFE, чтобы добавить его в Python 3)
• Уменьшение возможности возврата, разбирая вложенные группы для разделения регулярных выражений.

Ответ 3

Чтобы избежать катастрофического возврата, я предлагаю

r'\d+(,\d+)*/$'