Регулярные выражения в Python неожиданно замедляются

Рассмотрим этот код Python:

import timeit
import re

def one():
        any(s in mystring for s in ('foo', 'bar', 'hello'))

r = re.compile('(foo|bar|hello)')
def two():
        r.search(mystring)


mystring="hello"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])
mystring="goodbye"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])

В принципе, я сравниваю два способа проверить наличие одной из нескольких подстрок в большой строке.

То, что я получаю здесь (Python 3.2.3), является следующим:

[0.36678314208984375, 0.03450202941894531]
[0.6672089099884033, 3.7519450187683105]

В первом случае регулярное выражение легко побеждает выражение any - регулярное выражение сразу находит подстроку, а any должно проверять всю строку пару раз, прежде чем оно попадет в правильную подстроку.

Но что происходит во втором примере? В случае, когда подстрока отсутствует, регулярное выражение на удивление медленное! Это меня удивляет, так как теоретически регулярное выражение должно переходить только через строку, а выражение any должно пройти по строке 3 раза. Что здесь не так? Есть ли проблема с моим регулярным выражением или регулярные выражения Python просто замедляются в этом случае?

Ответ 1

Примечание для будущих читателей

Я думаю, правильный ответ заключается в том, что алгоритмы обработки строк Python действительно оптимизированы для этого случая, а модуль re на самом деле немного медленнее. То, что я написал ниже, верно, но, вероятно, не относится к простым регулярным выражениям, которые у меня есть в вопросе.

Оригинальный ответ

По-видимому, это не случайная случайность - модуль Python re действительно медленнее. Похоже, что он использует рекурсивный подход к обратному отслеживанию, когда ему не удается найти совпадение, в отличие от построения DFA и моделирования его.

Он использует подход backtracking, даже если в регулярном выражении нет обратных ссылок!

Это означает, что в худшем случае регулярные выражения Python принимают экспоненциальное, а не линейное время!

Это очень подробный документ, описывающий проблему: http://swtch.com/~rsc/regexp/regexp1.html

Я думаю, что этот график ближе к концу суммирует его кратко:

Ответ 2

Моя коллега нашла библиотеку re2 (https://code.google.com/p/re2/)? Существует оболочка python. Это немного, чтобы установить на некоторых системах.

У меня была такая же проблема с некоторыми сложными регулярными выражениями и длинными строками - re2 значительно ускорило время обработки - от секунд до миллисекунды.

Ответ 3

Причина, по которой регулярное выражение настолько медленное, состоит в том, что оно не только должно проходить через всю строку, но и должно иметь несколько вычислений для каждого символа.

Первый просто делает это:

Does f match h? No.
Does b match h? No.
Does h match h? Yes.
Does e match e? Yes.
Does l match l? Yes.
Does l match l? Yes.
Does o match o? Yes.
Done. Match found.

Вторая делает это:

Does f match g? No.
Does b match g? No.
Does h match g? No.
Does f match o? No.
Does b match o? No.
Does h match o? No.
Does f match o? No.
Does b match o? No.
Does h match o? No.
Does f match d? No.
Does b match d? No.
Does h match d? No.
Does f match b? No.
Does b match b? Yes.
Does a match y? No.
Does h match b? No.
Does f match y? No.
Does b match y? No.
Does h match y? No.
Does f match e? No.
Does b match e? No.
Does h match e? No.
... 999 more times ...
Done. No match found.

Я могу только рассуждать о различии между any и regex, но я предполагаю, что регулярное выражение работает медленнее, главным образом потому, что оно работает в очень сложном движке, как эффективная, как конкретная реализация (in).

В первой строке регулярное выражение найдет совпадение почти мгновенно, а any должно пройти цикл дважды, прежде чем что-либо найти.

Во второй строке, однако, any выполняет по существу те же шаги, что и регулярное выражение, но в другом порядке. Это указывает на то, что решение any выполняется быстрее, вероятно, потому, что оно проще.

Конкретный код более эффективен, чем общий код. Любые знания о проблеме можно использовать для оптимизации решения. Простой код предпочтительнее сложного кода.. По существу, регулярное выражение выполняется быстрее, когда шаблон будет находиться рядом с началом строки, но in выполняется быстрее, когда шаблон находится рядом с концом строки или не найден на всех.

Отказ от ответственности: я не знаю Python. Я знаю алгоритмы.

Ответ 4

У вас есть регулярное выражение, состоящее из трех регулярных выражений. Как вы думаете, что работает, если регулярное выражение не проверяет это три раза?:-) Там нет волшебства в вычислениях, вам все равно придется сделать три проверки.

Но regexp будет делать каждый три символа теста по символу, а метод "one()" проверяет всю строку для одного соответствия, прежде чем переходить на следующую.

В первом случае регулярное выражение намного быстрее, потому что вы проверяете строку, которая будет соответствовать последнему. Это означает, что one() нужно сначала просмотреть всю строку для "foo", затем для "bar", а затем для "hello", где она совпадает. Сначала перенесите "привет", а одно() и два() имеют почти такую же скорость, что и первое совпадение, выполненное в обоих случаях.

Regexps - это гораздо более сложные тесты, чем "in", поэтому я ожидаю, что он будет медленнее. Я подозреваю, что эта сложность сильно возрастает, когда вы используете "|", но я не читал источник для библиотеки regexp, так что я знаю.: -)