Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков.
Недавно стековерфлоу лёг на простенькой функции, которая чистила строчку от концевых пробелов.
Мы же понимаем, как легко это делается регекспами: s/\s+$//
Беда подкралась внезапно: строка с 20тыс пробелов в середине.
Движок регекспа запнулся и устроил квадратичный забег с откатами.
К>Недавно стековерфлоу лёг на простенькой функции, которая чистила строчку от концевых пробелов. К>Мы же понимаем, как легко это делается регекспами: 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-ем русском издании не упоминает.
Здравствуйте, Vain, Вы писали:
К>>Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков. V>Какая же попаболь у перловцев.. (первый же пример пропагандирует использование г-нищи)
В Perl стандартный способ сделать trim, это код:
$str =~ s/^\s+//;
$str =~ s/\s+$//;
И он не спотыкается на указанной в начальном сообщении строке.
V>PS Кстати, в перле есть такие встроенные переменные как $&. Помниться долго искал причину почему производительность регулярки была в районе плинтуса, хотя групинга никакого не было..
О том, что использование встроенных переменных понижает производительность регулярных выражений, прямо написано в документации.
А всё потому, что регэкспы надо разделить на две части — простые и сложные и явно отразить это в API. Простые регэкспы должны работать за O(N) (через DFA, например), а сложные пусть хоть заоткатываются.
А сейчас регэкспы это просто мессиво. Во-первых куча похожих, но отличающихся синтаксисов, во-вторых реализации без каких-то гарантий.
T>Да, о реализации движков очень хорошо изложено в классической книжке «Регулярные выражения» Дж. Фридла, глава 4. T>Там же описаны гибридные реализации. Например можно строить для регулярки ДКА (игнорируя некоторые навороты) и НКА. Далее ищем по строке с помощью ДКА, а имея совпадение прогоняем на нём НКА. T>К сожалению, о ТДКА Фридл ни во втором, ни в 3-ем русском издании не упоминает.
Ещё неплохо почитать до сих пор актуальные статьи от Russ Cox: https://swtch.com/~rsc/regexp/
Он же написал RE2, которая в данном случае должна отрабатывать линейно, если мне склероз не изменяет. RE2 тоже не панацея, в некоторых случаях откатывается на реализацию с бэктрекингом.
Здравствуйте, anonymous, Вы писали:
A>Не знаю. Могу только предположить, что оптимизация именно этих выражений, как часто используемых. Точнее второго: движок сразу понимает, что смотреть нужно конце, а не проверять, тянется ли найденное совпадение до конца.
A>Вот это уже не будет так работать: A>
Здравствуйте, Слава, Вы писали:
С>Здравствуйте, Кодт, Вы писали:
К>>Мы же понимаем, как легко это делается регекспами: 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.
Здравствуйте, Vain, Вы писали:
A>>>>Сочувствую боли, которую ты причинил себе. V>>>У меня не было боли. A>>Откуда ж ты о ней знаешь? V>Потому что как и все наступил на эти раскиданные грабли, но быстро увернулся
Прочувствовал, значит.
A>>Ага, нахватаются где-то вершков про встроенные переменные, а потом язык у них виноват. V>Да, виноват, потому что является поставщиком скрытых "Performance issue" и других "прелестей"
Как они могут быть скрытыми, если они явно описаны в документации? Ты пытаешься использовать возможность языка, не прочитав документацию, а потом винишь язык в том, что эта возможность работает не так, как ты себе напридумывал.
A>>Другие потом читают написанный первыми код и думают: «Капец язык, ничего не понять!» V>Так это недолго, скоро нечего будет читать
Отладил один скрипт и туда же — эксперт по умирающим языкам.
Здравствуйте, Кодт, Вы писали:
К>Движок регекспа запнулся и устроил квадратичный забег с откатами.
Строго говоря, не регекспом, а плохим движком, в чём они честно и признаются: "simple backtracking Regex engine". Это всё ещё поди в похапе каком-нибудь было. Сам по себе регексп вполне нормальный, автоматный. А вот креативные движки, чтобы любая кухарка за пять минут сделала себе магазин и бложег — зло. Особенно когда на них делают нагруженные сайты. Особенно "дванольные", "динамические" бесят: зайдёшь на курсеру или хакерранк, откроешь несколько страниц — и сразу и лиса и хром хоть на атоме хоть на i5 пухнут и дохнут, затыкая весь брафсер (лиса) пока не прочухаются. Чем статика не устраивает? Обязательно что-нибудь должно попукивать и похрюкивать?
Мне как-то знакомая кидала ссылку на сайтик, который слабала на каком-то доморощенном "портале" викс с конструктором: там на дефолтном заднем плане звёзды летят, он практически весь закрыт собственно страничкой, на несколько пикселей торчит, но это не мешает движку их таки отрисовывать (хотя потом и не показывать), видимо, попиксельно, а то ещё и с рей-трейсингом, скорее всего на жабаскрипте. "Хлебнули мы ещё фанты — и тормознули автобус с омоном крутейший i5 с 16 гигами оперативы".
Вообще-то там проблема не столько с регуляркой, сколько с ее применением для одного и того же (не изменяющегося) поста каждый раз при запросе их домашней страницы.
Говорить дальше не было нужды. Как и все космонавты, капитан Нортон не испытывал особого доверия к явлениям, внешне слишком заманчивым.
Здравствуйте, VTT, Вы писали:
VTT>Вообще-то там проблема не столько с регуляркой, сколько с ее применением для одного и того же (не изменяющегося) поста каждый раз при запросе их домашней страницы.
И это тоже.
Но про грабли с регулярками надо знать.
А то вдруг найдутся добрые люди и сделают дос-бомбу для какого-нибудь блога или форума.
Здравствуйте, vsb, Вы писали:
vsb>А всё потому, что регэкспы надо разделить на две части — простые и сложные и явно отразить это в API. Простые регэкспы должны работать за O(N) (через DFA, например), а сложные пусть хоть заоткатываются. vsb>А сейчас регэкспы это просто мессиво. Во-первых куча похожих, но отличающихся синтаксисов, во-вторых реализации без каких-то гарантий.
Как отличать простые регекспы от сложных? Ещё один синтаксис?
Здравствуйте, Кодт, Вы писали:
vsb>>А всё потому, что регэкспы надо разделить на две части — простые и сложные и явно отразить это в API. Простые регэкспы должны работать за O(N) (через DFA, например), а сложные пусть хоть заоткатываются. vsb>>А сейчас регэкспы это просто мессиво. Во-первых куча похожих, но отличающихся синтаксисов, во-вторых реализации без каких-то гарантий.
К>Как отличать простые регекспы от сложных? Ещё один синтаксис?
Простые это подмножество сложных, без тех фич, которые невозможно реализовать в рамках конечных автоматов. Ну и ещё раз повторю — отдельное API для них, чтобы сразу было видно, какую производительность можно ожидать.
Здравствуйте, vsb, Вы писали:
vsb>Простые это подмножество сложных, без тех фич, которые невозможно реализовать в рамках конечных автоматов. Ну и ещё раз повторю — отдельное API для них, чтобы сразу было видно, какую производительность можно ожидать.
Исходный регексп ^(.*?)(\s+)$ вполне себе реализуется на недетерминированном конечном автомате. И в детерминированный его переделать несложно.
Проблема в том, что похожий на него ^(.*?)(\s\s)+$ — находящий чётное количество концевых пробелов (если концевое количество нечётное — первый пробел проигнорирует) — рождает уже довольно громоздкий детерминированный автомат.
И ведь нам интересно не только получить ответ "подходит — не подходит", но и координаты групп найти.
Здравствуйте, Кодт, Вы писали:
К>Это, конечно, тема обще-алгоритмическая, но в первую очередь, важна именно для скриптовых языков.
Какая же попаболь у перловцев.. (первый же пример пропагандирует использование г-нищи)
PS Кстати, в перле есть такие встроенные переменные как $&. Помниться долго искал причину почему производительность регулярки была в районе плинтуса, хотя групинга никакого не было..
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, 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 у строки. Зачем там потребовались регэкспы? Кто-то очень хорошо их знал, ценил, любил и применял?
Здравствуйте, anonymous, Вы писали:
A>>>Сочувствую боли, которую ты причинил себе. V>>У меня не было боли. A>Откуда ж ты о ней знаешь?
Потому что как и все наступил на эти раскиданные грабли, но быстро увернулся
V>>Отладил и забыл. А вот что-то серьёзное на перле писать я уже не буду. Благо есть языки получше. A>Ага, нахватаются где-то вершков про встроенные переменные, а потом язык у них виноват.
Да, виноват, потому что является поставщиком скрытых "Performance issue" и других "прелестей"
A>Другие потом читают написанный первыми код и думают: «Капец язык, ничего не понять!»
Так это недолго, скоро нечего будет читать
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, anonymous, Вы писали:
A>>>>>Сочувствую боли, которую ты причинил себе. V>>>>У меня не было боли. A>>>Откуда ж ты о ней знаешь? V>>Потому что как и все наступил на эти раскиданные грабли, но быстро увернулся A>Прочувствовал, значит.
Тебя видимо попаболь берёт, что сам мучился и продолжаешь мучаться, а другие нет
A>>>Ага, нахватаются где-то вершков про встроенные переменные, а потом язык у них виноват. V>>Да, виноват, потому что является поставщиком скрытых "Performance issue" и других "прелестей" A>Как они могут быть скрытыми, если они явно описаны в документации?
Ну я говорю, на заборе тоже много чего пишут...
A>Ты пытаешься использовать возможность языка, не прочитав документацию, а потом винишь язык в том, что эта возможность работает не так, как ты себе напридумывал.
Представь, даже не пытался использовать, просто решил проверить.
A>>>Другие потом читают написанный первыми код и думают: «Капец язык, ничего не понять!» V>>Так это недолго, скоро нечего будет читать A>Отладил один скрипт и туда же — эксперт по умирающим языкам.
Зачем мне становиться экспертом г-на?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
V>>>>>У меня не было боли. A>>>>Откуда ж ты о ней знаешь? V>>>Потому что как и все наступил на эти раскиданные грабли, но быстро увернулся A>>Прочувствовал, значит. V>Тебя видимо попаболь берёт, что сам мучился и продолжаешь мучаться, а другие нет
Какая разница, что там у меня? Ты ж либо на своём опыте ощущения описываешь, либо додумал, опять же основываясь на своём опыте.
A>>Как они могут быть скрытыми, если они явно описаны в документации? V>Ну я говорю, на заборе тоже много чего пишут...
Официальная документация по-твоему — забор? Ясно-понятно.
A>>Ты пытаешься использовать возможность языка, не прочитав документацию, а потом винишь язык в том, что эта возможность работает не так, как ты себе напридумывал. V>Представь, даже не пытался использовать, просто решил проверить.
Это и есть использование.
A>>Отладил один скрипт и туда же — эксперт по умирающим языкам. V>Зачем мне становиться экспертом г-на?
Здравствуйте, anonymous, Вы писали:
A>>>Прочувствовал, значит. V>>Тебя видимо попаболь берёт, что сам мучился и продолжаешь мучаться, а другие нет A>Какая разница, что там у меня? Ты ж либо на своём опыте ощущения описываешь, либо додумал, опять же основываясь на своём опыте.
а ты не на своём опыте мне свои ощущения начал приписывать?
A>>>Как они могут быть скрытыми, если они явно описаны в документации? V>>Ну я говорю, на заборе тоже много чего пишут... A>Официальная документация по-твоему — забор? Ясно-понятно.
Любая. Всё надо проверять.
A>>>Ты пытаешься использовать возможность языка, не прочитав документацию, а потом винишь язык в том, что эта возможность работает не так, как ты себе напридумывал. V>>Представь, даже не пытался использовать, просто решил проверить. A>Это и есть использование.
Нет, изначально оно не использовалось.
A>>>Отладил один скрипт и туда же — эксперт по умирающим языкам. V>>Зачем мне становиться экспертом г-на? A>Тебе виднее, зачем ты им стал?
Зачем ты бъёшь жену?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, anonymous, Вы писали:
A>>Официальная документация по-твоему — забор? Ясно-понятно. V>Любая. Всё надо проверять.
а разве можно как-то иначе?
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.
Здравствуйте, мыщъх, Вы писали:
A>>>Официальная документация по-твоему — забор? Ясно-понятно. V>>Любая. Всё надо проверять. М>а разве можно как-то иначе?
Про то и речь, что документация здесь не особо играет рояль.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
A>>Какая разница, что там у меня? Ты ж либо на своём опыте ощущения описываешь, либо додумал, опять же основываясь на своём опыте. V>а ты не на своём опыте мне свои ощущения начал приписывать?
Я только что описал, на основании чего сделал свои выводы.
A>>>>Как они могут быть скрытыми, если они явно описаны в документации? A>>Официальная документация по-твоему — забор? Ясно-понятно. V>Любая. Всё надо проверять.
При чём тут проверка? Я бы понял тебя, если бы обнаруженное тобой поведение не соответствовало описанию. Но в этом случае не так.
V>>>Представь, даже не пытался использовать, просто решил проверить. A>>Это и есть использование. V>Нет, изначально оно не использовалось.
Но потом-то использовалось. Пробовал — значит пользовался.
V>>>Зачем мне становиться экспертом г-на? A>>Тебе виднее, зачем ты им стал? V>Зачем ты бъёшь жену?
Здравствуйте, Vain, Вы писали:
V>Про то и речь, что документация здесь не особо играет рояль.
У тебя есть описание — ты можешь его проверить. У тебя нет описания — проверять тебе нечего, кроме своих догадок. Но инструмент не виноват, что у тебя с догадками проблемы.
Здравствуйте, anonymous, Вы писали:
V>>Про то и речь, что документация здесь не особо играет рояль. A>У тебя есть описание — ты можешь его проверить.
Я проверяю код а не описание, что за чушь?
A>У тебя нет описания — проверять тебе нечего, кроме своих догадок. Но инструмент не виноват, что у тебя с догадками проблемы.
Бред сивой кобылы
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, anonymous, Вы писали:
A>>>Какая разница, что там у меня? Ты ж либо на своём опыте ощущения описываешь, либо додумал, опять же основываясь на своём опыте. V>>а ты не на своём опыте мне свои ощущения начал приписывать? A>Я только что описал, на основании чего сделал свои выводы.
Прочувствовал, значит.
Тут нет оснований, одни догадки.
A>>>>>Как они могут быть скрытыми, если они явно описаны в документации? A>>>Официальная документация по-твоему — забор? Ясно-понятно. V>>Любая. Всё надо проверять. A>При чём тут проверка? Я бы понял тебя, если бы обнаруженное тобой поведение не соответствовало описанию. Но в этом случае не так.
Самое лучшее описание это проверенное тобой лично, что я и сделал.
V>>>>Представь, даже не пытался использовать, просто решил проверить. A>>>Это и есть использование. V>>Нет, изначально оно не использовалось. A>Но потом-то использовалось. Пробовал — значит пользовался.
Ты читать умеешь? Написал же что решил проверить.
V>>>>Зачем мне становиться экспертом г-на? A>>>Тебе виднее, зачем ты им стал? V>>Зачем ты бъёшь жену? A>Это не я.
Т.е. кто-то бъёт твою жену, а ты просто смотришь?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
A>>>>Какая разница, что там у меня? Ты ж либо на своём опыте ощущения описываешь, либо додумал, опять же основываясь на своём опыте. V>>>а ты не на своём опыте мне свои ощущения начал приписывать? A>>Я только что описал, на основании чего сделал свои выводы. V>Прочувствовал, значит. Тут нет оснований, одни догадки.
Ты вообще читаешь, прежде чем ответить? Я специально для тебя цитирование оставил.
A>>При чём тут проверка? Я бы понял тебя, если бы обнаруженное тобой поведение не соответствовало описанию. Но в этом случае не так. V>Самое лучшее описание это проверенное тобой лично, что я и сделал.
Демагогия.
A>>Но потом-то использовалось. Пробовал — значит пользовался. V>Ты читать умеешь? Написал же что решил проверить.
Ну. Пользовался.
V>>>>>Зачем мне становиться экспертом г-на? A>>>>Тебе виднее, зачем ты им стал? V>Т.е. кто-то бъёт твою жену, а ты просто смотришь?
Нет, кто-то пытается уйти от обсуждения своей экспертной области.
Здравствуйте, Vain, Вы писали:
A>>У тебя есть описание — ты можешь его проверить. A>>У тебя нет описания — проверять тебе нечего, кроме своих догадок. Но инструмент не виноват, что у тебя с догадками проблемы. V>Бред сивой кобылы
Здравствуйте, anonymous, Вы писали:
A>>>У тебя есть описание — ты можешь его проверить. A>>>У тебя нет описания — проверять тебе нечего, кроме своих догадок. Но инструмент не виноват, что у тебя с догадками проблемы. V>>Бред сивой кобылы A>Так себе аргумент.
когда чушню пишут — нормальный
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, anonymous, Вы писали:
A>>>При чём тут проверка? Я бы понял тебя, если бы обнаруженное тобой поведение не соответствовало описанию. Но в этом случае не так. V>>Самое лучшее описание это проверенное тобой лично, что я и сделал. A>Демагогия.
лучше чем твой тупенький троллинг
V>>>>>>Зачем мне становиться экспертом г-на? A>>>>>Тебе виднее, зачем ты им стал? V>>Т.е. кто-то бъёт твою жену, а ты просто смотришь? A>Нет, кто-то пытается уйти от обсуждения своей экспертной области.
нет, кто то пытается троллить и не выходит
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Казалось бы тут можно оптимизировать и остановиться сразу как нашли начало, однако '.' означает всё кроме (в зависимости от флагов) символа новой строки.
И получаем полное сканирование входной строки.
Здравствуйте, мыщъх, Вы писали:
К>>>Мы же понимаем, как легко это делается регекспами: s/\s+$// М>начнем с того, что \s это не только пробел, но и табуляция. жду рабочего примера на асме или си.
На С — легко, если только ASCII, то есть быстрый макрос isspace, помним позицию последнего непробельного, если уткнулись в педаль — перекидываем туда позицию для дальнейшего вывода.
М> да, кодировки могут быть разные.
Кодировки в этот момент обычно не должны сильно парить, строка уже должна без кодировок в четырёхбайтном представлении быть. Если Вы, конечно, не разработчик извращений типа Julia, где внутреннее представление UTF-8. При этом проверка на пробельность чуть сложнее, но всё равно за константу, причём уже наверняка реализована, потому алгоритм не меняется.
М> при этом желательно чтобы по времени разработки и по наглядности кода вы не сильно отличались от регулярки.
Наглядность — это фор хум хау. Вы репорт читали? Там таки кошмарненький исходный регексп, это они уже для ясности упростили. Ну и вызов функции trim гораздо более нагляден.
М> ну а производительность регулярок -- гуглим статьи Russ Cox'a. так что проблема не в регулярках, а в реализациях.
+1, и надо будет почитать на досуге.
М> почему в популярных языках используются такие реализации -- это другой вопрос.
Почему серьёзные сайты делают на "популярных языках" — это ещё более другой вопрос
Здравствуйте, _NN_, Вы писали:
_NN>В копилку могу добавить и антипаттерн вида:
^prefix.+
_NN>Казалось бы тут можно оптимизировать и остановиться сразу как нашли начало, однако '.' означает всё кроме (в зависимости от флагов) символа новой строки. _NN>И получаем полное сканирование входной строки.
Сканирование (если префикс нашли) будет, может даже двойная память потребуется, но ведь квадрат не вылезет: дойдём до конца строки, и, если по дороге было что-то, то отработаем? Вот если без птички в начале, тогда печалька, будем на каждом вхождении префикса внутри строки перезапускаться и поимеем квадрат. Хотя, если хвост сам по себе не нужен (например, мы не хотим его тоже выкинуть), то действительно оверхед, но не критичный.
Здравствуйте, cures, Вы писали:
C>Сканирование (если префикс нашли) будет, может даже двойная память потребуется, но ведь квадрат не вылезет: дойдём до конца строки, и, если по дороге было что-то, то отработаем? Вот если без птички в начале, тогда печалька, будем на каждом вхождении префикса внутри строки перезапускаться и поимеем квадрат. Хотя, если хвост сам по себе не нужен (например, мы не хотим его тоже выкинуть), то действительно оверхед, но не критичный.
У нас получился критичный, было много регулярок такого плана, приходило много строк по 100кб и каждую сканировали по нескольку раз
Здравствуйте, _NN_, Вы писали:
_NN>У нас получился критичный, было много регулярок такого плана, приходило много строк по 100кб и каждую сканировали по нескольку раз
Почему не объединить регулярки дизъюнкцией "|" и скомпилировать? Разная логика на каждую регулярку? А если объединить, те которые с одинаковой логикой?
Перекуём баги на фичи!
