Здравствуйте, _NN_, Вы писали:
_NN>В копилку могу добавить и антипаттерн вида:
^prefix.+
_NN>Казалось бы тут можно оптимизировать и остановиться сразу как нашли начало, однако '.' означает всё кроме (в зависимости от флагов) символа новой строки.
_NN>И получаем полное сканирование входной строки.
Сканирование (если префикс нашли) будет, может даже двойная память потребуется, но ведь квадрат не вылезет: дойдём до конца строки, и, если по дороге было что-то, то отработаем? Вот если без птички в начале, тогда печалька, будем на каждом вхождении префикса внутри строки перезапускаться и поимеем квадрат. Хотя, если хвост сам по себе не нужен (например, мы не хотим его тоже выкинуть), то действительно оверхед, но не критичный.
Здравствуйте, cures, Вы писали:
C>Сканирование (если префикс нашли) будет, может даже двойная память потребуется, но ведь квадрат не вылезет: дойдём до конца строки, и, если по дороге было что-то, то отработаем? Вот если без птички в начале, тогда печалька, будем на каждом вхождении префикса внутри строки перезапускаться и поимеем квадрат. Хотя, если хвост сам по себе не нужен (например, мы не хотим его тоже выкинуть), то действительно оверхед, но не критичный.
У нас получился критичный, было много регулярок такого плана, приходило много строк по 100кб и каждую сканировали по нескольку раз
Здравствуйте, _NN_, Вы писали:
_NN>У нас получился критичный, было много регулярок такого плана, приходило много строк по 100кб и каждую сканировали по нескольку раз
Почему не объединить регулярки дизъюнкцией "|" и скомпилировать? Разная логика на каждую регулярку? А если объединить, те которые с одинаковой логикой?
T>Да, о реализации движков очень хорошо изложено в классической книжке «Регулярные выражения» Дж. Фридла, глава 4.
T>Там же описаны гибридные реализации. Например можно строить для регулярки ДКА (игнорируя некоторые навороты) и НКА. Далее ищем по строке с помощью ДКА, а имея совпадение прогоняем на нём НКА.
T>К сожалению, о ТДКА Фридл ни во втором, ни в 3-ем русском издании не упоминает.
Ещё неплохо почитать до сих пор актуальные статьи от Russ Cox:
https://swtch.com/~rsc/regexp/
Он же написал
RE2, которая в данном случае должна отрабатывать линейно, если мне склероз не изменяет. RE2 тоже не панацея, в некоторых случаях откатывается на реализацию с бэктрекингом.
