Регулярные выражения Perl и их применение

       

Встроенный код и оптимизация регулярных выражений


Мы уже имели возможность убедиться в полезности встроенного кода при выводе текущей позиции поиска и содержимого специальных переменных, изменяемых при поиске. Встроенный код также необходим во время отладки и ускорения работы регулярного выражения. Часто программист не подозревает, сколько лишней работы производят его конструкции внутри регулярного выражения.

Для примера рассмотрим программу, которая ищет и печатает даты в формате Jan 13 2007, Apr 5 2007 и т.д. Вот такая программа, которая сразу приходит в голову:

$_='Дата1 Jan 13 2007, дата2 Apr 5 2007'; while (/(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)(?:\s+\d+){2}/g) { print "Нашла дату $&\n"; }

Программа выдает:

Нашла дату Jan 13 2007 Нашла дату Apr 5 2007

Но задумаемся, как она производит поиск. Чтобы найти месяц, наша программа к каждому символу исходного текста применяет конструкцию выбора со всеми 12-ю месяцами. И как правило, безуспешно, а это значит, что все 12 имен месяцев сравниваются с каждым символом исходной строки, кроме двух. На нашем небольшом примере не заметно, что программа тратит на работу слишком много времени, но если это регулярное выражение будет обрабатывать десятки мегабайтов текстов, это станет видно.

Для любопытства вставим распечатку текущей позиции поиска в начало регулярного выражения:

$_='Дата1 Jan 13 2007, дата2 Apr 5 2007'; while (/(?{print pos($_).' '})(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec) (?:\s+\d+){2}/g) { print "\nНашла дату $&\n"; }

Получим на выходе

0 1 2 3 4 5 6 Нашла дату Jan 13 2007 17 18 19 20 21 22 23 24 25 Нашла дату Apr 5 2007

Вот столько раз (и как правило, безуспешно) эта программа применяет затратную конструкцию выбора.

Сделаем оптимизацию по начальному символу месяца - соберем все начальные символы в класс:

$_='Дата1 Jan 13 2007, дата2 Apr 5 2007'; while (/(?=[ADFJMNOS])(?{print pos($_).' '}) (?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)(?:\s+\d+){2}/g) { print "\nНашла дату $&\n"; }

(В этом тексте длинная строка могла быть перенесена на символе пробела.)

Теперь альтернативный подшаблон будет работать, только если в тексте встретится один из символов ADFJMNOS. Класс по-прежнему будет применяться к каждому очередному символу, но классы работают гораздо быстрее альтернатив. В итоге программа напечатает

6 Нашла дату Jan 13 2007 25 Нашла дату Apr 5 2007

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



Содержание раздела