Почему регулярное выражение. * Медленнее в одном месте и быстрее на другом
В последнее время я использую много регулярных выражений в java/ groovy. Для тестирования я обычно использую regex101.com. Очевидно, я тоже смотрю на производительность регулярных выражений.
Одна вещь, я заметил, что использование .* правильно может значительно улучшить общую производительность. Прежде всего, используя .* между ними или, лучше сказать, не в конце регулярного выражения, это производительность.
Например, в это регулярное выражение требуется необходимое количество шагов: 27:
![введите описание изображения здесь]()
Если я изменил первый .* на \s*, он значительно уменьшит необходимые шаги до 16:
![введите описание изображения здесь]()
Однако если я меняю второй .* на \s*, он не уменьшает дальнейшие шаги:
![введите описание изображения здесь]()
У меня есть несколько вопросов:
- Почему выше? Я не хочу сравнивать
\s и .*. Я знаю разницу. Я хочу знать, почему затраты \s и .* различаются в зависимости от их положения в полном регулярном выражении. А затем характеристики регулярного выражения, которые могут стоить по-разному в зависимости от их положения в общем регулярном выражении (или на основе любого другого аспекта, кроме положения, если таковой имеется).
- Дает ли счетчик шагов, данный на этом сайте, какие-либо указания о производительности регулярных выражений?
- какие другие простые или похожие (связанные с положением) наблюдения за регулярными выражениями у вас есть?
Ответы
Ответ 1
Механизмы регулярных выражений с квантором *, также как и жадный квантификатор, должны потреблять все на входе, которое соответствует, а затем:
- попробуйте следующий термин в регулярном выражении. Если он совпадает, продолжайте
- "unconsume" один символ (переместите указатель назад один), aka backtrack и перейти к шагу 1.
Так как . соответствует чему-либо (почти), первое состояние после столкновения с .* заключается в перемещении указателя в конец ввода, а затем начните перемещение назад через входной сигнал char за время, пробовав следующий термин пока не появится совпадение.
С \s* уничтожается только пробел, поэтому указатель изначально перемещается точно там, где вы хотите, - нет возврата к следующему члену.
Что-то, что вы должны попробовать, это использовать квантификатор неохотного .*?, который будет потреблять один char за один раз до следующего совпадения, который должен иметь такую же временную сложность, что и \s*, но быть немного более эффективным, не требуется проверка текущего char.
\s* и .* в конце выражения будут выполняться аналогичным образом, потому что оба будут потреблять все в конце ввода f, которое соответствует, что оставляет указатель равной позиции для обоих выражений.
Ответ 2
Из отладчика выводится следующее.
![pattern 1]()
![pattern 2]()
![pattern 3]()
Большая причина разницы в производительности заключается в том, что .* будет потреблять все до конца строки (кроме новой строки). Затем шаблон продолжит, заставляя регулярное выражение возвращаться (как видно на первом изображении).
Причина, по которой \s и .* одинаково хорошо работает в конце шаблона, заключается в том, что жадный шаблон против потребляющего пробела не имеет никакого значения, если нет ничего другого (кроме WS).
Если ваша тестовая строка не заканчивается пробелами, будет разница в производительности, как вы видели в первом шаблоне - регулярное выражение будет вынуждено отступить.
ИЗМЕНИТЬ
Вы можете увидеть разницу в производительности, если закончите что-то помимо пробелов:
Плохо:
^myname.*mahesh.*hiworld
![bad]()
лучше:
^myname.*mahesh\s*hiworld
![немного лучше]()
Еще лучше:
^myname\s*mahesh\s*hiworld
![Намного лучше]()
