Islands in the byte stream

List::Util::firstは遅い

Perl

(追記：この用途ではList::Util::firstを使うのは誤りで，List::MoreUtils::anyが意図されたコードです。効率についての結論は変わりません)

List::Util::first{expr}は組み込みのgrep{expr}に似ているが，exprが最初に真になった段階でその値を返すので，grep{expr}よりも効率がいいと説明されることが多い。しかし，実際にベンチマークを取ってみると，多くの場合grep{expr}より遅い。最初の要素が真になるというfirst{expr}にとって最適な条件でさえ，要素数が40を越えたあたりでようやくgrep{expr}とほぼ同程度の速度になる。したがって，List::Util::first{expr}が効果的なケースはそれほど多くないと思われる。

また，もし単なる文字列の検索でよく，その検索をプログラム中で繰り返すならば，grep{expr}よりもハッシュを見るほうが常に圧倒的に速い。

ベンチマーク：

$ perl first_benchmark.pl 40
Perl 5.8.5 on linux.
Found in the frist element:
          Rate  grep first  hash
grep   11377/s    --   -9%  -96%
first  12444/s    9%    --  -95%
hash  262044/s 2203% 2006%    --
Not found:
          Rate first  grep  hash
first   4483/s    --  -61%  -99%
grep   11487/s  156%    --  -96%
hash  309688/s 6807% 2596%    --

ベンチマークスクリプト(最初の引数で要素数を指定できる。デフォルトは10):

#!perl -w
use strict;
use Benchmark qw(:all);
use List::Util qw(first);

printf "Perl %vd on %s.\n", $^V, $^O;

my $n      = shift @ARGV;
my @values = ('foobar', ('xxxxxx') x ($n || 10));
my %values_in;
@values_in{@values} = ();

print "Found in the frist element:\n";
my $s = $values[0];
cmpthese -1, {
  grep => sub{
    for( 1 .. 10 ){
      1 if grep { $_ eq $s } @values;
    }
  },
  first => sub{
    for( 1 .. 10 ){
      1 if first { $_ eq $s } @values;
    }
  },
  hash => sub{
    for( 1 .. 10){
      1 if exists $values_in{ $s };
    }
  },
};

print "Not found:\n";
$s = reverse $s;
cmpthese -1, {
  grep => sub{
    for( 1 .. 10 ){
      1 if grep { $_ eq $s } @values;
    }
  },
  first => sub{
    for( 1 .. 10 ){
      1 if first { $_ eq $s } @values;
    }
  },
  hash => sub{
    for( 1 .. 10){
      1 if exists $values_in{ $s };
    }
  },
};
__END__

Permalink | コメント(0) | トラックバック(1) | 11:02