Хронометраж времени выполнения регулярных выражений
В поставке 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. Все права защищены. |
