Эффективность и ресурсозатратность регулярных выражений
Здравствуйте. Посоветуйте пожалуйста литературу на тему того, насколько эффективны регулярные выражения как средство, какие ресурсы они потребляют и что с ними делать, чтобы выжать максимум эффективности, то есть оптимизировать, чтобы не перегружать оперативку устройства
Посоветуйте пожалуйста литературу на тему того, насколько эффективны регулярные выражения как средствоПосле этой фразы я подумал что он спрашивает про книги из разряда "Как убрать слова паразиты из лексикона" а потом я прочитал последнюю фразу
чтобы не перегружать оперативку устройстваИ нихера не понял о чём он просит.
Regex это из программирования, а с оперативкой у них все очень грустно на больших данных
Самое полезное, что можно прочитать про регулярные выражения, это вот эту вот цитату за авторством Jamie Zawinski:
Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems.
Можно распечатать и повесить на стену. Контекст цитаты — времена, когда регулярные выражения были на пике популярности, и Perl был в большом почёте. Тогда было написано совершенно лютое количество абсолютно нечитаемого и полного багов говнокода с монстроузными выражениями в несколько строчек длиной, который было проще выкинуть и переписать по-человечески, чем пытаться сопровождать.
Если у тебя действительно есть задача, где вроде бы неудобно писать обычный код (т.е. ты делаешь что-то сложнее, чем проверку в духе "а есть ли в строчке символ @"), и в то же самое время не пытаешься решить с помощью регулярных выражений то, для чего по-хорошему надо бы написать нормальный парсер, то:
1. Пиши.
2. Замеряй производительность.
Время выполнения может быть сложно-предсказуемым, и тяжело "угадать", какой случай может оказаться для библиотеки совсем ужасным, а какой будет работать быстро.
В целом есть куча бенчмарков, и можно посмотреть, какие библиотеки в целом обычно быстрые или в целом обычно медленные. Например все имплементации std::regex — это абсолютное беспросветное говнище, работающее раз так в 300 медленнее, чем надо (и это теперь не могут починить не ломая ABI, поэтому регулярные выражения из стандартной библиотеки C++ лучше просто никогда не трогать).
Например прикрепил табличку вот отсюда: https://github.com/HFTrader/regex-performance
Смотри, например, колонку rust_regex: в сотни раз быстрее std::regex почти везде, но работает совершенно чудовищно в одном конкретном случае, где все остальные справляются гораздо лучше.
Или pcre-jit — кажется, что в целом неплохо и без больших просадок, но иногда оказывается медленней rust_regex в несколько раз.
Я это к тому, что любая попытка угадывать производительность без измерений — очень плохая затея. Ну т.е. понятно, что если сделать выражение сильно сложнее, то наверное может быть будет медленней, но сложно сказать, на 5% будет медленней или в 100 раз.
Если тебе хочется предсказуемое поведение, и у тебя крайне мало мест, где ты хотел написать регексп, то возможно там лучше написать обычный код.
Спасибо, очень развернутый ответ, это круто
По производительности по скорости только один совет: пиши так, чтобы выражение работало за один проход (без возвратов).
Вот тут, например, несколько советов: https://www.loggly.com/blog/five-invaluable-techniques-to-improve-regex-performance/
Немного не понял это:
не перегружать оперативкуРазве они занимают много памяти? При компиляции у тебя получается эквивалентный автоматный (или КС-) код.
Если использовать дизьюнкцию, да. Но именно на больших данных. Под большими подразумеваю строки длинной больше 10^6 симвооов
А, ещё пиши скобочки «(...)» только если тебе нужен захват подвыражения. Если не нужен, лучше используй математические скобки «(?:...)».
Я пишу на шарпе, там есть два режима у regex'ов: компилируемый и динамический. Если выражение используется кучу раз, то лучше за предкомпилировать.