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

Question

m/.+?(\d{4})<\/i>\)/s

Вышеупомянутое регулярное выражение медленно, когда я запускаю его на некоторых HTML-страницах нормального размера? Зачем? Я бы не подумал, что это должно продолжаться медленно.

EDIT: Вот пример кода, который демонстрирует проблему:

use WWW::Mechanize; 
my $mech = new WWW::Mechanize; 
$mech->get("http://www.elaws.gov.bw/desplaysubsidiary.php?m=SUBSIDIARY&v=I&vp=&id=904"); 
$page = $mech->content(); 
$page =~ m/.+?(\d{4})<\/i>\)/s; 

Регулярное выражение линия берет навсегда. Если я удалю .+?, нет задержки.

Answer 1

Это регулярное выражение медленно, потому что вы вводите ленивость в . с +?. Для 20-минутного html-привет мир он поднимает шаги с 60 (когда жадные) до 2000 (когда ленивый).

Представьте, что он будет делать с "некоторые нормальные HTML-страницы формата". Вы можете проверить here (под отладчик regex).

Также взгляните на why you shouldn't use regex to parse html.

Answer 2

Там, кажется, какое-то недоразумение об этом

Предположим, что у нас есть строка

my $s = 'xxxxxxxxxx9999</i>)'; 

затем шаблон совпадающий как этот

$s =~ m<.*?(\d{4})</i>\)> 

начнется, если предположить, что .*? занимает нет символов в начале строки. Затем он проверяет, соответствует ли (\d{4})</i>\) строке в этой точке

Он не работает, поэтому двигатель регулярного выражения дает один символ x до .*? и повторяет попытку. Это также терпит неудачу, поэтому часть строки, потребляемая .*?, расширена по-символу, пока она не соответствует десяти символам xxxxxxxxxx.В этот момент остаток шаблона соответствует успешно и тесту регулярного выражения объявляется успехом

Если вместо этого у нас есть, не ленив рисунок на

$s =~ m<.*(\d{4})</i>\)> 

Это запустит в предположении, что .* занимает все строки

Остальная часть рисунка не соответствует в этой точке, поэтому откат начинается за раз, давая .* все, кроме одного символа строки и повторите попытку

Это повторяется, как и раньше, но сокращение матча характер за символом, пока не будет найдено совпадение, когда он отступал над задними девяти символами строки 9999</i>) и .* теперь соответствует xxxxxxxxxx, как и раньше

Backtracking: Назад к ранее подобранному элементу шаблона, когда совпадение было найдено с ошибкой, изменяя, как этот элемент совпадает и повторяет попытку. Это не будет назад через объект строку ищет что-то

Проблема здесь вызвана .*?, которая должна учитываться в шаблоне. Если бы у нас было только m<(\d{4})</i>\)>, тогда вообще никакого возврата нет. Движок регулярных выражений просто ищет \d{4}</i>\) и либо находит, либо не

Это прекрасно работает до тех пор, как это первого появление узора, который вы хотите. К сожалению, единственный способ найти последнее вхождение подстроки является перед ним .*, который стартует возвратов и делает процесс обязательно медленнее

выше регулярное выражение медленно, когда я запускаю его через некоторый нормальный размер HTML-страниц?

Несмотря на это, в зависимости от того, какова ваша идея «HTML-страниц нормального размера», я не вижу, чтобы это заняло больше нескольких миллисекунд. Двигатель регулярных выражений закодирован в C и написан очень быстро. Думаю, вы должны запустить таймер, чтобы заметить какую-либо задержку?