Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Пардон, а что такое gerex в PHP?
1 пункт оптимизаторы обычно правят сами :)
Главное забыто — жадные модификаторы, особенно .*
Backtracking после них — может съесть бОльшую часть времени выполнения регулярного выражения. Лучше использовать либо negated character classes [^abc] (если известна граница группы), либо попробовать переписать логику на работе с не-жадной версией .*?
Backtracking после них — может съесть бОльшую часть времени выполнения регулярного выражения. Лучше использовать либо negated character classes [^abc] (если известна граница группы), либо попробовать переписать логику на работе с не-жадной версией .*?
Готов обсудить Ваше предложение подробнее, как только Вы явно озвучите, что именно Вы имеете ввиду под определением «Backtracking». Не хотелось бы дискутировать о преимуществе арбузов над помидорами.
В общем же виде сама модель НКА, применяемого практически во всех продуктах (за редким исключением), формализуется как «поиск самого длинного совпадения, ближнего к левому краю», т.е. механизм внутреннеоптимизирован.
И как пишет Фридл (стр.314)
и ранее (стр.304)
Я бы рекомендовал использовать (+) а не (*) в качестве квантификатора всегда, когда это возможно.
Что до negated character classes [^abc] — да, очень эффективная техника, но с большими ограничениями.
В общем же виде сама модель НКА, применяемого практически во всех продуктах (за редким исключением), формализуется как «поиск самого длинного совпадения, ближнего к левому краю», т.е. механизм внутреннеоптимизирован.
И как пишет Фридл (стр.314)
Если Вам абсолютно ничего не известно о целевых данных, выбирайте максимальный квантификатор, поскольку он обычно оптимизируется чуть лучше минимального, особенно если следующий элемент регулярного выражения не позволяет использовать оптимизацию по символу, следующему за минимальным квантификатором.
и ранее (стр.304)
Проверка символа, следующего за минимальным квантификатором.
При использовании минимальных квантификаторов в конструкциях вида /"(.*?)"/ механизм должен постоянно переходить между проверками совпадения квантифицированной конструкции (точки) и тем, что следует после нее ("). По этой и по ряду других причин минимальные квантификаторы обычно работают гораздо медленнее максимальных.<...> Если минимальный квантификатор заключен в сохраняющие круглые скобки, управление приходится постоянно передавать внутрь скобок и за их пределы, что приводит к дополнительным затратам времени.
Я бы рекомендовал использовать (+) а не (*) в качестве квантификатора всегда, когда это возможно.
Что до negated character classes [^abc] — да, очень эффективная техника, но с большими ограничениями.
Backtracking — механизм «возврата» жадным квалификатором символов входной строки, если текущее (т.е. изначально — до конца строки) его значение не позволяет выполнится всему регулярному выражению. Это иногда удобно — если нам нужен текст между первым < и последним >, то можно написать просто /<.*>/ — и вернётся всё, что нужно. Но чаще бывает другая ситуация — нам нужен какой-то небольшой участок входного текста — первый тег, к примеру. Тогда жадность создаст большие проблемы — съев всю строку.
Жадные модификаторы плохи, когда им приходится возвращать обратно регулярному выражению много, и хороши, когда возвращать почти ничего не придётся. Это правило позволяет определить, когда их стоит использовать, а когда — нет.
По поводу + — иногда надо разрешать пустые участки — к примеру, bb-теги [b][/b] — валидный тег, но внутри ничего нет. Или если во входном тексте пробел — необязательный разделитель ввода.
Низкая производительность не-жадных модификаторов — да, выход из сохраняющих скобок дорог. Но вот возьмём классику — выделить из текста строку между двумя кавычками, с учётом экранирование кавычки слешем. У меня есть пример из «Mastering regular expressions» с использованием жадного варианта [^..]* и мой вариант, через .*? и negative look-behind. Второй — быстрее) Могу привести обе регулярки.
Жадные модификаторы плохи, когда им приходится возвращать обратно регулярному выражению много, и хороши, когда возвращать почти ничего не придётся. Это правило позволяет определить, когда их стоит использовать, а когда — нет.
По поводу + — иногда надо разрешать пустые участки — к примеру, bb-теги [b][/b] — валидный тег, но внутри ничего нет. Или если во входном тексте пробел — необязательный разделитель ввода.
Низкая производительность не-жадных модификаторов — да, выход из сохраняющих скобок дорог. Но вот возьмём классику — выделить из текста строку между двумя кавычками, с учётом экранирование кавычки слешем. У меня есть пример из «Mastering regular expressions» с использованием жадного варианта [^..]* и мой вариант, через .*? и negative look-behind. Второй — быстрее) Могу привести обе регулярки.
На регулярки было бы интересно взглянуть. В идеале и на хронометраж.
Из Mastering RE — "([^"\\]*(?:\\.[^"\\]*)*)"
Lazy + negative lb — "(.*?)"(?<! \\")
paste.org.ru/?374ll0
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% --
извините, но выражение по вашей ссылке на мой субъективный взгляд некорректны :)
1) std
сохраняющие скобки захватывают не то что надо, +атомарная группировка и квантификатор должны немного улучшить дело :)
"((?>[^"\\]*|\\.)*)" — так мне кажется корректней. По идее и быстрее. Извините, щас проверить не могу, нет ничего под рукой…
2) lazy
"(.*?)(?<!\\)"
Как я понял он некорректен при выражении вида \\"
У lazy_2 та же проблема.
3) plus
не съест найдёт пустый строки ""
Получается только unroll валидный для отловки текста между двумя кавычками :) В нём вроде как всё выглядит нормально. По крайней мере на первый взгляд :)
Щас будем думать как и его улучшить. :)
1) std
сохраняющие скобки захватывают не то что надо, +атомарная группировка и квантификатор должны немного улучшить дело :)
"((?>[^"\\]*|\\.)*)" — так мне кажется корректней. По идее и быстрее. Извините, щас проверить не могу, нет ничего под рукой…
2) lazy
"(.*?)(?<!\\)"
Как я понял он некорректен при выражении вида \\"
У lazy_2 та же проблема.
3) plus
не съест найдёт пустый строки ""
Получается только unroll валидный для отловки текста между двумя кавычками :) В нём вроде как всё выглядит нормально. По крайней мере на первый взгляд :)
Щас будем думать как и его улучшить. :)
На примере с \\" споткнулся только lazy: paste.org.ru/?i2g88w (или есть более сложный пример?)
Поменяв $str на "" — съели все. ЧЯДНТ?)
Насколько я помню этот скрипт — std, plus, unroll все из Mastering RE. Ещё, если перл 5.10 — можно попробовать greedy, но у меня нет его под рукой.
Поменяв $str на "" — съели все. ЧЯДНТ?)
Насколько я помню этот скрипт — std, plus, unroll все из Mastering RE. Ещё, если перл 5.10 — можно попробовать greedy, но у меня нет его под рукой.
$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! >
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! >
Первое правило по Фридлу (во всяком случае для меня) — понимайте свои данные.
Если Вам нужно найти пары ключ-значение, при этом значение является строкой, находящейся в кавычках, отделенной от следующего ключа пробелом, так и напишите:
или
и получите
Мысли-то у Вас в правильном направлении пошли с
Если Вам нужно найти пары ключ-значение, при этом значение является строкой, находящейся в кавычках, отделенной от следующего ключа пробелом, так и напишите:
$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*В наших случаях мы учитывали ещё и возможность экранирования, что в вашем случае нет :)
PS: в чем вы строите такие таблицы хронометражей ?:)
PS: в чем вы строите такие таблицы хронометражей ?:)
Таблицы хронометражей сам только вчера подсмотрел у DurRandir — сходите в его пример кода.
Хорошо, поехали с Вашим замечанием — «возможность экранирования» — активная, как в Perl — 2 слеша -> 1 «экранированный» слеш или экранирование экранируемых символов нас не интересует? Это нифигово важное соглашение — отнеситесь серьезно.
Согласитесь — оптимизация решения общих вопросов в общем виде должна начинаться с уточнения вопроса и вида, а не с ковыряния алгоритма. При всем Вашем желании Вы не сможете мне на доске нарисовать сетку координат, в которую влезет любой придуманый мной прямоугольник.
Хорошо, поехали с Вашим замечанием — «возможность экранирования» — активная, как в Perl — 2 слеша -> 1 «экранированный» слеш или экранирование экранируемых символов нас не интересует? Это нифигово важное соглашение — отнеситесь серьезно.
Согласитесь — оптимизация решения общих вопросов в общем виде должна начинаться с уточнения вопроса и вида, а не с ковыряния алгоритма. При всем Вашем желании Вы не сможете мне на доске нарисовать сетку координат, в которую влезет любой придуманый мной прямоугольник.
Процитирую, что было написано выше:
«Но вот возьмём классику — выделить из текста строку между двумя кавычками, с учётом экранирование кавычки слешем.»
Я ответил на ваш вопрос?
Насчёт хронометража… хоть убей, не вижу там ничего кроме пастинга кода… хоть убей не вижу :)
«Но вот возьмём классику — выделить из текста строку между двумя кавычками, с учётом экранирование кавычки слешем.»
Я ответил на ваш вопрос?
Насчёт хронометража… хоть убей, не вижу там ничего кроме пастинга кода… хоть убей не вижу :)
Нет, не ответили :)
Я Вас русским по белому спрашиваю — слеш экранирует любой символ, включая слеш, или единственной экранируемой конструкцией является
Последовательность
Сделайте копипаст кода по ссылке и запустите уже скрипт! Метод научного тыка — наше все :)
Вся магия в cmpthese из use Benchmark qw/cmpthese timethese/;
Я Вас русским по белому спрашиваю — слеш экранирует любой символ, включая слеш, или единственной экранируемой конструкцией является
\" ?Последовательность
\\" для нас означает «экранированный слеш и кавычка» или «слеш и экранированная кавычка»? Теперь Вы понимает, почему это важное соглашение?Сделайте копипаст кода по ссылке и запустите уже скрипт! Метод научного тыка — наше все :)
Вся магия в cmpthese из use Benchmark qw/cmpthese timethese/;
Я здесь ответу и Castle.
Я согласен с тем, что случай экранирования произвольного количества слешей перед кавычкой ни одна из предложенных мной регулярок не решает. Но для моего случая (я использую lazy_2) — я буду считать пришедшие данные невалидными, если они не соответствуют этой регулярке. Благо я контролирую обе стороны передачи данных :)
Это и ответ на 2й вопрос — про modern. Этот кусок кода — часть xml-парсера (а мне нужно очень небольшое подмножество xml), поэтому внутри кавычек может быть произвольный текст — вариант с [^] не проходит.
Я согласен с тем, что случай экранирования произвольного количества слешей перед кавычкой ни одна из предложенных мной регулярок не решает. Но для моего случая (я использую lazy_2) — я буду считать пришедшие данные невалидными, если они не соответствуют этой регулярке. Благо я контролирую обе стороны передачи данных :)
Это и ответ на 2й вопрос — про modern. Этот кусок кода — часть xml-парсера (а мне нужно очень небольшое подмножество xml), поэтому внутри кавычек может быть произвольный текст — вариант с [^] не проходит.
Давайте кусок настоящих (тождественных настоящим) данных — я запутался, о чем речь и почему нас интересует произвольный текст в кавычках внутри валидного xml, а пример — с парами ключ-значение? Что явлется данными, что разделителями?
PS. Если Вы контролируете оба конца, то самое лучшее — акисома «разделитель является собственностью программиста! попытка подделки разделителя преследуется по закону». Т.е. объявляете для себя разделителем «что-то», и это «что-то» вырезаете из входящего текста до его комплексной обработки.
PS. Если Вы контролируете оба конца, то самое лучшее — акисома «разделитель является собственностью программиста! попытка подделки разделителя преследуется по закону». Т.е. объявляете для себя разделителем «что-то», и это «что-то» вырезаете из входящего текста до его комплексной обработки.
В 1м бенчмарке был вполне себе кусок данных. Просто там извлекается не только "...", но и key=«value» — это, видимо, и смутило при построении modern.
PS: Формат — xml, от этого никуда не деться. Но если мне пришло что-то, с моей точки зрения, невалидное — я это спокойно отбрасываю. Полная версия парсера — 3 регулярки, на моём подможестве xml скорость примерно такая:
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% --
Оба выражения modern полностью решают задачу извлечения данных из пар ключ-значение, последовательно сохраняя ключ и парное ему значение в переменных $1 и $2 соответственно из данных приведенной Вами же в Вашем же примере адресной (для регулярного выражения) строки. Меня это поведение кода абсолютно не смущает. ЧЯДНТ?
В общем — есть желание — выкладывайте пример исходных данных из жизни, нет — заминаем для ясности, бо последние дцать ответов — малоинтересные сообществу попытки уточнить, что имел ввиду отвечающий, когда не так понял вопрошающего.
В общем — есть желание — выкладывайте пример исходных данных из жизни, нет — заминаем для ясности, бо последние дцать ответов — малоинтересные сообществу попытки уточнить, что имел ввиду отвечающий, когда не так понял вопрошающего.
Ещё бы к важным я причислил управление компиляцией… интерполюцией… предварительным копированием…
Очень часто полезно применение атомарные группировки…
Вообще, не зная принципов работы НКА не стоит даже пытаться что-либо оптимизировать. Особенно в работе с квантификаторами :) Велик шанс того, что эффект будет обратным. Либо вообще измените результат работы патерна.
Очень часто полезно применение атомарные группировки…
Вообще, не зная принципов работы НКА не стоит даже пытаться что-либо оптимизировать. Особенно в работе с квантификаторами :) Велик шанс того, что эффект будет обратным. Либо вообще измените результат работы патерна.
Можно я Вас отговорю от управления компиляцией?
Пожалуйста, никогда не делайте так, даже если Вы точно знаете цель данного действа.
Управление компилятором — грязный трюк, который гарантировано закончится полным фиаско при минимальном обновлении внутренней логики.
Вообще, я как раз и пытаюсь заинтересовать читателя самостоятельно узнать побольше о принципах работы НКА и возможностях, которые ему станут доступны, отсылая к лучшей книге по этой теме.
Я, знаете ли, Фридла не заменю при всем желании, потому как ориентируюсь в вопросе не столь хорошо.
Пожалуйста, никогда не делайте так, даже если Вы точно знаете цель данного действа.
Управление компилятором — грязный трюк, который гарантировано закончится полным фиаско при минимальном обновлении внутренней логики.
Вообще, я как раз и пытаюсь заинтересовать читателя самостоятельно узнать побольше о принципах работы НКА и возможностях, которые ему станут доступны, отсылая к лучшей книге по этой теме.
Я, знаете ли, Фридла не заменю при всем желании, потому как ориентируюсь в вопросе не столь хорошо.
Можно поподробнее насчёт «грязного трюка»???
Эм. Как у меня часто случается — «Подумал не то, что сказал». Конечно же стоит использовать управление компиляцией шаблона, если он используется далее в цикле и т.п.
А имел ввиду я всякие «суб-оптимизационные» трюки с вариантом шаблона, который по тем или иным причинам, не связанным с логикой регулярных выражений, выполняется быстрее в строго определенной среде.
А имел ввиду я всякие «суб-оптимизационные» трюки с вариантом шаблона, который по тем или иным причинам, не связанным с логикой регулярных выражений, выполняется быстрее в строго определенной среде.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Общие советы по составлению оптимальных регулярных выражений