Общие советы по составлению оптимальных регулярных выражений

    Регулярные выражения — неотъемлемая часть любого инструмента обработки данных.
    Логично, что в различных вариациях поддерживается различный синтаксис и различный функционал.
    Не смотря на это принципы работы самих регулярных выражений, машины регулярных выражений и базовые установки оптимизации практически едины.
    Где-то на просторах сети видел совершенно глупое заявление, что “регулярные выражения не приспособлены для решения нерегулярных данных” или нечто похожее. Полнейшая ерунда.

    Другое дело, что чем более интеллектуален шаблон поиска, тем сильнее машина регулярных выражений “напрягается”, дабы “объяснить” тексту, что от него в итоге требуется.
    Кстати, в классической книжке Фридла есть целая глава по оптимизации регулярных выражений. Важная ее часть — сама структура главы. Сначала рассматривается общий принцип оптимизации самих по себе выражений, а далее — оптимизация применительно к языкам программирования. Т.е. в оптимизации есть несколько стадий, не следует этого забывать.

    Для самих выражений есть несколько очевидных правил:
    1. Литеральный поиск самый быстрый — /aa/ обычно быстрее /а{2}/ или /[a]{2}/
    2. Поиск данных неопределенной длинны расточителен (во всяком случае для HKA-версий). Если Вам известен размер данных — укажите его хотя-бы примерно. /\w{3,500}/ быстрее /\w+/
    3. Наличие скобок (и несохраняющих! тоже) замедляет поиск. Если Вам не нужна информация — никогда не заключайте сегмент в сохраняющие скобки и пытайтесь переписать шаблон для отказа и от несохраняющих. Требование иногда невозможное, но стоит иметь его ввиду. Кроме того, не стоит пытаться “помочь” машине регулярных выражений с поиском конструкциями типа /(?:.*)one/, это только запутает автомат.
    4. Наличие исполняемого кода в “теле” самого выражения или в “теле” выражения для подстановки — разорительны. Используйте эту технику только в том случае, если Вы абсолютно убеждены, что другого выхода нет. Положим, идея “оседлать” неявный цикл выражения с ключом /g — зачастую(JavaScript — точно) пустая трата времени. “Нативные” циклы базового языка вероятнее всего будут на порядок-другой быстрее, чем вход-выход в процессе работы машины регулярного выражения.
    5. Выражения “замены” гораздо медленнее выражений поиска. В случае замены больших кусков текста имеет смысл подумать об альтернативном варианте с созданием новой версии текста. Может оказаться сложнореализуемым, но имеет смысл хотя бы задуматься о такой проблеме.
    6. Альтернативы замедляют поиск, альтернативы неизвестной длины настолько его замедляют, что иногда следует попробовать искать в несколько проходов безальтернативной конструкцией.
    7. Не забывайте пользоваться “якорями” начала /^/ и конца /$/ строки, если они могут быть применены в Вашем случае.
    8. Конструкции “заглядывания” назад и вперед обычно плохо сказываются на скорости. Попробуйте сформулировать шаблон точнее.
    9. Не пользуйтесь конструкциями $` и $’ (в JavaScript это RegExp.leftContext и RegExp.rightContext) — они могут сильно замедлить разбор.

    Основная идея — чем точнее вы объясняете, что именно нужно снять с верхней полки, тем меньше времени простоите перед прилавком. Не забывайте, лучше услышать сразу “пивом не торгуем” в булочной, чем 20 минут гонять продавца по всем стеллажам с просьбой “дайте мне такую хрень, не знаю как объяснить…” с тем же результатом. Чем ближе Ваш шаблон будет к созданию бинарного решения ЕСТЬ-НЕТ при его применении к тексту ЦЕЛИКОМ, тем лучше.
    В отношении частной оптимизации к конкретному языку программирования — все до неприличия непросто. Старайтесь ориентироваться на минимализацию возвращаемых данных. К примеру — нет смысла выполнять оператор замены, дабы выяснить совпадет ли шаблон. Да и само совпадение можно попробовать выяснить наименее “говорливым” оператором. Положим, в JavaScript есть оператор .test который сообщает только “совпало-не совпало”. Если это единственное, что Вас интересует — используйте его, а не .match или .exec. Полагаю, что особенно ценен этот совет может оказаться для пользователей PHP с его бестиарием regex-like операторов.
    Данная заметка не претендует ни на что, кроме как заставить читателя(да и писателя тоже) задуматься о процессе оптимизации такого мощного инструмента, как регулярные выражения.
    Задумались? Перечитайте Фридла с его “Регулярными выражениями”, а если такой книжки еще нет — немедля прикупите!
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 26

      0
      Пардон, а что такое gerex в PHP?
        +2
        Думаю автор хотел сказать regex =)
          +1
          Опечатка вышла, однако.
          0
          1 пункт оптимизаторы обычно правят сами :)
            +4
            Главное забыто — жадные модификаторы, особенно .*
            Backtracking после них — может съесть бОльшую часть времени выполнения регулярного выражения. Лучше использовать либо negated character classes [^abc] (если известна граница группы), либо попробовать переписать логику на работе с не-жадной версией .*?
              0
              Готов обсудить Ваше предложение подробнее, как только Вы явно озвучите, что именно Вы имеете ввиду под определением «Backtracking». Не хотелось бы дискутировать о преимуществе арбузов над помидорами.
              В общем же виде сама модель НКА, применяемого практически во всех продуктах (за редким исключением), формализуется как «поиск самого длинного совпадения, ближнего к левому краю», т.е. механизм внутреннеоптимизирован.
              И как пишет Фридл (стр.314)
              Если Вам абсолютно ничего не известно о целевых данных, выбирайте максимальный квантификатор, поскольку он обычно оптимизируется чуть лучше минимального, особенно если следующий элемент регулярного выражения не позволяет использовать оптимизацию по символу, следующему за минимальным квантификатором.

              и ранее (стр.304)
              Проверка символа, следующего за минимальным квантификатором.
              При использовании минимальных квантификаторов в конструкциях вида /"(.*?)"/ механизм должен постоянно переходить между проверками совпадения квантифицированной конструкции (точки) и тем, что следует после нее ("). По этой и по ряду других причин минимальные квантификаторы обычно работают гораздо медленнее максимальных.<...> Если минимальный квантификатор заключен в сохраняющие круглые скобки, управление приходится постоянно передавать внутрь скобок и за их пределы, что приводит к дополнительным затратам времени.

              Я бы рекомендовал использовать (+) а не (*) в качестве квантификатора всегда, когда это возможно.
              Что до negated character classes [^abc] — да, очень эффективная техника, но с большими ограничениями.
                0
                Backtracking — механизм «возврата» жадным квалификатором символов входной строки, если текущее (т.е. изначально — до конца строки) его значение не позволяет выполнится всему регулярному выражению. Это иногда удобно — если нам нужен текст между первым < и последним >, то можно написать просто /<.*>/ — и вернётся всё, что нужно. Но чаще бывает другая ситуация — нам нужен какой-то небольшой участок входного текста — первый тег, к примеру. Тогда жадность создаст большие проблемы — съев всю строку.

                Жадные модификаторы плохи, когда им приходится возвращать обратно регулярному выражению много, и хороши, когда возвращать почти ничего не придётся. Это правило позволяет определить, когда их стоит использовать, а когда — нет.

                По поводу + — иногда надо разрешать пустые участки — к примеру, bb-теги [b][/b] — валидный тег, но внутри ничего нет. Или если во входном тексте пробел — необязательный разделитель ввода.

                Низкая производительность не-жадных модификаторов — да, выход из сохраняющих скобок дорог. Но вот возьмём классику — выделить из текста строку между двумя кавычками, с учётом экранирование кавычки слешем. У меня есть пример из «Mastering regular expressions» с использованием жадного варианта [^..]* и мой вариант, через .*? и negative look-behind. Второй — быстрее) Могу привести обе регулярки.
                  0
                  На регулярки было бы интересно взглянуть. В идеале и на хронометраж.
                    0
                    Из Mastering RE — "([^"\\]*(?:\\.[^"\\]*)*)"
                    Lazy + negative lb — "(.*?)"(?<! \\")

                    paste.org.ru/?374ll0

                              Rate    std   lazy   plus unroll lazy_2
                    std    14162/s     --   -21%   -62%   -70%   -78%
                    lazy   17921/s    27%     --   -52%   -62%   -72%
                    plus   37121/s   162%   107%     --   -20%   -43%
                    unroll 46690/s   230%   161%    26%     --   -28%
                    lazy_2 64631/s   356%   261%    74%    38%     --
                    
                      0
                      извините, но выражение по вашей ссылке на мой субъективный взгляд некорректны :)
                      1) std
                      сохраняющие скобки захватывают не то что надо, +атомарная группировка и квантификатор должны немного улучшить дело :)
                      "((?>[^"\\]*|\\.)*)" — так мне кажется корректней. По идее и быстрее. Извините, щас проверить не могу, нет ничего под рукой…
                      2) lazy
                      "(.*?)(?<!\\)"
                      Как я понял он некорректен при выражении вида \\"
                      У lazy_2 та же проблема.
                      3) plus
                      не съест найдёт пустый строки ""

                      Получается только unroll валидный для отловки текста между двумя кавычками :) В нём вроде как всё выглядит нормально. По крайней мере на первый взгляд :)
                      Щас будем думать как и его улучшить. :)

                        0
                        На примере с \\" споткнулся только lazy: paste.org.ru/?i2g88w (или есть более сложный пример?)

                        Поменяв $str на "" — съели все. ЧЯДНТ?)

                        Насколько я помню этот скрипт — std, plus, unroll все из Mastering RE. Ещё, если перл 5.10 — можно попробовать greedy, но у меня нет его под рукой.
                          0
                          $str = ' cb «zero \» one\\\\" two \\\\\" free \\\\\\\\" four \\\\\\\\\" no!" ';
                          print "$str\n\n";
                          print «1) lazy2 < $1 >\n» while $str =~ m/"(.*?)"(?<!\\")/g;
                          print «2) plus < $1 >\n» while $str =~ m/"(([^"\\]+|\\.)*)"/g;
                          print «3) std < $1 >\n» while $str =~ m/"((?>[^"\\]+|\\.)*)"/g;
                          print «4) lazy < $1 >\n» while $str =~ m/"(.*?)(?<!\\)"/g;
                          print «5) unroll < $1 >\n» while $str =~ m/"([^"\\]*(?:\\.[^"\\]*)*)"/g;
                          print «6) ??? < $1 >\n» while $str =~ m/"(.*?)"(?<! \\")/g;

                          cb «zero \» one\\" two \\\" free \\\\" four \\\\\" no!"

                          1) lazy2 < zero \" one\\" two \\\" free \\\\" four \\\\\" no! >
                          2) plus < zero \" one\\ >
                          2) plus < free \\\\ >
                          2) plus < no! >
                          3) std < zero \" one\\ >
                          3) std < free \\\\ >
                          3) std < no! >
                          4) lazy < zero \" one\\" two \\\" free \\\\" four \\\\\" no! >
                          5) unroll < zero \" one\\ >
                          5) unroll < free \\\\ >
                          5) unroll < no! >
                          6) ??? < zero \" one\\ >
                          6) ??? < free \\\\ >
                          6) ??? < no! >
                            0
                            std и plus правлены мною.
                            Насчёт моего утверждение, что plus не съест пустые кавычки — я был не прав. Извините. Это всё моя невнимательность… Остальное вроде так как и говорил.
                            И кстати, выше я предлагал выражение "((?>[^"\\]*|\\.)*)". Тут грубейшая ошибка!) Думаю сами догадались какая :)
                        0
                        Первое правило по Фридлу (во всяком случае для меня) — понимайте свои данные.
                        Если Вам нужно найти пары ключ-значение, при этом значение является строкой, находящейся в кавычках, отделенной от следующего ключа пробелом, так и напишите:

                        $str =~ /\G([-a-zA-Z0-9_]+) = "([^\s]*)" /gcx; # modern_1 - пессимистичный вариант, когда значение может быть пустым
                        или
                        $str =~ /\G([-a-zA-Z0-9_]+) = "([^\s]+)" /gcx; # medern_2 - оптимистичный вариант, у нас гарантировано не будет пустых значений

                        и получите

                                                Rate      std     lazy     plus   unroll   lazy_2 modern_1 modern_2
                        std              24660/s       --     -38%     -65%     -74%     -83%     -92%     -93%
                        lazy             39456/s      60%       --     -43%     -58%     -73%     -87%     -88%
                        plus             69591/s     182%      76%       --     -26%     -52%     -76%     -80%
                        unroll          93699/s     280%     137%      35%       --     -35%     -68%     -73%
                        lazy_2       143913/s     484%     265%     107%      54%       --     -51%     -58%
                        modern_1 295080/s    1097%     648%     324%     215%     105%       --     -14%
                        modern_2 341672/s    1286%     766%     391%     265%     137%      16%       --
                        
                        

                        Мысли-то у Вас в правильном направлении пошли с \s*
                          +1
                          В наших случаях мы учитывали ещё и возможность экранирования, что в вашем случае нет :)
                          PS: в чем вы строите такие таблицы хронометражей ?:)
                            0
                            Таблицы хронометражей сам только вчера подсмотрел у DurRandir — сходите в его пример кода.

                            Хорошо, поехали с Вашим замечанием — «возможность экранирования» — активная, как в Perl — 2 слеша -> 1 «экранированный» слеш или экранирование экранируемых символов нас не интересует? Это нифигово важное соглашение — отнеситесь серьезно.

                            Согласитесь — оптимизация решения общих вопросов в общем виде должна начинаться с уточнения вопроса и вида, а не с ковыряния алгоритма. При всем Вашем желании Вы не сможете мне на доске нарисовать сетку координат, в которую влезет любой придуманый мной прямоугольник.
                              0
                              Процитирую, что было написано выше:
                              «Но вот возьмём классику — выделить из текста строку между двумя кавычками, с учётом экранирование кавычки слешем.»
                              Я ответил на ваш вопрос?
                              Насчёт хронометража… хоть убей, не вижу там ничего кроме пастинга кода… хоть убей не вижу :)
                                0
                                Нет, не ответили :)
                                Я Вас русским по белому спрашиваю — слеш экранирует любой символ, включая слеш, или единственной экранируемой конструкцией является \" ?
                                Последовательность \\" для нас означает «экранированный слеш и кавычка» или «слеш и экранированная кавычка»? Теперь Вы понимает, почему это важное соглашение?

                                Сделайте копипаст кода по ссылке и запустите уже скрипт! Метод научного тыка — наше все :)
                                Вся магия в cmpthese из use Benchmark qw/cmpthese timethese/;
                                  0
                                  Я здесь ответу и Castle.

                                  Я согласен с тем, что случай экранирования произвольного количества слешей перед кавычкой ни одна из предложенных мной регулярок не решает. Но для моего случая (я использую lazy_2) — я буду считать пришедшие данные невалидными, если они не соответствуют этой регулярке. Благо я контролирую обе стороны передачи данных :)

                                  Это и ответ на 2й вопрос — про modern. Этот кусок кода — часть xml-парсера (а мне нужно очень небольшое подмножество xml), поэтому внутри кавычек может быть произвольный текст — вариант с [^] не проходит.
                                    0
                                    Давайте кусок настоящих (тождественных настоящим) данных — я запутался, о чем речь и почему нас интересует произвольный текст в кавычках внутри валидного xml, а пример — с парами ключ-значение? Что явлется данными, что разделителями?

                                    PS. Если Вы контролируете оба конца, то самое лучшее — акисома «разделитель является собственностью программиста! попытка подделки разделителя преследуется по закону». Т.е. объявляете для себя разделителем «что-то», и это «что-то» вырезаете из входящего текста до его комплексной обработки.
                                      0
                                      В 1м бенчмарке был вполне себе кусок данных. Просто там извлекается не только "...", но и key=«value» — это, видимо, и смутило при построении modern.

                                      PS: Формат — xml, от этого никуда не деться. Но если мне пришло что-то, с моей точки зрения, невалидное — я это спокойно отбрасываю. Полная версия парсера — 3 регулярки, на моём подможестве xml скорость примерно такая:

                                                           Rate simple_expat simple_default simple_libxml_sax simpe_parser simple_expat_xs xml_twig tree_parser xml_parser xml_libxml regexp
                                      xml_libxml         9754/s        1469%          1072%              673%         658%            645%     619%        230%       176%         --   -81%
                                      regexp            50355/s        8002%          5952%             3892%        3814%           3747%    3612%       1602%      1324%       416%     --
                                      
                                        0
                                        Оба выражения modern полностью решают задачу извлечения данных из пар ключ-значение, последовательно сохраняя ключ и парное ему значение в переменных $1 и $2 соответственно из данных приведенной Вами же в Вашем же примере адресной (для регулярного выражения) строки. Меня это поведение кода абсолютно не смущает. ЧЯДНТ?
                                        В общем — есть желание — выкладывайте пример исходных данных из жизни, нет — заминаем для ясности, бо последние дцать ответов — малоинтересные сообществу попытки уточнить, что имел ввиду отвечающий, когда не так понял вопрошающего.
                0
                Ещё бы к важным я причислил управление компиляцией… интерполюцией… предварительным копированием…
                Очень часто полезно применение атомарные группировки…

                Вообще, не зная принципов работы НКА не стоит даже пытаться что-либо оптимизировать. Особенно в работе с квантификаторами :) Велик шанс того, что эффект будет обратным. Либо вообще измените результат работы патерна.
                  0
                  Можно я Вас отговорю от управления компиляцией?
                  Пожалуйста, никогда не делайте так, даже если Вы точно знаете цель данного действа.
                  Управление компилятором — грязный трюк, который гарантировано закончится полным фиаско при минимальном обновлении внутренней логики.
                  Вообще, я как раз и пытаюсь заинтересовать читателя самостоятельно узнать побольше о принципах работы НКА и возможностях, которые ему станут доступны, отсылая к лучшей книге по этой теме.
                  Я, знаете ли, Фридла не заменю при всем желании, потому как ориентируюсь в вопросе не столь хорошо.
                    0
                    Можно поподробнее насчёт «грязного трюка»???
                      0
                      Эм. Как у меня часто случается — «Подумал не то, что сказал». Конечно же стоит использовать управление компиляцией шаблона, если он используется далее в цикле и т.п.
                      А имел ввиду я всякие «суб-оптимизационные» трюки с вариантом шаблона, который по тем или иным причинам, не связанным с логикой регулярных выражений, выполняется быстрее в строго определенной среде.

                Only users with full accounts can post comments. Log in, please.