Что является более эффективным регулярным выражением?

Question

Я анализирую некоторые большие файлы журнала и у меня есть несколько очень простых совпадений строк, например

if(m/Some String Pattern/o){
    #Do something
}

Это кажется достаточно простым, но на самом деле большинство моих совпадений может быть против начала строки, но совпадение будет "более длинным", например

if(m/^Initial static string that matches Some String Pattern/o){
    #Do something
}

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

Я догадываюсь, что последний будет более эффективным. Может ли кто-нибудь поддержать меня / подстрелить: -)

Answer 1

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

Это то, что вы могли бы легко проверить и измерить, конечно. Сделайте совпадение с регулярным выражением 10 миллионов раз или около того, измерьте, сколько времени это займет, затем повторите попытку с другим регулярным выражением.

Answer 2

Линейный якорь делает это быстрее. Я должен добавить, что модификатор // o здесь не нужен, на самом деле он ничего не делает. Это кодовый запах для меня.

Раньше были действительные значения для // o, но в наши дни это предоставляется qr //

Answer 3

Я сделал несколько таймингов в соответствии с рекомендациями. Вот результаты для моего приложения. Это все приложение, а не только поиск регулярных выражений. Сканирует 60 000 строк. 11 Регулярных выражений средняя короткая длина составляла около 30 символов. Длиннее, но на якоре около 120.

Short
   real    0m58.780s
   user    0m54.940s
   sys     0m0.790s

Long (anchored)
   real    0m54.260s
   user    0m53.630s
   sys     0m0.490s

Long (not anchored)
   real    0m54.705s
   user    0m54.130s
   sys     0m0.400s

Таким образом, закрепление длинных строк происходит немного быстрее. Хотя не сильно. Казалось бы, если бы мои строки были больше, это могло бы быть другое дело.

Answer 4

Скорость RE зависит от двух факторов: самого RE и данных, передаваемых через RE. Как правило, привязанный RE (начало или конец) без возврата будет быстрее, чем другие. Но если вы обрабатываете файл, в котором каждая строка пуста, разницы в скорости между /^hello/ и /hello/ нет (по крайней мере, если механизм RE написан правильно).

Но я соблюдаю правило: измеряй, не угадывай.

Answer 5

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

Всегда полезно просмотреть рекомендуемые Perl методы производительности , включая рекомендуемые методы синхронизации.

Если я проведу этот небольшой тест:

#!/usr/bin/perl 

use strict;
use warnings;
use Benchmark;

my $target="aeiou";

my $str="lkdjflzdjfljdsflkjasdjf asldkfj lasdjf dslfj sldfj asld alskdfj lasd f";

my $str2=$str.$target;

timethese(10_000_000, {
            'float'       => sub {
                die "no match" unless $str2=~m/$target/o;
            },
            'anchored'  => sub {
                die "no match" unless $str2=~m/^.*$target/o;
            },
            'prefixed'   => sub {
                die "no match" unless $str2=~m/^$str$target/o ;
            },  

    });

Я получаю вывод:

Benchmark: timing 10000000 iterations of anchored, float, prefixed...
  anchored:  4 wallclock secs ( 3.46 usr +  0.01 sys =  3.47 CPU) @ 2881844.38/s 
     float:  2 wallclock secs ( 1.87 usr +  0.00 sys =  1.87 CPU) @ 5347593.58/s 
  prefixed:  4 wallclock secs ( 3.05 usr +  0.01 sys =  3.06 CPU) @ 3267973.86/s 

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

Answer 6

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

/^blah blah The Real Regex/

Это, безусловно, не повредит производительности , и, вероятно, поможет, но не по той причине, о которой вы думаете. Хотя они больше всего известны за «волшебные» вещи, такие как якоря, обходные пути и группы захвата, лучше всего использовать механизмы регулярных выражений для сопоставления буквенных последовательностей символов. Чем длиннее последовательность, тем быстрее совпадение (конечно, до определенного момента).

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

Answer 7

Я голосую за того, кто стоял на якоре в начале, именно по той причине, о которой вы заявляете!