Почему поиск в регулярном выражении медленнее с захватом групп в Python?

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

>>> import timeit
>>> setup = '''
... import re
... '''   

#no capture group 
>>> print(timeit.timeit("re.search(r'hello|bye|ola|cheers','some say hello,some say bye, or ola or cheers!')", setup=setup))
0.922958850861

#with capture group
>>> print(timeit.timeit("re.search(r'(hello)|(bye)|(ola)|(cheers)','some say hello,some say bye, or ola or cheers!')", setup=setup))
1.44321084023

#no capture group
>>> print(timeit.timeit("re.search(r'hello|bye|ola|cheers','some say hello,some say bye, or ola or cheers!')", setup=setup))
0.913202047348

# capture group
>>> print(timeit.timeit("re.search(r'(hello)|(bye)|(ola)|(cheers)','some say hello,some say bye, or ola or cheers!')", setup=setup))
1.41544604301

Вопрос: Что приводит к значительному снижению производительности при использовании групп захвата?

Ответ 1

Ваши шаблоны отличаются только в группах захвата. Когда вы определяете группу захвата в шаблоне регулярного выражения и используете шаблон с re.search, результатом будет MatchObject. Каждый объект сопоставления будет содержать столько групп, сколько будет захвачено группами в шаблоне, даже если они пусты. Это накладные расходы для внутренних элементов re: добавление групп (списка) (распределение памяти и т.д.). Помните, что группы также содержат такие детали, как начальный и конечный индекс текста, который они соответствуют и более (см. MatchObject ссылка).

Ответ 2

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

Например, использование этого регулярного выражения (hello|bye|ola|cheers) или (hello)|(bye)|(ola)|(cheers) будет значительно сильнее, чем использование атомной группы или не захватывающей, например, (?:hello|bye|ola|cheers).

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

Я знаю, что вы отметили python, но подготовили онлайн-тест для javascript, чтобы показать, как захватываются и не захватываются группы в js-regex engine.

https://jsperf.com/capturing-groups-vs-non-capturing-groups