Регулярные выражения (англ. regular expression или, кратко, regex) — это такое очень сильное колдунство, созданное для точной, филигранной работы с текстом. Как верный заправский ниндзя из популярных боевиков на вашей службе, хорошо составленное регулярное выражение искусно нашинкует текст на нужные кусочки. Но наспех и плохо составленные регулярные выражения подобны пьянице, который шатается, постоянно спотыкается о текст и кое-как добивается результата. Основной причиной мифической медлительности регэксов в подавляющем большинстве случаев является отнюдь не медленный движок, а именно неумело составленное выражение.

Эта история о том, как всего несколько символов могут так значительно повлиять на производительность.

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

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

В статье в качестве примера используются регулярные выражения из аналогичной англоязычной статьи и этот текст можно рассматривать как её вольный (очень) перевод.

Плохое и получше

Предлагаю следующую задачу, на примере которой мы рассмотрим производительность различных регэксов в шагах1)Некоторые шаги могут быть более затратны, чем другие, однако измерение производительности в шагах является хорошим показателем эффективности регулярного выражения относительно данного ввода, не вдаваясь в дебри бенчмарка.2)Тестирование проводится движком RegexBuddy.  (не миллисекундах), т.е. в том, сколько действий совершает сконструированный по нашей кальке автомат, чтобы обработать введённый текст. Текcтом для обработки будет некая строка из некоего лога (веб-сервера):

2014-08-26 app[web.1]: 50.0.134.125 - - [26/Aug/2014 00:27:41] "GET / HTTP/1.1" 200 14 0.0005

Из этой строки нам нужно достать с помощью регулярного выражения, например, значения app и web.1. Рассмотрим два регулярных выражения, оба из которых корректны и, в итоге, выполняют поставленную задачу.

.*\s(.*)\[(.*)\]:.*
[12]\d{3}-[01]\d-[0-3]\d\s(.*)\[(.*)\]:.*

Как думаете, какое из них эффективнее? Да, действительно второе, но попробуйте-ка угадать, насколько. Первое регулярное выражение обрабатывает строку за 2625 шагов, второе — за 635 шагов. Учитывая, что разные шаги могут выполняться за разное время, разница в производительности может достигать 42 раз!

Секрет успеха

Дело в том, что чем короче вы делаете своё регулярное выражение, чем больше обобщаете его, тем больше «простора для фантазии» вы даёте нижележащему автомату. Фактически, вы заставляете его перебирать намного, намного больше вариантов раскройки входной строки, чем нужно. Регулярное выражение должно быть как можно более конкретным и подробным, если даже оно становится очень длинным. Справедливо и обратное, обычно чем длиннее регулярное выражение, тем больше специальных символов и ограничителей оно содержит и тем быстрее и эффективнее оно будет в итоге. Кроме того, более специфичное регулярное выражение, кроме преимущества в скорости, ещё и снижает вероятность совпасть не с теми входными данными (ну ещё бы, да). В частности, старайтесь не использовать (в идеале — вообще никогда) оператор точки (.), вместо него лучше использовать перечисление символов, которые вы должны встретить (или наоборот, которых быть не должно).

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

Но самым королём падений производительности является оператор неограниченного захвата — *. По моим наблюдениям, именно его использование в сочетании с точкой приводит к самым тяжелым последствиям для скорости выполнения. Встречая его в середине выражения, автомат захватывает всю строку до конца, после чего начинает по необходимости (в «жадном» варианте) откатываться назад, что приводит к драматическому увеличению количество шагов из-за постоянного сканирования. И напротив, встретив «ленивый» (*?) захват там, где нужно поймать большую часть текста, например, до конца строки, автомат будет стараться захватывать аккуратно и по одному символу, стараясь сделать область захвата как можно меньше. Это опять приведёт к неразумному увеличению количества шагов и, опять, значительному падению скорости выполнения.

Лучшее регулярное выражение

Представляю вам лучшее регулярное выражение для заданной строки, составленное с учётом рекомендаций выше:

[12]\d{3}-[01]\d-[0-3]\d\s([^\s\[]*?)\[([^\]]*?)\]:.*

Как думаете, за сколько шагов оно выполнит поставленную задачу? 300? 200? Нет. Это регулярное выражение справляется с задачей за 41 шаг (в сравнении с 635 и 2625 шагами для предыдущих выражений). В итоге, разница в производительности между самым плохим и лучшим регулярным выражениями может быть просто чудовищна.

Особенно отметьте «ленивый» (*?) захват в середине выражения. Если заменить его на «жадный», количество шагов только от этого увеличится до 182, т. е. в 4,5 раза!

Мораль истории

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

Используйте все доступные инструменты регулярных выражений в нужном месте и будьте как можно более точны и подробны в описании и вы определённо станете мастерами кунг-фу регулярных выражений.

comments powered by HyperComments

Заметки   [ + ]

1. Некоторые шаги могут быть более затратны, чем другие, однако измерение производительности в шагах является хорошим показателем эффективности регулярного выражения относительно данного ввода, не вдаваясь в дебри бенчмарка.
2. Тестирование проводится движком RegexBuddy.