Приемы микрооптимизации регулярных выражений

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

Условия тестирования

Все описанные приемы протестированы с использованием модуля timeit, предназначенного для измерения времени выполнения небольшого фрагмента кода.

  1. Интерпретатор — Python 3.5.2.
  2. Обработчик регулярных выражений — библиотека re.
  3. Все шаблоны предварительно компилируются с помощью re.compile().
  4. Количество запусков — 1000000.
  5. Количество повторов — 3.

Модуль timeit возвращает общее количество секунд, затраченное на вычисления, но поскольку фрагмент кода в эксперименте вычисляется 1000000 раз, то результат можно рассматривать как количество микросекунд, затраченных на выполнение одного теста.

Приемы микрооптимизации

1. Максимально конкретизируйте выражения

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

Например, необходимо выбрать все числа из следующей строки:

код: 1, размер: 42, рост: 172, возраст: 28

Если использовать выражение:

код: (.*), размер: (.*), рост: (.*), возраст: (.*).*

Поиск займет 1,78 микросекунды. Если использовать прием оптимизации, время выполнения составит 1,01 микросекунды, что на 43% быстрее:

код: ([^ ]*), размер: ([^ ]*), рост: ([^ ]*), возраст: ([^ ]*).*

2. Раскрывайте литеральные символы

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

Например, из строки артикулов:

НННА9091, НВГ2149, НННН023, ННП9071, ПНН2455

Мы бы хотели выбрать только те артикулы, которые содержат хотя бы одну букву Н. Если воспользоваться шаблоном Н+, поиск займет 2,01 микросекунды. Если шаблон преобразовать в НН*, совпадения будут найдены за 1,53 микросекунды, что на 24% быстрее.

3. Используйте якори и выносите их из-под чередования

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

Согласно теории, выражение ^.*ква отбрасывает совпадение быстрее, чем .*ква. На тестовой строке:

Санкт-Петербург|второй крупнейший город России

Выражение .*ква отработало за 4,1 микросекунды вместо 1,19 микросекунд с использованием выражения ^.*ква.

Также якори полезно выносить из-под чередования. Предпочтительнее ^(?:Мос|Лен), чем ^Мос|^Лен.

4. Имитируйте, где уместно, чередование с помощью звездочки (*)

Выражению с чередованием, такому как (A|B)*, есть альтернатива — A*(?:B+A*)*. Выглядит сложнее, но работает быстрее.

Предположим, необходимо выбрать серийные номера, которые включают цифры и любую из следующих букв: EAOUMPSLN. Проведем эксперимент с использованием строки:

SN20160101EAOUMPS6E2P2EA1OUML10165

Можно воспользоваться выражением:

(?:\d|[EAOUMPSLN])*

Оно отработает за 2,51 микросекунды. Но если применить микрооптимизацию:

\d*(?:[EAOUMPSLN]+\d*)*

Получим результат в 1,33 микросекунды, что на 47% быстрее.

5. Используйте ленивые квантификаторы

Ленивый режим работы квантификаторов означает «повторять минимальное количество раз». Используя это обстоятельство, можно значительно ускорить обработку регулярных выражений без изменения результата. Во многих выражениях жадный квантификатор * можно безопасно заменить на ленивый *?.

Например, в следующей строке необходимо найти количество документов, обработанных с ошибками:

Обработано документов: 2021  С ошибками: 10  Без ошибок: 2011  В очереди на удаление: 121

Вариант с жадным квантификатором отработал за 1,51 микросекунды:

.* С ошибками: (\d+) .*

Оптимизированный вариант с ленивым квантификатором:

.*?С ошибками: (\d+).*

Отработал за 1,42 микросекунды. Выигрыш — 6%.

6. Используйте режим обучения, если возможно

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

Строка-пример:

20 студийных и 6 концертных альбомов Scorpions выпустили в период с 1972 по 2015 год.

Регулярное выражение:

\d+\b(студийных|концертных)\b/S

Без режима обучения  — 2,45 микросекунды. C режимом обучения  — 2,37. Выигрыш составил 3,3%.

7. Избегайте повторной компиляции выражений

Если логика вашей программы предполагает использование одних и тех же регулярных выражений в нескольких местах, эффективно предварительно компилировать все регулярные выражения. Метод re.compile() компилирует выражения в объект RegexObject, обладающий методами для различных операций, таких как поиск вхождения шаблона или выполнение замены строки.

Я предпочитаю всегда работать со скомпилированными объектами.

8. Убедитесь, что вам действительно нужны регулярные выражения

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

Например, метод str.replace() всегда будет работать быстрее, чем re.sub().

Выводы

  • Расширяйте свой словарь. Не ограничивайтесь привычной группой операторов.
  • Не верьте слепо в универсальность одного и того же выражения: для определенного набора данных наверняка есть более эффективное выражение.
  • Исключайте то, что не ищете.
  • Используйте возможности предварительной компиляции.
  • Интересуйтесь разными способами достижения результата. Возможно, для решения вашей задачи существуют более простые и эффективные инструменты, чем регулярные выражения. Экспериментируйте, делайте измерения, выбирайте наиболее подходящий вариант.