Производительность сопоставления подстрок, не содержащих bar - PullRequest
Новая
       4

Производительность сопоставления подстрок, не содержащих bar

3 голосов
/ 15 июля 2011

В Perl, какая из следующих конструкций регулярных выражений будет самой быстрой?

  1. /foo(?>.*?bar)/s
  2. /foo(?:(?!bar).)*+bar/s
  3. /foo(?:[^b]++|b(?!ar))*+bar/

Для больших струн с большим расстоянием от foo до bar (с умеренным содержанием b).(PCRE ответы также были бы интересны.)

Ответы [ 3 ]

5 голосов
/ 15 июля 2011 
use Benchmark;

чтобы узнать точные измерения.

0 голосов
/ 21 июля 2011
  1. ab(?>.*?cd)
  2. ab(?:(?!cd).)*+cd
  3. ab(?:[^c]++|c(?!d))*+cd

В простом случае, как в предыдущем вопросе, с длинной тестовой строкой и следующим кодом на Perl 5.12, ответ таков: первое регулярное выражение намного превосходит остальные , второе самый медленный (как и предполагалось).

Это были результаты в итерациях в секунду (масштабированные до самого медленного):

  1. 23,49 x iter / sec
  2. 1,00 x iter / sec
  3. 3.35 x iter / sec

Используя код: 

use v5.12;
use Benchmark qw(:hireswallclock :all);

my $str = '';
my $ab = 'ab' x 1024**2;
$str .= $ab . 'cd';
$str .= $ab . 'cde';
$str .= $ab . 'cdef';
$str .= $ab . 'cdefg';
$str .= $ab . 'cdefgh';

printf "Test string length: %.2f MiB\n", (length($str)/1024**2);

timethese(-10, {
    '0:index'       => sub { index($str, 'cdefgh') },

    '1:match'       => sub { $str =~ /ab(?>.*?cdefgh)/ },
    '1:fail'        => sub { $str =~ /ab(?>.*?cdefgg)/ },

    '2:match'       => sub { $str =~ /ab(?:(?!cdefgh).)*+cdefgh/ },
    '2:fail'        => sub { $str =~ /ab(?:(?!cdefgg).)*+cdefgg/ },

    '3:match'       => sub { $str =~ /ab(?:[^c]++|c(?!defgh))*+cdefgh/ },
    '3:fail'        => sub { $str =~ /ab(?:[^c]++|c(?!defgg))*+cdefgg/ },
});

Выход: 

Test string length: 10.00 MiB
Benchmark: running 0:index, 1:fail, 1:match, 2:fail, 2:match, 3:fail, 3:match for at least 10 CPU seconds...
   0:index: 11.0578 wallclock secs (10.00 usr +  0.00 sys = 10.00 CPU) @ 246.70/s (n=2467)
    1:fail: 11.0379 wallclock secs (10.05 usr +  0.00 sys = 10.05 CPU) @ 245.05/s (n=2462)
   1:match: 11.9981 wallclock secs (10.08 usr +  0.00 sys = 10.08 CPU) @ 63.80/s (n=643)
    2:fail: 12.0531 wallclock secs (10.53 usr +  0.00 sys = 10.53 CPU) @ 255.25/s (n=2688)
   2:match: 11.0573 wallclock secs (10.13 usr +  0.00 sys = 10.13 CPU) @  2.67/s (n=27)
    3:fail: 12.8325 wallclock secs (10.78 usr +  0.00 sys = 10.78 CPU) @ 266.58/s (n=2874)
   3:match: 11.8457 wallclock secs (10.09 usr +  0.00 sys = 10.09 CPU) @  9.31/s (n=94)

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

0 голосов
/ 15 июля 2011

Так как это достаточно просто проверить, я предполагаю, что вы спрашиваете либо как дразнилку мозга, либо как способ проверить свои предположения;Я укушу;)

Я ожидаю, что №3 будет самым быстрым..*?bar по сути то же самое, что и (?:(?!bar).)*, поэтому # 1 и # 2 оба должны заглянуть в каждую позицию.# 3 делает только один раз, когда видит b.

...