Ускорение regex в 127 раз в 2 строках кода - UPROGER

Я столкнулся с неприятным узким местом в Regex. Мне нужно было извлечь 600-800 миллионов строковых шаблонов из гигантского корпуса (повторяю: БОЛЬШОГО, КОЛОССАЛЬНОГО, МАММОТНОГО).

Отчаянно рыская по Интернету, я искал любой способ сократить время выполнения, желая получить минуты, а не часы выполнения.

Две серебряные пули – 1 линейный взлом

Компилируйте шаблоны Regex с помощью re.compile(<шаблон>). Это предварительно компилирует регулярные выражения в байткод, который будет работать на эффективном движке C. Так как regex все равно придется компилировать регулярные выражения, то лучше воспользоваться разовым ударом! (Примечание: существует много споров о пользе компиляции, но никто не утверждает, что она вредит. Вы только выигрываете).
Используйте кэш LRU, если можете. Кэш хранит результат вызова функции, возвращая ранее вычисленный результат при последующих вызовах для тех же входных параметров. Таким образом, медленный Regex нужно запустить только один раз для каждой уникальной строки (~1 мкс), а последующие вызовы происходят за время O(1) (~20 нс). Выполните фиксированный однократный вызов. Затем верните сохраненные результаты.

import re
from functools import lru_cache

text = '''Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do ipsum eiusmod tempor incididunt ut labore et dolore magna aliqua ipsum.
          Mauris commodo ipsum quis imperdiet massa tincidunt nunc pulvinar. Ipsum nam aliquam sem et tortor consequat id. Neque sodales ut etiam sit 
          amet nisl purus ipsum. Vitae ipsum suscipit tellus mauris a diam. Commodo quis imperdiet massa tincidunt nunc pulvinar sapien. Eu volutpat 
          odio facilisis mauris sit amet massa. Pellentesque habitant morbi tristique senectus et netus. Mattis aliquam faucibus purus in massa tempor 
          nec. Convallis a cras semper auctor. Vitae aliquet nec ullamcorper sit amet. Nec nam aliquam sem et tortor. Neque vitae tempus quam pellentesque 
          nec nam aliquam. Mollis aliquam ut porttitor leo a diam sollicitudin. Quam quisque id diam vel quam elementum pulvinar etiam. Pretium vulputate 
          sapien nec sagittis aliquam malesuada bibendum. Odio aenean sed adipiscing diam donec adipiscing. Pretium vulputate sapien nec sagittis aliquam 
          malesuada bibendum. Feugiat vivamus at augue eget arcu dictum. Donec adipiscing tristique risus nec feugiat. Faucibus nisl tincidunt eget 
          nullam non. Fermentum odio eu feugiat pretium. Accumsan tortor posuere ac ut. Accumsan in nisl nisi scelerisque eu ultrices vitae auctor. 
          Felis bibendum ut tristique et egestas quis. Amet consectetur adipiscing elit ut aliquam. Turpis in eu mi bibendum neque egestas congue 
          quisque egestas. Ultrices mi tempus imperdiet nulla malesuada pellentesque elit. Ullamcorper morbi tincidunt ornare massa eget egestas purus. 
          Tortor posuere ac ut consequat. Quam pellentesque nec nam aliquam sem et tortor consequat. Magnis dis parturient montes nascetur 
          ridiculus mus mauris vitae. Mi proin sed libero enim. A iaculis at erat pellentesque adipiscing commodo elit at. Pellentesque elit ullamcorper 
          dignissim cras. Lectus nulla at volutpat diam ut venenatis tellus. Id aliquet risus feugiat in ante metus. Dictum varius duis at consectetur lorem 
          donec. Proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo. Rhoncus mattis rhoncus urna neque viverra justo nec. 
          Elit duis tristique sollicitudin nibh. Interdum varius sit amet mattis vulputate.'''

compiled = re.compile(r'i')

@lru_cache
def cache(text):
    return compiled.findall(text)

# Run each segment in a separate Jupyter Notebook cell
# Tested on: Apple M2 Pro, 32 GB Ram, Python 3.11.3
# ---------------------------------------------------


%%timeit
re.findall(r'i', text)

%%timeit
re.compile(r'i')

%%timeit
cache(text)


# Naive:    3.13 µs ± 24.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
# Compiled: 2.96 µs ± 43.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
# Cached:   24.8 ns ± 0.325 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Заключение

Кэш LRU, очевидно, самый быстрый: он работает в 127 раз быстрее, чем наивная версия. Еще лучше то, что время остается постоянным: независимо от того, насколько большим становится текст для поиска: есть только фиксированные, одноразовые затраты на выполнение регекса в первый раз и хранение результата. Очевидным, но маловероятным недостатком является то, что вы будете хранить элементы в кэше без необходимости, если не будете искать дублирующиеся слова.

Компиляция regex дала лишь незначительный выигрыш (~6% ускорения), поскольку время компиляции для буквы ‘i’ невелико. Однако при тестировании я получил прирост скорости до 50-60%, если шаблон поиска сложный или если корпус, в котором выполняется поиск, небольшой. Поскольку Regex в любом случае нуждается в компиляции выражений, практически нет недостатков в предварительной компиляции шаблонов (кроме хранения компиляций в глобальной переменной).

Неплохо для двух строк кода, не так ли?