Почему регулярное выражение. * Медленнее в одном месте и быстрее на другом

В последнее время я использую много регулярных выражений в java/ groovy. Для тестирования я обычно использую regex101.com. Очевидно, я тоже смотрю на производительность регулярных выражений.

Одна вещь, я заметил, что использование .* правильно может значительно улучшить общую производительность. Прежде всего, используя .* между ними или, лучше сказать, не в конце регулярного выражения, это производительность.

Например, в это регулярное выражение требуется необходимое количество шагов: 27:

Если я изменил первый .* на \s*, он значительно уменьшит необходимые шаги до 16:

Однако если я меняю второй .* на \s*, он не уменьшает дальнейшие шаги:

У меня есть несколько вопросов:

Почему выше? Я не хочу сравнивать \s и .*. Я знаю разницу. Я хочу знать, почему затраты \s и .* различаются в зависимости от их положения в полном регулярном выражении. А затем характеристики регулярного выражения, которые могут стоить по-разному в зависимости от их положения в общем регулярном выражении (или на основе любого другого аспекта, кроме положения, если таковой имеется).
Дает ли счетчик шагов, данный на этом сайте, какие-либо указания о производительности регулярных выражений?
какие другие простые или похожие (связанные с положением) наблюдения за регулярными выражениями у вас есть?

Ответ 1

Механизмы регулярных выражений с квантором *, также как и жадный квантификатор, должны потреблять все на входе, которое соответствует, а затем:

попробуйте следующий термин в регулярном выражении. Если он совпадает, продолжайте
"unconsume" один символ (переместите указатель назад один), aka backtrack и перейти к шагу 1.

Так как . соответствует чему-либо (почти), первое состояние после столкновения с .* заключается в перемещении указателя в конец ввода, а затем начните перемещение назад через входной сигнал char за время, пробовав следующий термин пока не появится совпадение.

С \s* уничтожается только пробел, поэтому указатель изначально перемещается точно там, где вы хотите, - нет возврата к следующему члену.

Что-то, что вы должны попробовать, это использовать квантификатор неохотного .*?, который будет потреблять один char за один раз до следующего совпадения, который должен иметь такую же временную сложность, что и \s*, но быть немного более эффективным, не требуется проверка текущего char.

\s* и .* в конце выражения будут выполняться аналогичным образом, потому что оба будут потреблять все в конце ввода f, которое соответствует, что оставляет указатель равной позиции для обоих выражений.

Ответ 2

Из отладчика выводится следующее.

Большая причина разницы в производительности заключается в том, что .* будет потреблять все до конца строки (кроме новой строки). Затем шаблон продолжит, заставляя регулярное выражение возвращаться (как видно на первом изображении).

Причина, по которой \s и .* одинаково хорошо работает в конце шаблона, заключается в том, что жадный шаблон против потребляющего пробела не имеет никакого значения, если нет ничего другого (кроме WS).

Если ваша тестовая строка не заканчивается пробелами, будет разница в производительности, как вы видели в первом шаблоне - регулярное выражение будет вынуждено отступить.

ИЗМЕНИТЬ

Вы можете увидеть разницу в производительности, если закончите что-то помимо пробелов:

Плохо:

^myname.*mahesh.*hiworld

лучше:

^myname.*mahesh\s*hiworld

Еще лучше:

^myname\s*mahesh\s*hiworld