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

Компиляция регулярных выражений, модификатор o, функция study, хронометраж

Разбить на страницы
Показывать лекцию целиком

13.1. Компиляция и кэширование регулярных выражений

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

При компиляции сначала происходит обработка литералов регулярного выражения.

  • Отыскивается завершающий ограничитель регулярного выражения и читаются модификаторы всего регулярного выражения, которые стоят за этим ограничителем. Наличие модифиатора x учитывается при обработке литерала регулярного выражения.
  • Если регулярное выражение имеет интерполируемые переменные, то вместо них подставляется их значение. При этом учитывается, что последовательности символов $|, $), … не являются переменными и не интерполируются.
  • Далее обрабатываются конструкции изменения регистра /U, /l, … а также конструкции /Q…/E, но в тех частях регулярного выражения, которые получились от интерполяции переменных, эти конструкции не распознаются и не обрабатываются.
    •

    Потом, если не было замечено ошибок на шагах 1-3, регулярное выражение переводится в свою внутреннюю форму, готовую к применению механизмом регулярных выражений.

    Но регулярное выражение может применяться в цикле, что при каждой его компиляции потребует существенных затрат времени процессора. Perl запоминает внутреннее представление регулярного выражения после его компиляции и привязывает его к соответствующему регулярному выражению в программе. В последующем при обращении к данному регулярному выражению повторной компиляции не происходит, а используется его готовое внутреннее представление. Это кэширование регулярного выражения делается для регулярных выражений, которые не содержат интерполируемых переменных или имеют модификатор o. Переменные, содержащиеся во встроенном коде, и динамические регулярные выражения на кэширование регулярного выражения не влияют, поскольку не интерполируются, а входят в исполняемый код, который не изменяется между обращениями к данному регулярному выражению. Кэш регулярных выражений имеет ограниченные возможности, поэтому кэшируются лишь десять регулярных выражений, которые использовались последними (хотя в точности этого числа кэшируемых регулярных выражений я не уверен).

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

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

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

    my $a='abc';
my $b='cde';
my $re='(\w)';
$a =~ /$re/;
print "$1\n";
$b =~ //;
print $1;

    На печать выводится

    a
c

    Пояснение: в операторе $a =~ /$re/; мы использовали регулярное выражение, которое совпало, и напечаталась буква a. Далее мы можем множество раз задавать пустое регулярное выражение //. Вместо него будет использоваться это последнее совпавшее кэшированное регулярное выражение. Это видно при печати буквы c. Если теперь изменить содержимое переменной $re, то это не повлияет на результат применения пустого регулярного выражения, потому что интерполированное значение переменной $re (т.е. внутреннее представление литерала (\w) ) уже находится в кэшированном регулярном выражении по умолчанию).

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

    Если оператор поиска или замены не содержит ничего кроме объекта регулярного выражения:

    my $re=/…/;
…
if ($_ =~ $re) …
или
if (m/$re/) …

    то в этом операторе напрямую применяется откомпилированный объект регулярного выражения.

    Здесь уместно вспомнить об опасности применения модификатора o с объектами регулярных выражений:

    my $re=/…/o;

    который дает неожиданный и неприятный эффект, описанный ранее.

    13.2. Отладочная информация регулярных выражений

    Если применить директиву

    use re qw(debug);

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

    use re qw(debug);

'abcd' =~ /abc(d)/;

    На печать будет выдано:

    Compiling REx `abc(d)'
size 9 Got 76 bytes for offset annotations.
first at 1
   1: EXACT <abc>(3)
   3: OPEN1(5)
   5:   EXACT <d>(7)
   7: CLOSE1(9)
   9: END(0)
anchored `abcd' at 0 (checking anchored) minlen 4
Offsets: [9]
        1[3] 0[0] 4[1] 0[0] 5[1] 0[0] 6[1] 0[0] 7[0]
Guessing start of match, REx `abc(d)' against `abcd'...
Found anchored substr `abcd' at offset 0...
Guessed: match at offset 0
Matching REx `abc(d)' against `abcd'
  Setting an EVAL scope, savestack=3
   0 <> <abcd>            |  1:  EXACT <abc>
   3 <abc> <d>            |  3:  OPEN1
   3 <abc> <d>            |  5:  EXACT <d>
   4 <abcd> <v            |  7:  CLOSE1
   4 <abcd> <>            |  9:  END
Match successful!
Freeing REx: `"abc(d)"'

    Текст

    1: EXACT <abc>(3)
   3: OPEN1(5)
   5:   EXACT <d>(7)
   7: CLOSE1(9)
   9: END(0)

    является расшифровкой внутреннего представления регулярного выражения. Например, строка

    1: EXACT <abc>(3)

    означает, что надо искать строковый литерал abc длиной 3 символа. Строка

    anchored `abcd' at 0 (checking anchored) minlen 4

    означает, что текст abcd длины 4 привязан к началу регулярного выраения и должен встретиться при любом совпадении. Поэтому, если целевой текст окажется короче этого текста, то Perl не станет применять регулярное выражение, оператор поиска без применения сразу возвратит неудачу. Строка

    3: OPEN1(5)

    означает, что открылась первая захватывающая скобка, 5 означает номер следующей исполняемой строки псевдокода.

    13.3. Функция study

    Функция

    study( переменная с целевым текстом )

    является еще одной возможностью оптимизации использования регулярных выражений.

    Эта функция создает в переменной с целевым текстом скрытую информацию о тексте, который содержит эта переменная. Это список позиций, в которых каждый символ встречается в данном тексте. В результате на построение этого списка позиций расходуется время и память, которая обычно превосходит в четыре раза объем памяти для текста этой переменной. Поэтому выигрыша во времени можно не получить вовсе, если применять функцию study не там, где нужно. Функция study может существенно ускорить поиск, если в регулярном выражении имеется литеральный текст, но модификатор i сводит на нет усилия функции study. Также функция study может оказаться полезной, если к одной и той же переменной применяется много операторов с регулярными выражениями или если целевой текст имеет большой объем. При любом присваивании значения переменной, содержащей целевой текст, внутренняя информация, привязанная к этой переменной, становится недействительной.

    Для применения оптимизаций, которые возможны с функцией study, надо стараться выделять литеральный текст. Например, вместо

    a+

    надо написать эквивалентный подшаблон

    aa*

    а вместо

    a{3,6}

    нужно записать

    aaa{0,3}

    Если конструкция выбора ( альтернативный шаблон ) в каждой ветви начинается с одного и того же литерала, то его надо "вынести за скобку" и, к примеру, вместо

    that|this

    записать

    th(?:at|is)

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

    В поставке 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)

    Итак, это регулярное выражение тратит 1.11 секунды на миллион повторов цикла. (Кстати, на компиляцию этого регулярного выражения тратится 0.02 секунды, что намного больше, чем тратится на его выполнение для 90000 символов.)

    Теперь давайте уберем атомарную группировку:

    $_=' <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);

    Распечатка времени показывает, что программа стала работать быстрее и теперь тратит всего 1.08 секунды. Это можно понять так: зачем трудиться по уничтожению сохраненных состояний, когда регулярное выражение заканчивается? Если убрать атомарные скобки вокруг подшаблона \s*, то регулярное выражение начиает работать еще немного быстрее. Но здесь все зависит от данных, которые обрабатывает это регулярное выражение. В нашем случае пробелов мало, они встречаются по одному, а если группы пробелов будут большими, то в этом случае уничтожение состояний для подшаблона \s* может пригодиться. Кроме того, у нас нет возвратов при переборе. Если убрать последнюю атомарную группировку:

    /\A				# начало текста
        (?:			# цикл пропуска пробелов и тегов
            \s*			# пропускаем пробельные символы
            <[^>]*>	        # пропускаем тег с его содержимым
        )*			# повтор любое число раз
    \S				# и вот он наконец - непробельный символ
/x;

    то время выполнения участка кода практически не изменится и станет равным 1.03 секунды.

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

    (?=[^<>]*>)

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

    (?![^<>]*>)

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

    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 замедлял работу программы в десятки раз.

    Страницы:

    13.1. Компиляция и кэширование регулярных выражений

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

    При компиляции сначала происходит обработка литералов регулярного выражения.

  • Отыскивается завершающий ограничитель регулярного выражения и читаются модификаторы всего регулярного выражения, которые стоят за этим ограничителем. Наличие модифиатора x учитывается при обработке литерала регулярного выражения.
  • Если регулярное выражение имеет интерполируемые переменные, то вместо них подставляется их значение. При этом учитывается, что последовательности символов $|, $), … не являются переменными и не интерполируются.
  • Далее обрабатываются конструкции изменения регистра /U, /l, … а также конструкции /Q…/E, но в тех частях регулярного выражения, которые получились от интерполяции переменных, эти конструкции не распознаются и не обрабатываются.
    •

    Потом, если не было замечено ошибок на шагах 1-3, регулярное выражение переводится в свою внутреннюю форму, готовую к применению механизмом регулярных выражений.

    Но регулярное выражение может применяться в цикле, что при каждой его компиляции потребует существенных затрат времени процессора. Perl запоминает внутреннее представление регулярного выражения после его компиляции и привязывает его к соответствующему регулярному выражению в программе. В последующем при обращении к данному регулярному выражению повторной компиляции не происходит, а используется его готовое внутреннее представление. Это кэширование регулярного выражения делается для регулярных выражений, которые не содержат интерполируемых переменных или имеют модификатор o. Переменные, содержащиеся во встроенном коде, и динамические регулярные выражения на кэширование регулярного выражения не влияют, поскольку не интерполируются, а входят в исполняемый код, который не изменяется между обращениями к данному регулярному выражению. Кэш регулярных выражений имеет ограниченные возможности, поэтому кэшируются лишь десять регулярных выражений, которые использовались последними (хотя в точности этого числа кэшируемых регулярных выражений я не уверен).

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

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

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

    my $a='abc';
my $b='cde';
my $re='(\w)';
$a =~ /$re/;
print "$1\n";
$b =~ //;
print $1;

    На печать выводится

    a
c

    Пояснение: в операторе $a =~ /$re/; мы использовали регулярное выражение, которое совпало, и напечаталась буква a. Далее мы можем множество раз задавать пустое регулярное выражение //. Вместо него будет использоваться это последнее совпавшее кэшированное регулярное выражение. Это видно при печати буквы c. Если теперь изменить содержимое переменной $re, то это не повлияет на результат применения пустого регулярного выражения, потому что интерполированное значение переменной $re (т.е. внутреннее представление литерала (\w) ) уже находится в кэшированном регулярном выражении по умолчанию).

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

    Если оператор поиска или замены не содержит ничего кроме объекта регулярного выражения:

    my $re=/…/;
…
if ($_ =~ $re) …
или
if (m/$re/) …

    то в этом операторе напрямую применяется откомпилированный объект регулярного выражения.

    Здесь уместно вспомнить об опасности применения модификатора o с объектами регулярных выражений:

    my $re=/…/o;

    который дает неожиданный и неприятный эффект, описанный ранее.

    13.2. Отладочная информация регулярных выражений

    Если применить директиву

    use re qw(debug);

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

    use re qw(debug);

'abcd' =~ /abc(d)/;

    На печать будет выдано:

    Compiling REx `abc(d)'
size 9 Got 76 bytes for offset annotations.
first at 1
   1: EXACT <abc>(3)
   3: OPEN1(5)
   5:   EXACT <d>(7)
   7: CLOSE1(9)
   9: END(0)
anchored `abcd' at 0 (checking anchored) minlen 4
Offsets: [9]
        1[3] 0[0] 4[1] 0[0] 5[1] 0[0] 6[1] 0[0] 7[0]
Guessing start of match, REx `abc(d)' against `abcd'...
Found anchored substr `abcd' at offset 0...
Guessed: match at offset 0
Matching REx `abc(d)' against `abcd'
  Setting an EVAL scope, savestack=3
   0 <> <abcd>            |  1:  EXACT <abc>
   3 <abc> <d>            |  3:  OPEN1
   3 <abc> <d>            |  5:  EXACT <d>
   4 <abcd> <v            |  7:  CLOSE1
   4 <abcd> <>            |  9:  END
Match successful!
Freeing REx: `"abc(d)"'

    Текст

    1: EXACT <abc>(3)
   3: OPEN1(5)
   5:   EXACT <d>(7)
   7: CLOSE1(9)
   9: END(0)

    является расшифровкой внутреннего представления регулярного выражения. Например, строка

    1: EXACT <abc>(3)

    означает, что надо искать строковый литерал abc длиной 3 символа. Строка

    anchored `abcd' at 0 (checking anchored) minlen 4

    означает, что текст abcd длины 4 привязан к началу регулярного выраения и должен встретиться при любом совпадении. Поэтому, если целевой текст окажется короче этого текста, то Perl не станет применять регулярное выражение, оператор поиска без применения сразу возвратит неудачу. Строка

    3: OPEN1(5)

    означает, что открылась первая захватывающая скобка, 5 означает номер следующей исполняемой строки псевдокода.

    13.3. Функция study

    Функция

    study( переменная с целевым текстом )

    является еще одной возможностью оптимизации использования регулярных выражений.

    Эта функция создает в переменной с целевым текстом скрытую информацию о тексте, который содержит эта переменная. Это список позиций, в которых каждый символ встречается в данном тексте. В результате на построение этого списка позиций расходуется время и память, которая обычно превосходит в четыре раза объем памяти для текста этой переменной. Поэтому выигрыша во времени можно не получить вовсе, если применять функцию study не там, где нужно. Функция study может существенно ускорить поиск, если в регулярном выражении имеется литеральный текст, но модификатор i сводит на нет усилия функции study. Также функция study может оказаться полезной, если к одной и той же переменной применяется много операторов с регулярными выражениями или если целевой текст имеет большой объем. При любом присваивании значения переменной, содержащей целевой текст, внутренняя информация, привязанная к этой переменной, становится недействительной.

    Для применения оптимизаций, которые возможны с функцией study, надо стараться выделять литеральный текст. Например, вместо

    a+

    надо написать эквивалентный подшаблон

    aa*

    а вместо

    a{3,6}

    нужно записать

    aaa{0,3}

    Если конструкция выбора ( альтернативный шаблон ) в каждой ветви начинается с одного и того же литерала, то его надо "вынести за скобку" и, к примеру, вместо

    that|this

    записать

    th(?:at|is)

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

    В поставке 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)

    Итак, это регулярное выражение тратит 1.11 секунды на миллион повторов цикла. (Кстати, на компиляцию этого регулярного выражения тратится 0.02 секунды, что намного больше, чем тратится на его выполнение для 90000 символов.)

    Теперь давайте уберем атомарную группировку:

    $_=' <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);

    Распечатка времени показывает, что программа стала работать быстрее и теперь тратит всего 1.08 секунды. Это можно понять так: зачем трудиться по уничтожению сохраненных состояний, когда регулярное выражение заканчивается? Если убрать атомарные скобки вокруг подшаблона \s*, то регулярное выражение начиает работать еще немного быстрее. Но здесь все зависит от данных, которые обрабатывает это регулярное выражение. В нашем случае пробелов мало, они встречаются по одному, а если группы пробелов будут большими, то в этом случае уничтожение состояний для подшаблона \s* может пригодиться. Кроме того, у нас нет возвратов при переборе. Если убрать последнюю атомарную группировку:

    /\A				# начало текста
        (?:			# цикл пропуска пробелов и тегов
            \s*			# пропускаем пробельные символы
            <[^>]*>	        # пропускаем тег с его содержимым
        )*			# повтор любое число раз
    \S				# и вот он наконец - непробельный символ
/x;

    то время выполнения участка кода практически не изменится и станет равным 1.03 секунды.

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

    (?=[^<>]*>)

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

    (?![^<>]*>)

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

    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 замедлял работу программы в десятки раз.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^