Python, самый быстрый способ перебора регулярных выражений, но останавливаться на первом совпадении

У меня есть функция, которая возвращает True, если строка соответствует хотя бы одному регулярное выражение в списке и False в противном случае. Функция называется достаточно часто, что производительность является проблемой.

При запуске через cProfile функция тратит около 65% его время делает матчи и 35% времени перебирает список.

Я бы подумал, что есть способ использовать map() или что-то, но я не могу подумайте о способе остановить его повторение после того, как он найдет совпадение.

Есть ли способ сделать функцию быстрее, все еще возвращая ее при поиске первого матча?

def matches_pattern(str, patterns):
    for pattern in patterns:
        if pattern.match(str):
            return True
    return False

Ответ 1

Первое, что приходит на ум, - это нажать цикл на сторону C, используя выражение генератора:

def matches_pattern(s, patterns):
    return any(p.match(s) for p in patterns)

Возможно, вам даже не нужна отдельная функция для этого.

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

def matches_pattern(s, patterns):
    return re.match('|'.join('(?:%s)' % p for p in patterns), s)

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

Вы также можете просмотреть общий совет для отладки регулярных выражений в Python. Это также может помочь найти возможности для оптимизации.

ОБНОВЛЕНИЕ: Мне было любопытно и написал небольшой ориентир:

import timeit

setup = """
import re
patterns = [".*abc", "123.*", "ab.*", "foo.*bar", "11010.*", "1[^o]*"]*10
strings = ["asdabc", "123awd2", "abasdae23", "fooasdabar", "111", "11010100101", "xxxx", "eeeeee", "dddddddddddddd", "ffffff"]*10
compiled_patterns = list(map(re.compile, patterns))

def matches_pattern(str, patterns):
    for pattern in patterns:
        if pattern.match(str):
            return True
    return False

def test0():
    for s in strings:
        matches_pattern(s, compiled_patterns)

def test1():
    for s in strings:
        any(p.match(s) for p in compiled_patterns)

def test2():
    for s in strings:
        re.match('|'.join('(?:%s)' % p for p in patterns), s)

def test3():
    r = re.compile('|'.join('(?:%s)' % p for p in patterns))
    for s in strings:
        r.match(s)
"""

import sys
print(timeit.timeit("test0()", setup=setup, number=1000))
print(timeit.timeit("test1()", setup=setup, number=1000))
print(timeit.timeit("test2()", setup=setup, number=1000))
print(timeit.timeit("test3()", setup=setup, number=1000))

Выход на моей машине:

1.4120500087738037
1.662621021270752
4.729579925537109
0.1489570140838623

Итак, any, похоже, не быстрее вашего первоначального подхода. Динамическое создание динамического выражения также не очень быстро. Но если вам удастся создать регулярное выражение и использовать его несколько раз, это может привести к повышению производительности. Вы также можете адаптировать этот тест для тестирования некоторых других вариантов:)

Ответ 2

Способ сделать это быстрее всего состоит в том, чтобы объединить все регулярные выражения в один с "|" между ними, а затем сделать один вызов совпадения регулярных выражений. Кроме того, вам нужно будет скомпилировать его один раз, чтобы быть уверенным, что вы избегаете повторной компиляции регулярных выражений.

Например:

def matches_pattern(s, pats):
    pat = "|".join("(%s)" % p for p in pats)
    return bool(re.match(pat, s))

Это для pats как строки, а не скомпилированные шаблоны. Если вы действительно только скомпилировали регулярные выражения, то:

def matches_pattern(s, pats):
    pat = "|".join("(%s)" % p.pattern for p in pats)
    return bool(re.match(pat, s))

Ответ 3

Добавляя к превосходным ответам выше, убедитесь, что вы сравниваете вывод re.match с None:

>>> timeit('None is None')
0.03676295280456543
>>> timeit('bool(None)')
0.1125330924987793
>>> timeit('re.match("a","abc") is None', 'import re')
1.0200879573822021
>>> timeit('bool(re.match("a","abc"))', 'import re')
1.134294033050537