Ответ 1
Я бы не стал полагаться ни на количество шагов, ни на какую-либо отладку как тест
либо отступления, либо сбой.
Как правило, избегайте простых конструкций, таких как (A+)*, что не только
backtrack внутренний A+, но также возвращает outter (..)*.
Каждый проход наружу дает новую (новую) внутреннюю серию возврата.
Получите хорошее тестовое программное обеспечение, например RegexFormat
и проверите серию для экспоненциального результата времени.
Линейный результат - это то, что вы ищете, так как контент увеличивается тем же
количество.
Ниже приведен пример (A+)? vs (A+)*. Мы установили цель для известного отказа
и неуклонно увеличивать длину, чтобы продлить обработку этого отказа.
Если вы посмотрите на regex 2 (A+)*, вы можете заметить экспоненциальное увеличение просто
увеличивается три цели.
Наконец, мы продуваем цель, чтобы перегрузить внутренние ресурсы двигателя.
Изменить. После некоторого анализа я публикую небольшой вывод о шагах возврата.
При анализе контрольного времени, приведенного ниже, обратное отслеживание, по-видимому, является процессом 2 ^ N.
Где N - количество символов, которые возвращаются с ошибкой.
Учитывая простой случай Revo, немного легче изолировать откат.
Потому что это похоже на то, что% 98 от общего времени занимает просто откат.
Учитывая это предположение, можно взять результаты времени из 2 точек и сгенерировать уравнение.
Форма используемого уравнения была f(x) = a * r^x.
Приведенные координаты (# из "А против времени" ), используя точки
(7, 1.13), (9, 4.43), которые порождали это f(x) = 0.009475 * 1.9799 ^ x
что на самом деле это # sec = 0.009475 * 1.9799 ^ # letters
Я запустил все количество букв "А" из приведенного ниже теста в эту формулу.
#LTR Bench Time
7 1.13
9 4.43
13 70.51
который произвел точное контрольное время (+/-.1%).
Затем я увидел, что 1.9799 довольно близко к 2.0, поэтому я скорректировал коэффициент "a" до 0,009 и снова запустил его, получив следующее:
f(7 letters) = 2 ^ 7 * .009 = 1.152 sec’s
f(9 letters) = 2 ^ 9 * .009 = 4.608 sec’s
f(13 letters) = 2 ^ 13 * .009 = 73.728 sec’s
f(27 letters) = 2 ^ 27 * .009 = 1207959.552 sec’s = 335 hours
Теперь кажется довольно ясным, что шаги отступания коррелируют с числом буквы для возврата в соотношении 2 ^ N.
Я также считаю, что это справедливая ставка, что некоторые двигатели могут сделать эту простую математику 2 ^ N
только в простом сценарии, подобном этому. Кажется, это время, когда
двигатель немедленно возвращается и говорит Слишком сложно!.
Перевод здесь состоит в том, что регулярное выражение достаточно простое, чтобы движок мог
обнаружить его. В других случаях двигатель никогда не возвращается,
он висел, и может вернуться через год или два (или десять...).
Заключение, следовательно, не в том, что двигатель отступит, но будет, но как будет ли ваша целевая строка влиять на обратную трассировку.
Таким образом, бдительность требуется при написании регулярного выражения и должна быть настороже против
вложенных открытых кванторов.
Я бы сказал, что лучший выбор - всегда сильно ударить по регулярному выражению, чтобы он не получился.
И я говорю о чрезмерных повторяющихся литералах в подозрительных местах.
end edit
Цель: AAAAAAAC
Контрольная точка
Regex1: ^(A+)?B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 0.07 s, 72.04 ms, 72040 µs
Regex2: ^(A+)*B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 1.13 s, 1126.44 ms, 1126444 µs
Цель: AAAAAAAAAC
Контрольная точка
Regex1: ^(A+)?B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 0.08 s, 82.43 ms, 82426 µs
Regex2: ^(A+)*B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 4.43 s, 4433.19 ms, 4433188 µs
Цель: AAAAAAAAAAAAAC
Контрольная точка
Regex1: ^(A+)?B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 0.10 s, 104.02 ms, 104023 µs
Regex2: ^(A+)*B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 70.51 s, 70509.32 ms, 70509321 µs
Цель: AAAAAAAAAAAAAAAAAAAAAAAAAAAC
Контрольная точка
Regex1: ^(A+)?B
Options: < none >
Completed iterations: 50 / 50 ( x 1000 )
Matches found per iteration: 0
Elapsed Time: 0.18 s, 184.05 ms, 184047 µs
Regex2: ^(A+)*B
Options: < none >
Error: Regex Runtime Error !!
Completed iterations: 0 / 50 ( x 1000 )
Matches found per iteration: -1
Elapsed Time: 0.01 s, 7.38 ms, 7384 µs
Error item 2 : Target Operation ..
The complexity of matching the regular expression exceeded predefined
bounds. Try refactoring the regular expression to make each choice made by
the state machine unambiguous. This exception is thrown to prevent
"eternal" matches that take an indefinite period time to locate.