Можно ли простой и вроде невинной регуляркой убить систему? Да, можно.
Например:
>>> r = '(a+)*b'
Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем:
>>> re.findall('(a+)*b', 'aaaaaab')
['aaaaaa']
Круто, работает, пошли пить пиво.
А нет…
Если строка, в которой ищем, не будет содержать искомого паттерна, например просто 'aaaaaa', компилятор будет пробовать найти её следующим алгоритмом:
1. Вся стока удовлетворяет 'a+', но мы не находим 'b', шаг назад.
2. Теперь 'a+' удовлетворяет только 'aaaaa' (все, кроме последней), последняя удовлетворяет повтору '*', 'b' все равно не находим, шаг назад.
3. Первое 'a+' удовлетворяет только 'aaaa', последние два 'aa' удовлетворяют повтору '*', 'b' все равно не находим, шаг назад.
4. Первое 'a+' удовлетворяет 'aaaa', предпоследняя 'a' удовлетворяет одному повтору '*', следующая 'a' еще одному повтору '*', 'b' так и не находиться…
Ну Вы поняли — и так далее. Вплоть до полного перебора строки.
Немного статистики:
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*20)", number=1)
0.24741506576538086
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*22)", number=1)
0.99283289909362793
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*24)", number=1)
3.9849259853363037
Как видим, время исполнения растет экспоненциально. Для бОльших строк Python 2.6 на FreeBSD своевременно выкидывает RuntimeError, но на Windows тот самый Python бодренько перебирает все комбинации. Строки больше 30 символов не рискнул тестировать :)
Оригинал статьи можно найти тут
Например:
>>> r = '(a+)*b'
Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем:
>>> re.findall('(a+)*b', 'aaaaaab')
['aaaaaa']
Круто, работает, пошли пить пиво.
А нет…
Если строка, в которой ищем, не будет содержать искомого паттерна, например просто 'aaaaaa', компилятор будет пробовать найти её следующим алгоритмом:
1. Вся стока удовлетворяет 'a+', но мы не находим 'b', шаг назад.
2. Теперь 'a+' удовлетворяет только 'aaaaa' (все, кроме последней), последняя удовлетворяет повтору '*', 'b' все равно не находим, шаг назад.
3. Первое 'a+' удовлетворяет только 'aaaa', последние два 'aa' удовлетворяют повтору '*', 'b' все равно не находим, шаг назад.
4. Первое 'a+' удовлетворяет 'aaaa', предпоследняя 'a' удовлетворяет одному повтору '*', следующая 'a' еще одному повтору '*', 'b' так и не находиться…
Ну Вы поняли — и так далее. Вплоть до полного перебора строки.
Немного статистики:
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*20)", number=1)
0.24741506576538086
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*22)", number=1)
0.99283289909362793
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*24)", number=1)
3.9849259853363037
Как видим, время исполнения растет экспоненциально. Для бОльших строк Python 2.6 на FreeBSD своевременно выкидывает RuntimeError, но на Windows тот самый Python бодренько перебирает все комбинации. Строки больше 30 символов не рискнул тестировать :)
Оригинал статьи можно найти тут
Комментарии
Отправить комментарий