[Moscow.pm] Регулярные выражения. Помогите понять, почему так.
Sergey Aleynikov
sergey.aleynikov на gmail.com
Пт Окт 28 18:28:23 PDT 2016
Добрый день,
Базовым выражением, которое пытается сматчится, здесь будет
qr/(?:[^a-z]\s*?)+?r/. Оно не-матчится с экспоненциальной сложностью
относительно длины строки для движка pcre. И причина - не в
backreferenc'ах (их тут нет), а в backtracking'e. Поэтому, на "голом"
движке, несовпадение $regexp15 занимало бы столько же времени, сколько
и $regexp16. И даже $regexp1.
К счастью, для простых случаев перл оптимизацию содержит - если он
встречает определенный шаблон в выражении, то запоминает позиции,
начиная с которых совпадений точно не будет, что превращает поиск в
линейный. Проблема в том, что для определения того, к какой группе
относятся запомненные позиции, выделено всего 4 бита. И, собрав
достаточно длинную регулярку, выбирающую все уровни CURLYX/WHILEM
кэша, экспонента все-таки вылезет.
Посмотреть, как выглядит скомпилированная регулярка, может через perl
-Mre=debug -e 'qr/(?:[^a-z]\s*?)+?r/'. Инструкции с кэшом будут
выглядеть как WHILEM[1/1] (0), без кэша - как WHILEM (0).
Вывод - лучше не использовать 100% экспоненциальные для данного движка
регулярки, полагаясь на его оптимизации. Еще можно поменять движок, но
у них всех есть как ограничения, так и патологичекие случаи.
Best regards,
Sergey Aleynikov
28 октября 2016 г., 19:17 пользователь Loginoff Nick via Moscow-pm
<moscow-pm на pm.org> написал:
>
> Столкнулся с проблемой.
>
> В проекте есть список похожих регулярок (спам фильтр на домены, если
> точнее). Все регулярки сливаются в одну и потом идет матчинг.
> Появилась проблема, что скрипт начал подвисать. По результату, накидал
> небольшой тест:
>
> Если регулярок 15 шт, то даже при увеличении строки до 100 символов, они
> работают быстро.
> НО! Если регулярок 16 и более, то время увеличивается вдвое на каждое
> увеличение строки. Регулярка, которая совпадает, стоит последней в списке
>
> Пробовал на perl 5.10.1 и 5.8.8 и там и там работает так же.
>
> Вот код:
>
> #!/usr/bin/perl
>
> use strict;
> use warnings;
>
> use Time::HiRes;
>
> $| = 1;
>
> my $regexp15 = qr('
> (3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(2\s*?(?:[^a-z]\s*?)+?r)
> ');
>
> my $regexp16 = qr('
> (3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(3\s*?(?:[^a-z]\s*?)+?r)
> |(2\s*?(?:[^a-z]\s*?)+?r)
> ');
>
> print "Regexp 15:\n";
> my $str = "1 2";
> for (my $i=0;25>=$i;$i++) {
> $str .= " 1";
> my $start = Time::HiRes::gettimeofday();
> $str =~ $regexp15;
> print "$i. " . ( Time::HiRes::gettimeofday() - $start
> )."\t\t".$str."\n";
> }
>
> print "\n\nRegexp 16:\n";
> $str = "1 2";
> for (my $i=0;25>=$i;$i++) {
> $str .= " 1";
> my $start = Time::HiRes::gettimeofday();
> $str =~ $regexp16;
> print "$i. " . ( Time::HiRes::gettimeofday() - $start
> )."\t\t".$str."\n";
> }
>
>
> На выводе получаем вот это:
> Regexp 15:
> 0. 2.59876251220703e-05 1 2 1
> 1. 1.81198120117188e-05 1 2 1 1
> 2. 3.29017639160156e-05 1 2 1 1 1
> 3. 6.29425048828125e-05 1 2 1 1 1 1
> 4. 0.000128030776977539 1 2 1 1 1 1 1
> 5. 0.000234127044677734 1 2 1 1 1 1 1 1
> 6. 0.000262975692749023 1 2 1 1 1 1 1 1 1
> 7. 0.000327825546264648 1 2 1 1 1 1 1 1 1 1
> 8. 0.000325918197631836 1 2 1 1 1 1 1 1 1 1 1
> 9. 0.000358819961547852 1 2 1 1 1 1 1 1 1 1 1 1
> 10. 0.000417232513427734 1 2 1 1 1 1 1 1 1 1 1 1 1
> 11. 0.000411033630371094 1 2 1 1 1 1 1 1 1 1 1 1 1 1
> 12. 0.000481128692626953 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
> 13. 0.000468969345092773 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 14. 0.000528097152709961 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 15. 0.0005340576171875 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 16. 0.000589132308959961 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 17. 0.000611066818237305 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 18. 0.000608921051025391 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 19. 0.000670909881591797 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 20. 0.000718832015991211 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1
> 21. 0.00074005126953125 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1
> 22. 0.000860929489135742 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1
> 23. 0.000805854797363281 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1
> 24. 0.000832080841064453 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1 1
> 25. 0.000850915908813477 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1 1 1
>
> Regexp 16:
> 0. 9.05990600585938e-06 1 2 1
> 1. 1.69277191162109e-05 1 2 1 1
> 2. 3.31401824951172e-05 1 2 1 1 1
> 3. 6.29425048828125e-05 1 2 1 1 1 1
> 4. 0.000123023986816406 1 2 1 1 1 1 1
> 5. 0.000240087509155273 1 2 1 1 1 1 1 1
> 6. 0.000504970550537109 1 2 1 1 1 1 1 1 1
> 7. 0.000976085662841797 1 2 1 1 1 1 1 1 1 1
> 8. 0.00191593170166016 1 2 1 1 1 1 1 1 1 1 1
> 9. 0.00382804870605469 1 2 1 1 1 1 1 1 1 1 1 1
> 10. 0.00754117965698242 1 2 1 1 1 1 1 1 1 1 1 1 1
> 11. 0.0151779651641846 1 2 1 1 1 1 1 1 1 1 1 1 1 1
> 12. 0.0302209854125977 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
> 13. 0.0605261325836182 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 14. 0.120044946670532 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 15. 0.241585969924927 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 16. 0.482980012893677 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 17. 0.965275049209595 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 18. 1.93135094642639 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 19. 3.86527395248413 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 20. 7.74077796936035 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1
> 21. 15.4553070068359 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1
> 22. 30.9984660148621 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1
> 23. 61.9043700695038 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1
> 24. 124.614840984344 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1 1
> 25. 247.499380111694 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1 1 1
>
>
> --
> С Уважением, Login|off Nick или STork.
>
>
> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org
>
Подробная информация о списке рассылки Moscow-pm