Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков.
Недавно стековерфлоу лёг на простенькой функции, которая чистила строчку от концевых пробелов.
Мы же понимаем, как легко это делается регекспами: s/\s+$//
Беда подкралась внезапно: строка с 20тыс пробелов в середине.
Движок регекспа запнулся и устроил квадратичный забег с откатами.
Вообще-то там проблема не столько с регуляркой, сколько с ее применением для одного и того же (не изменяющегося) поста каждый раз при запросе их домашней страницы.
Говорить дальше не было нужды. Как и все космонавты, капитан Нортон не испытывал особого доверия к явлениям, внешне слишком заманчивым.
А всё потому, что регэкспы надо разделить на две части — простые и сложные и явно отразить это в API. Простые регэкспы должны работать за O(N) (через DFA, например), а сложные пусть хоть заоткатываются.
А сейчас регэкспы это просто мессиво. Во-первых куча похожих, но отличающихся синтаксисов, во-вторых реализации без каких-то гарантий.
Здравствуйте, VTT, Вы писали:
VTT>Вообще-то там проблема не столько с регуляркой, сколько с ее применением для одного и того же (не изменяющегося) поста каждый раз при запросе их домашней страницы.
И это тоже.
Но про грабли с регулярками надо знать.
А то вдруг найдутся добрые люди и сделают дос-бомбу для какого-нибудь блога или форума.
Здравствуйте, vsb, Вы писали:
vsb>А всё потому, что регэкспы надо разделить на две части — простые и сложные и явно отразить это в API. Простые регэкспы должны работать за O(N) (через DFA, например), а сложные пусть хоть заоткатываются. vsb>А сейчас регэкспы это просто мессиво. Во-первых куча похожих, но отличающихся синтаксисов, во-вторых реализации без каких-то гарантий.
Как отличать простые регекспы от сложных? Ещё один синтаксис?
Здравствуйте, Кодт, Вы писали:
vsb>>А всё потому, что регэкспы надо разделить на две части — простые и сложные и явно отразить это в API. Простые регэкспы должны работать за O(N) (через DFA, например), а сложные пусть хоть заоткатываются. vsb>>А сейчас регэкспы это просто мессиво. Во-первых куча похожих, но отличающихся синтаксисов, во-вторых реализации без каких-то гарантий.
К>Как отличать простые регекспы от сложных? Ещё один синтаксис?
Простые это подмножество сложных, без тех фич, которые невозможно реализовать в рамках конечных автоматов. Ну и ещё раз повторю — отдельное API для них, чтобы сразу было видно, какую производительность можно ожидать.
Здравствуйте, vsb, Вы писали:
vsb>Простые это подмножество сложных, без тех фич, которые невозможно реализовать в рамках конечных автоматов. Ну и ещё раз повторю — отдельное API для них, чтобы сразу было видно, какую производительность можно ожидать.
Исходный регексп ^(.*?)(\s+)$ вполне себе реализуется на недетерминированном конечном автомате. И в детерминированный его переделать несложно.
Проблема в том, что похожий на него ^(.*?)(\s\s)+$ — находящий чётное количество концевых пробелов (если концевое количество нечётное — первый пробел проигнорирует) — рождает уже довольно громоздкий детерминированный автомат.
И ведь нам интересно не только получить ответ "подходит — не подходит", но и координаты групп найти.
К>Недавно стековерфлоу лёг на простенькой функции, которая чистила строчку от концевых пробелов. К>Мы же понимаем, как легко это делается регекспами: s/\s+$// К>Беда подкралась внезапно: строка с 20тыс пробелов в середине.
А вот не нужно использовать регулярки там, где есть специализированные функции.
В любом современном языке есть функция для отрезания концевых пробелов, которая гарантированно работает быстрее, экономнее и главное корректно в любых ситуациях.
К>Движок регекспа запнулся и устроил квадратичный забег с откатами. К>http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016 К>
К>"_____x__"
К> +++++X - неудача, откат
К> ++++X - неудача, откат
К> +++X - неудача, откат
К> ++X - неудача, откат
К> +X - неудача, откат
К> X - сразу неудача, идём дальше
К> +++ - удача, конец
К>
Простейший диалект языка регулярных выражений (РЕГ) эквивалентен детерминированному конечному автомату (ДКА).
И преобразовав РЕГ в ДКА можно проверить совпадение за линейное время.
Но, уже возможность группировки и получения значений сопоставленных групп ломает эту идилию.
Не говоря уже о ссылках на группы.
Поэтому большинство популярных реализаций использует реализацию через интерпретацию — типа расширенный НКА (недетерминированный конечный автомат).
Которая сильно более гибка (например реализации от MS, Lua, PCRE умеют описывать вложенные структуры), но улетает в экспоненту на некоторых типах регулярок и строк.
Что мы и видим на данном примере.
Да, о реализации движков очень хорошо изложено в классической книжке «Регулярные выражения» Дж. Фридла, глава 4.
Там же описаны гибридные реализации. Например можно строить для регулярки ДКА (игнорируя некоторые навороты) и НКА. Далее ищем по строке с помощью ДКА, а имея совпадение прогоняем на нём НКА.
К сожалению, о ТДКА Фридл ни во втором, ни в 3-ем русском издании не упоминает.
Здравствуйте, Кодт, Вы писали:
К>Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков.
Какая же попаболь у перловцев.. (первый же пример пропагандирует использование г-нищи)
PS Кстати, в перле есть такие встроенные переменные как $&. Помниться долго искал причину почему производительность регулярки была в районе плинтуса, хотя групинга никакого не было..
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
К>>Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков. V>Какая же попаболь у перловцев.. (первый же пример пропагандирует использование г-нищи)
В Perl стандартный способ сделать trim, это код:
$str =~ s/^\s+//;
$str =~ s/\s+$//;
И он не спотыкается на указанной в начальном сообщении строке.
V>PS Кстати, в перле есть такие встроенные переменные как $&. Помниться долго искал причину почему производительность регулярки была в районе плинтуса, хотя групинга никакого не было..
О том, что использование встроенных переменных понижает производительность регулярных выражений, прямо написано в документации.
Здравствуйте, anonymous, Вы писали:
A>Здравствуйте, Vain, Вы писали:
К>>>Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков. V>>Какая же попаболь у перловцев.. (первый же пример пропагандирует использование г-нищи)
A>В Perl стандартный способ сделать trim, это код: A>
A>$str =~ s/^\s+//;
A>$str =~ s/\s+$//;
A>
A>И он не спотыкается на указанной в начальном сообщении строке.
Здравствуйте, Sharov, Вы писали:
A>>В Perl стандартный способ сделать trim, это код: A>>
A>>$str =~ s/^\s+//;
A>>$str =~ s/\s+$//;
A>>
A>>И он не спотыкается на указанной в начальном сообщении строке. S>Почему? Движок, стандарт другой?
Не знаю. Могу только предположить, что оптимизация именно этих выражений, как часто используемых. Точнее второго: движок сразу понимает, что смотреть нужно конце, а не проверять, тянется ли найденное совпадение до конца.
Здравствуйте, anonymous, Вы писали:
A>О том, что использование встроенных переменных понижает производительность регулярных выражений, прямо написано в документации.
Чтобы что-то прочитать из документации надо сначало хотя бы знать что искать и где. А когда хер знает из-за чего тормозит это уже претензии к перлу будут в целом.
A>Сочувствую боли, которую ты причинил себе.
У меня не было боли. Отладил и забыл. А вот что-то серьёзное на перле писать я уже не буду. Благо есть языки получше.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
A>>О том, что использование встроенных переменных понижает производительность регулярных выражений, прямо написано в документации. V>Чтобы что-то прочитать из документации надо сначало хотя бы знать что искать и где. А когда хер знает из-за чего тормозит это уже претензии к перлу будут в целом.
perldoc perlvar → Variables related to regular expressions → Performance issues
A>>Сочувствую боли, которую ты причинил себе. V>У меня не было боли.
Откуда ж ты о ней знаешь?
V>Отладил и забыл. А вот что-то серьёзное на перле писать я уже не буду. Благо есть языки получше.
Ага, нахватаются где-то вершков про встроенные переменные, а потом язык у них виноват. Другие потом читают написанный первыми код и думают: «Капец язык, ничего не понять!»
Здравствуйте, Кодт, Вы писали:
К>Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков.
К>Недавно стековерфлоу лёг на простенькой функции, которая чистила строчку от концевых пробелов. К>Мы же понимаем, как легко это делается регекспами: s/\s+$//
Если я правильно помню, подобный поиск первого не-пробельного символа делался на ассемблере с помощью одной инструкции вроде repnz scas <образец>, <указатель на строку>, или что-то вроде. Для C-подобных языков это делалось бы обычным for i--, а в C# вообще есть стандартный TrimEnd у строки. Зачем там потребовались регэкспы? Кто-то очень хорошо их знал, ценил, любил и применял?
Здравствуйте, Слава, Вы писали:
С>Здравствуйте, Кодт, Вы писали:
К>>Мы же понимаем, как легко это делается регекспами: s/\s+$// С>Зачем там потребовались регэкспы? Кто-то очень хорошо их знал, ценил, любил и применял?
начнем с того, что \s это не только пробел, но и табуляция. жду рабочего примера на асме или си. да, кодировки могут быть разные. при этом желательно чтобы по времени разработки и по наглядности кода вы не сильно отличались от регулярки. ну а производительность регулярок -- гуглим статьи Russ Cox'a. так что проблема не в регулярках, а в реализациях. почему в популярных языках используются такие реализации -- это другой вопрос.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Перекуём баги на фичи!
