Регулярное выражение в модуле Python, которое ищет символ звездочки, работает очень медленно

Question

Моя рабочая среда :

OS: Windows 10 (64 bits)
RAM: 32 GB
Processor: Intel(R) Xeon(R) CPU E3-1240 v5 @ 3.50 GHz
Python version: 3.7.4 (64 bits)

Описание проблемы :

Я работаю над спокойным файлом журнала API. Пользователи этого API могут указать variableName:value в URL-адресе своих запросов, и на основе имени переменной и указанного значения поисковая система, стоящая за этим API, вернет результат. Также существует функция подстановочных знаков, позволяющая создавать запросы с использованием регулярных выражений, которые могут иметь одну из следующих форм:

variableName:va*
variableName:*lue
variableName:*alu*
variableName:*

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

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

Для целей этого анализа, Я разработал модуль Python со следующим регулярным выражением:

regexp_wildcard_asterisk = r"".join(
    [
        r"[a-zA-Z][a-zA-Z0-9]*([:]|%3A)",
        r"(([*]|%2A)|[^=*]+([*]|%2A)|([*]|%2A)[^=*]+|",
        r"([*]|%2A)[^=*]+([*]|%2A))"
    ]
)
regexp_wildcard_asterisk_prog = re.compile(
    regexp_wildcard_asterisk, re.IGNORECASE
)

Учитывая, что запросы являются действительными URL-адресами http, поэтому в приведенном выше регулярном выражении вы можете увидеть% 3A и% 2A, потому что в зависимости от кодировка на стороне клиента : и * также может быть закодирована как %3A и %2A соответственно.

Тогда все, что мне нужно сделать, это прочитать файл журнала построчно, внутри al oop и чтобы проверить, есть ли совпадение:

with open(
        src_file,
        "r",
        encoding="UTF-8"
) as srcfile_desc:

    csv_reader = csv.reader(srcfile_desc, delimiter="|")

    wildcard_asterisk_func_counter = 0

    for tokens in csv_reader:

        # The pattern matching is done on the 5th colonne of each 
        # line, that's why I've written tokens[4]
        if (regexp_wildcard_asterisk_prog.search(tokens[4])):
            wildcard_asterisk_func_counter += 1

Ну, это работает, но очень медленно! Хотя я должен признать, что иногда мой файлы журнала довольно большие, но все же размер файла не объясняет очень долгое время выполнения этой программы. В последний раз я запускал указанную выше программу в файле журнала всего с 890 строками и примерно 240 000 символов в каждой строке (всего несколько строк с 1 100 000 символов). Это заняло более 24 часов, и, когда я проверил, он все еще работал.

Теперь я знаю, что регулярные выражения действительно могут повлиять на производительность, но я провел сопоставление с образцом в других файлах журналов API с миллионами строк, а иногда и с миллионами символов в каждой строке, ища другие символы например, ?, [, ], {, }, и время выполнения никогда не превышало нескольких часов. Поэтому я подумал, что, возможно, есть какая-то ошибка в определении моего регулярного выражения, ищущего звездочку.

Читая мой код, не могли бы вы сказать мне, где, по вашему мнению, я допустил ошибку (или ошибки)?

Answer 1

Самый быстрый способ, который я нашел:

^.*\w+(?::|%3A)[^=*]*?\* 

Демо и объяснение (3 совпадения / 83 шага / 2 мс)

для сравнения с вашим тот же пример текста,

Демонстрация и объяснение (22 совпадения / 476 шагов / 4 мс)

Answer 2

Я обновил регулярное выражение, чтобы удалить группы захвата и не делать ничего, что могло бы попытаться выполнить поиск за пределами границ (в любом случае я ищу только отдельные строки). Я также использую регулярное выражение, которое ищет минимальное совпадение, которое распознает запрос с подстановочными знаками. Я дважды рассчитал свой код, используя регулярное выражение OP и приведенное ниже, и не обнаружил заметной разницы для этих 4 тестовых случаев. Я удалил флаг re.IGNORECASE, поскольку он не служил какой-либо полезной цели.

Я пробовал разные варианты сопоставления нуля или более символов, которые не были ни новой строкой, ни одним из символов звездочки (* или %3A ), и не было заметных изменений времени.

import re

# matches enough of the query to detect whether there was a wildcard:
regexp_wildcard_asterisk = r"""(?x) # Verbose mode
[a-zA-Z][a-zA-Z0-9]+    # Match variable
(?::|%3A)               # Match ':'
(?:(?!\*|%2A).)*        # Match zero or more non-'*' non-newline characters
(?:\*|%2A)              # Match '*'
"""

regexp_wildcard_asterisk_prog = re.compile(
    regexp_wildcard_asterisk
)

lines = [
    'variableName:va*',
    'variableName:*lue',
    'variableName:*alu*',
    'variableName:*', # 1000 lines of these
]

from time import time
t1 = time()
for _ in range(300):
    wildcard_asterisk_func_counter = 0
    for line in lines:
        if (regexp_wildcard_asterisk_prog.search(line)):
                wildcard_asterisk_func_counter += 1
t2 = time()
print(t2 - t1)

См. демонстрацию Regex