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

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), Это приводит к раннему провалу.

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

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

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