Next Previous Contents

Unix Review Column 28 -- Компиляция регулярных выражений

Randal Schwartz

Октябрь 1999

Перевод Anton Petrusevich <casus@mail.ru> и Alex Ott <ott@phtd.tpu.edu.ru>

Регулярные выражения Perl помещают его отдельно от других скриптовых языков. Некоторые из свойств (такие как положительные и отрицательные просмотры вперед, также опициональная отложенная оценка множителей) делают трудные операции поиска строк тривиальными при использовании Perl. Эта мощь не была незамечена сообществом открытого программного обеспечения -- в сети доступен пакет, названный PCRE (для поиска используйте свою любимую поисковую систему) и предназначенный для реализации ``библиотеки работы с регулярными выражениями, которая совместима с синтаксисом Perl 5.004''.

Также как и строки с которыми производится сравнение, регулярные выражения могут быть получены из разных источников. Основным источником является исходные тексты программ:

    @ARGV = qw(/usr/dict/words);
    while (<>) {
        print if /foo/ || /bar/;
    }

Эта небольшая программа выполняется на моем компьютере примерно четверть секунды, и создает великолепный список слов, которые содержат foo и bar. Заметьте, что я написал /foo/ и /bar/ как отдельные регулярные выражения, вместо выражения /foo|bar/, которое кажется похожим на них. Почему я так сделал? Опыт. Как показано следующей программой:

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    use Benchmark;
    timethese (10 => {
        'expression or' =>
            '@x = grep /foo/ || /bar/, @words',
        'regex or' =>
            '@x = grep /foo|bar/, @words',
    });

мы получаем следующий вывод от модуля Benchmark:

    Benchmark: timing 10 iterations of expression or, regex or...
    expression or:  1 wallclock secs ( 0.97 usr +  0.00 sys =  0.97 CPU)
    regex or:  3 wallclock secs ( 2.87 usr +  0.00 sys =  2.87 CPU)

Эти результаты показывают, что использование оператора регулярного выражения | приводит почти к двухкратному замедлению работы. Существуют методы оптимизации, которые взрываются, когда текст, которому надо найти соответствие является постоянной строкой, которая не может быть выполнена, когда у нас имеется что-то сложное. Точный список оптимизованых операций варьируется от версии к версии Perl, так что модуль Benchmark будет хорошим подспорьем.

Часто регулярные выражения поступают из вычисленных строк, таких как значения форм веб-серверов или параметров командных строк или результатов запросов к пользователю. Синтаксис Perl позволяет нам интерполировать переменные в регулярные выражения, позволяя создавать регулярные выражения во время выполнения программы:

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    $regex1 = "foo";
    @result = grep /$regex1/, @words;

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

Это предоставляет огромные возможности (при неправильном использовании, создание регулярных выражений во время выполнения программы может привести к потере производительности). Давайте проверим это:

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    push @words, @words;
    push @words, @words;
    use Benchmark;
    $foo = '[f][o][o]';
    $bar = '[b][a][r]';
    timethese (5 => {
        'constant' =>
            '@x = grep /[f][o][o]/ || /[b][a][r]/, @words',
        'one variable' =>
            '@x = grep /$foo/ || /[b][a][r]/, @words',
        'two variables' =>
            '@x = grep /$foo/ || /$bar/, @words',
    });

И вот результата:

    Benchmark: timing 5 iterations of constant, one variable, two variables...
    constant:  3 wallclock secs ( 2.86 usr +  0.00 sys =  2.86 CPU)
    one variable:  4 wallclock secs ( 3.49 usr +  0.00 sys =  3.49 CPU)
    two variables:  4 wallclock secs ( 4.11 usr +  0.00 sys =  4.11 CPU)

Заметьте, что мы несем потери при ре-компиляции регулярного выражения. (Для того, чтобы сделать это очевидным, я усложнил регулярное выражение и заставил его использовать больше данных).

Почему это происходит? Хорошо, для каждого из сравнений между элементами массива @words и регулярным выражением, определенным переменной, Perl должен каждый раз перекомпилировать регулярное выражение.

Одним из исправлений является использование для регулярного выражения модификатора ``только-раз''. Добавляя к регулярному выражению суффикс o, любая отсроченная компиляция будет выполнена только раз при каждом выполнении программы. Давайте посмотрим, как это может нам помочь:

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    push @words, @words;
    push @words, @words;
    use Benchmark;
    $foo = '[f][o][o]';
    $bar = '[b][a][r]';
    timethese (5 => {
        'constant' =>
            '@x = grep /[f][o][o]/ || /[b][a][r]/, @words',
        'two variables' =>
            '@x = grep /$foo/ || /$bar/, @words',
        'two variables - opt' =>
            '@x = grep /$foo/o || /$bar/o, @words',
    });

И затем посмотрев на результаты, мы убедимся, что это нам сильно помогло:

    Benchmark: timing 5 iterations of constant, two variables, two variables - opt...
    constant:  3 wallclock secs ( 2.86 usr +  0.01 sys =  2.87 CPU)
    two variables:  4 wallclock secs ( 4.15 usr +  0.01 sys =  4.16 CPU)
    two variables - opt:  3 wallclock secs ( 2.98 usr +  0.00 sys =  2.98 CPU)

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

Так что, код похожий на данный работает великолепно:

    $var = param('search_for');
    @results = grep /$var/o, @input;

А следующий код, является сильно нарушенным и его тяжело отслеживать:

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    for $item (qw(foo bar)) {
        @results = grep /$item/o, @words;
        print @results. " words match $item\n";
    }

что выдает:

    43 words match foo
    43 words match bar

вместо правильного ответа:

    43 words match foo
    131 words match bar

который я получил после удаления суффикса o. Это происходит, поскольку строка foo была запомнена при компиляции регулярного выражения, даже после того, как значение $item было изменено для второй итерации.

Так что мы будем делать? Как мы можем получить скорость однажды скомпилированого выражения, но при этом иметь возможность выполнения цикла по нескольким шаблонам поиска?

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

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    for $item (qw(foo bar)) {
        $match = eval 'sub { $_[0] =~ /$item/o }';
        @results = grep $match->($_), @words;
        print @results. " words match $item\n";
    }

Что снова выдает нам правильные значения. То что происходит здесь является немного странным... мы все еще используем $item шаблон поиска, но поскольку каждое новое выполнение цикла перекомпилирует анонимную подпрограмму (на которую ссылаются с помощью переменной $match), то флаг однократной компиляции сбрасывается.

Конечно, мы отбрасываем результат компиляции при каждой итерации цикла, но по крайней мере мы не перекомпилируем выражение для каждого из объектов в массиве @words.

Вы даже можете создать подпрограмму, которая создает эти подпрограммы:

    sub make_match {
        my $item = shift;
        eval 'sub { $_[0] =~ /$item/o }';
    }
    $match_foo = make_match "foo";
    $match_bar = make_match "bar";
    @foo_words = grep $match_foo->($_), @words;
    @bar_words = grep $match_bar->($_), @words;

Здесь ссылка на $item в анонимной подпрограмме создает ``замкнутое выражение (closure)'', которое запоминает значение $item вне зависимости от того, как долго живет подпрограмма.

И есть спасение при использовании Perl 5.005! В последних версиях Perl был введен оператор заключения в кавычки qr//. Этот оператор предназначен для компиляции регулярных выражений и передачи в переменные скомпилированных значений, а не оригинальных строк.

Давайте снова исправим наш код:

    @ARGV = qw(/usr/dict/words);
    @words = <>;
    for $item (qw(foo bar)) {
        $compiled = qr/$item/;
        @results = grep /$compiled/, @words;
        print @results. " words match $item\n";
    }

Да, мы снова получаем правильный ответ. И Perl компилирует регулярные выражения один раз, а не каждый раз когда он видит строку. Мы даже можем скомпилировать их все разом:

    @patterns = map { qr/$_/ } qw(foo bar);

И затем использовать интерполированую @patterns как мы могли делать при использовании оригинальных строк.

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


Next Previous Contents