Почему выполнение этого регулярного выражения занимает много времени?

Question

Я обнаружил, что, например, эта строка имеет очень и очень большое время выполнения:

System.out.println(
        ".. .. .. .. .. .. .. .. ..  .. .. .. .. .. .. .. .. .. .. .. .... .. .."
        .matches("(?i)(?:.* )?\\W?([a-z0-9-_\\.]+((?: *)\\.(?: *))+(?:DE))(?:[0-9]{1,5})?")
);

Если я уменьшу количество точек в начале строки, время выполнения уменьшится (кажется,это экспоненциально).Вот трассировка стека приостановленного потока:

[Repeating text]...
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4279
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Loop.match(Matcher, int, CharSequence) line: 4785
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4279
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Single(Pattern$BmpCharProperty).match(Matcher, int, CharSequence) line: 3798
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Loop.match(Matcher, int, CharSequence) line: 4785
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Single(Pattern$BmpCharProperty).match(Matcher, int, CharSequence) line: 3798
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4279
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Loop.matchInit(Matcher, int, CharSequence) line: 4801
Pattern$Prolog.match(Matcher, int, CharSequence) line: 4741
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Ques.match(Matcher, int, CharSequence) line: 4182
Pattern$BranchConn.match(Matcher, int, CharSequence) line: 4568
Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717
Pattern$Single(Pattern$BmpCharProperty).match(Matcher, int, CharSequence) line: 3798
Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272
Pattern$Curly.match(Matcher, int, CharSequence) line: 4234
Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658
Pattern$Branch.match(Matcher, int, CharSequence) line: 4604
Matcher.match(int, int) line: 1270
Matcher.matches() line: 604
Pattern.matches(String, CharSequence) line: 1135
String.matches(String) line: 2121
Main.main(String[]) line: 11

Почему это происходит?

Answer 1

Когда шаблон x сделан необязательным - с использованием квантификаторов ? или * (или {0,}) - двигатель имеет два пути приближения в соответствии с природой используемого квантификатора:

• Потребляет затем возврат к другим шаблонам (случай жадности, т. Е. .*, .?)
• Сначала не потребляет и сразу ищет другие шаблоны (случай лени .*?)

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

Сложность времени начинается с O(n) и продолжается с O(n^2b), где b - уровень вложенности квантификаторов.Таким образом, в случае отказа число шагов, которое делает двигатель, ОГРОМНО.

Чтобы избежать таких ситуаций, кто-то должен рассмотреть некоторые руководящие принципы:

• Указание границ.Если шаблон должен остановиться где-то до того, как цифры не делают .*.Вместо этого выполните \D*.

• Условия использования.Вы можете проверить, существует ли шаблон / буква x, прежде чем запускать целое совпадение, используя запрос ^(?=[^x]*x)Это приводит к раннему отказу.

• Используйте квантификаторы притяжений или атомные группы (если доступны).Эти двое избегают возврата.Иногда вам не нужны возвраты.

• Не выполняйте (.*)+ или аналогичные схемы.Вместо этого пересмотрите ваши требования или, по крайней мере, используйте атомные группы (?>.*)+.

Ваше собственное регулярное выражение не является исключением.Он страдает от большой жадности и необязательных совпадений и требует времени для восстановления.