регулярное выражение занимает много времени

Question

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

use warnings;
use strict;
use LWP::Simple;

my $content=get('http://mytempscripts.com/2011/09/temporary-post.html') or die $!;
$content=~s/\n//g;
$content=~s/ / /g;
$content=~/<b>this is a temp post<\/b><br \/><br \/>(.*?)<div style='clear: both;'><\/div>/;
my $temp=$1;


while($temp=~/((.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9]    {1,})(.*?)\s+)/g){
print "found a match\n";
}

Это работает, но занимает много времени.Когда я сокращаю регулярное выражение до следующего, я получаю результаты менее чем за секунду.Почему мое оригинальное регулярное выражение занимает столько времени?Как мне это исправить?

while($temp=~/((.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9]    {1,})(.*?)\s+)/g){
print "found a match\n";
}

Answer 1

Регулярные выражения похожи на функцию sort в Perl. Вы думаете, что это довольно просто, потому что это всего лишь одна команда, но, в конце концов, она использует много вычислительной мощности для выполнения этой работы.

Есть некоторые вещи, которые вы можете сделать, чтобы помочь:

1. Сохраняйте синтаксис максимально простым.
2. Прекомпилируйте ваш шаблон регулярного выражения, используя qr //, если вы используете это регулярное выражение в цикле. Это избавит Perl от необходимости компилировать ваше регулярное выражение с каждым циклом.
3. Старайтесь избегать синтаксиса регулярных выражений, который должен возвращать . Это обычно заканчивается тем, что самые общие подходящие шаблоны (такие как .*).

Жалкая правда в том, что после десятилетий написания на Perl я никогда не постигал глубокие темные секреты парсинга регулярных выражений. Я много раз пытался это понять, но обычно это означает исследование в Интернете, и ... ну ... меня отвлекают все остальные вещи в Интернете.

И, это не так уж и сложно, любой наполовину приличный разработчик с IQ 240 и склонностью к садизму должен легко уметь его поднять.

---

@ Дэвид У .: Думаю, я не уверен в том, что возвращаюсь назад Мне пришлось читать вашу ссылку несколько раз, но я все еще не совсем понимаю, как реализовать ее (или не реализовать) в моем случае. - user522962

Давайте рассмотрим простой пример:

my $string = 'foobarfubar';
$string =~ /foo.*bar.*(.+)/;
my $result = $1;

Что будет $result? Это будет r. Вы видите, как это работает? Посмотрим, что получится.

Изначально регулярное выражение разбивается на токены, и используется первый токен foo.*. Это на самом деле соответствует всей строке:

"foobarfubar" =~ /foo.*/

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

"foobarfubar" =~ /foo.*/    #/bar.*/ doesn't match
"foobarfuba" =~ /foo.*/     #/bar.*/ doesn't match.
"foobarfub" =~ /foo.*/      #/bar.*/ doesn't match.
"foobarfu" =~ /foo.*/       #/bar.*/ doesn't match.
"foobarf" =~ /foo.*/        #/bar.*/ doesn't match.
"foobar" =~ /foo.*/         #/bar.*/ doesn't match.
 ...
"foo" =~ /foo.*/            #Now /bar.*/ can match!

Теперь то же самое происходит с остальной частью строки:

"foobarfubar" =~ /foo.*bar.*/  #But the final /.+/ doesn't match
"foobarfuba"  =~ /foo.*bar.*/  #And the final /.+/ can match the "r"!

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

Надеюсь, это поможет объяснить возвращение.

Проблема, с которой вы сталкиваетесь, не в том, что ваша программа не работает, а в том, что она занимает много времени.

Я надеялся, что суть моего ответа в том, что синтаксический анализ регулярных выражений не так прост, как это делает Perl. Я могу видеть команду sort @foo; в программе, но забыть, что если @foo содержит миллион или около того записей, это может занять некоторое время. Теоретически, Perl мог бы использовать пузырьковую сортировку, и таким образом алгоритм представляет собой O ² . Я надеюсь, что Perl на самом деле использует более эффективный алгоритм, и мое фактическое время будет ближе к O * log (O). Однако все это скрыто моим простым однострочным утверждением.

Я не знаю, является ли проблема обратного отслеживания в вашем случае, но вы рассматриваете вывод всей веб-страницы как одну строку, чтобы сопоставить ее с регулярным выражением, что может привести к очень длинной строке. Вы пытаетесь сопоставить его с другим регулярным выражением, которое вы делаете снова и снова. По-видимому, это довольно трудоемкий шаг, который скрыт тем фактом, что это один оператор Perl (так же, как sort @foo скрывает его сложность).

Думая об этом время от времени, вы не должны пытаться анализировать HTML или XML с помощью регулярных выражений, потому что это так небрежно. В результате вы получаете что-то довольно неэффективное и хрупкое.

В подобных случаях может быть лучше использовать что-то вроде HTML :: Parser или XML :: Simple , с которым я более знаком, но не обязательно с ним работаю плохо отформатированный HTML.

Регулярные выражения Perl хороши, но они могут легко выйти из-под нашего контроля.

Answer 2

Одна вещь, которую вы можете попробовать, - это изменить все группы захвата (...) на группы без захвата (?: ...)

Это сэкономит некоторые усилия для сопоставителя, если все, что вам нужно, это распечатать «найдено совпадение», но я не уверен, что вы можете сделать это в реальности, если ваш реальный код сделает больше.

Также, вообще говоря, наличие большого количества символов подстановки, таких как (. *?), Просто прибавит веса, я думаю, поэтому, возможно, зная, что вы пытаетесь сопоставить, вы сможете устранить некоторые из них? Я не могу сказать наверняка; здесь не вижу чисто формальных оптимизаций.