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

       

Хронометраж времени выполнения регулярных выражений


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

use Benchmark; … my $t1=new Benchmark;

# Здесь находится участок кода, время работы которого измеряется …

my $t2=new Benchmark; print timestr(timediff $t2,$t1);

В переменной $t1 запоминается время начала исполнения участка кода, в переменной $t2 запоминается время окончания выполнения этого участка кода. Затем с помощью функций timediff и timestr выводится разница между временем окончания и временем начала работы участка кода, который тестируется. Но не забывайте, что при первом обращении к регулярному выражению тратится время на его компиляцию!

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

$_=' <pppp>' x 13000; $_.='<table>a'; my $re=qr /\A # начало текста (?> # атомарная группировка (?: # цикл пропуска пробелов и тегов (?>\s*) # пропускаем пробельные символы <(?>[^>]*)> # пропускаем тег с его содержимым )* # повтор любое число раз ) \S # и вот он наконец - непробельный символ /x; my $t1=new Benchmark; for (1..1000000) { /$re/; } my $t2=new Benchmark; print timestr(timediff $t2,$t1);

В этом примере избран такой подход: в цикле (?: … )* пропускаются пробельные символы и теги, а после окончания цикла таких пропусков должен встретиться непробельный символ \S. Если он встретится, то поиск завершится удачей. В переменной $_ создается длинная строка с тегами и пробелами, которая завершается непробельным символом a вне тегов. Чтобы время компиляции регулярного выражения> не вошло в интересующий нас интервал времени, мы используем объект регулярного выражения $re. Поскольку регулярное выражение работает быстро, создаем цикл из миллиона повторов применения этого регулярного выражения к тексту.

При прогоне этой программы на моем компьютере выводится следующее значение времени выполнения заданного участка кода:

1 wallclock secs ( 1.11 usr + 0.00 sys = 1.11 CPU)


А если этот символ стоит вне тегов, то такого текста найдено не будет, поэтому будет истинен шаблон

(?![^<>]*>)

Вот вся эта программа:

use Benchmark;

$_=' <pppp>' x 13000; $_.='<table>a'; my $re=qr /[^\s<>] (?![^<>]*>) /x; my $t1=new Benchmark; for (1..1000000) { /$re/; } my $t2=new Benchmark; print timestr(timediff $t2,$t1);

На печати получаем:

1 wallclock secs ( 1.09 usr + 0.00 sys = 1.09 CPU)

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

Теперь узнаем, в какую цену обходится встроенный код Perl. Добавим в последний пример встроенный код, который будет увеличивать счетчик:

use Benchmark;

$_=' <pppp>' x 13000; $_.='<table>a'; my $count=0; my $re=qr /[^\s<>] (?![^<>]*>) (?{ ++$count }) /x; my $t1=new Benchmark; for (1..1000000) { /$re/; } my $t2=new Benchmark; print timestr(timediff $t2,$t1); print "\n$count";

На печати появится:

3 wallclock secs ( 3.44 usr + 0.00 sys = 3.44 CPU) 1000000



Время выполнения увеличилось примерно в 3 раза. Сравним это со временем выполнения самого кода автоприращения:

use Benchmark;

my $count=0; my $t1=new Benchmark; for (1..1000000) { ++$count } my $t2=new Benchmark; print timestr(timediff $t2,$t1); print "\n$count";

Напечатается

0 wallclock secs ( 0.13 usr + 0.00 sys = 0.16 CPU) 1000000

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

Далее рассмотрим ресурсоемкость динамического регулярного выражения. Для этого вернемся к примеру из лекции 12 и переделаем его для наших нужд:

use Benchmark;

$_='Далее стоит 13 нулей: 0000000000000' x 13000; my $re=qr/(\d+)\D+(??{"0{$1}"})/; my $t1=new Benchmark; for (1..1000000) { /$re/; } my $t2=new Benchmark; print timestr(timediff $t2,$t1);



Напечатается

4 wallclock secs ( 4.74 usr + 0.00 sys = 4.74 CPU)

А сейчас заменим динамическое регулярное выражение подшаблоном \d+:

use Benchmark;

$_='Далее стоит 13 нулей: 0000000000000' x 13000; my $re=qr /(\d+)\D+\d+/; my $t1=new Benchmark; for (1..1000000) { /$re/; } my $t2=new Benchmark; print timestr(timediff $t2,$t1);

В этот раз время уменьшится:

1 wallclock secs ( 1.38 usr + 0.00 sys = 1.38 CPU)

Замечаем, что встроенный код и динамические регулярные выражения даже в простом случае увеличивают время выполнения регулярного выражения примерно в 3 раза.

Аналогично заметно возрастает время выполнения оператора подстановки s/// с модификатором e. Были практические случаи, когда оператор подстановки с модификатором e замедлял работу программы в десятки раз.

© 2003-2007 INTUIT.ru. Все права защищены.

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