local $PERL_MEMO;

■ [perl][func][memo]配列をshuffle(ランダムに並べ替えたい)/take potluck(ランダムに抜き出したい) - 爆速編

前回の更新ではベンチ取らないでやってたので今回は高速化に挑戦。

まずはベンチマーク

使ったコードはこちら。

#!perl
use Benchmark qw(timethese cmpthese);
use List::Util;
my @a = 'Aa'..'Zz'; # 0 .. 675

cmpthese(timethese(10000, {
  'L::U::shuffle' => sub { List::Util::shuffle(@a) },
  shuffle_simple  => sub { shuffle_simple(@a) },
  shuffle         => sub { shuffle(@a) },
  L_U_shuffle     => sub { L_U_shuffle(@a) },
}));


sub shuffle_simple { return sort { int(rand 3) -1 } @_ }

sub shuffle {
  my @old = @_; local $_;
  my ($i, $new) = ($#old+1, 0);
  map {
    $_ = $old[$new = rand $i--];
    $old[$new] = $old[$i];
    $_;
  } 0 .. $#old
}

sub L_U_shuffle {
  my @old = \(@_);
  my $n; my $i = @_;
  map {
    (${$old[$n = rand $i--]}, $old[$n] = $old[$i])[0];
  } @_
}

L_U_shuffleはList::Util::shuffleのpure perl版です。

で、結果が以下。

                   Rate shuffle L_U_shuffle L::U::shuffle shuffle_simple
shuffle           215/s      --        -73%          -97%          -100%
L_U_shuffle       794/s    270%          --          -90%           -99%
L::U::shuffle    7622/s   3453%        859%            --           -94%
shuffle_simple 125000/s  58171%      15635%         1540%             --

…(shuffle_simpleはともかく)勝負にならんな！あとXSのshuffle速すぎ。

なんでこんなに差がつくかというと、L_U_shuffleは実体をコピーするのではなくさっきの記事の方法を使ってリファレンスのリストを作ってそいつを回しているのが原因だと思う。余計な代入も一切発生しない。あと僕の作ったshuffleはmap回すのに0..$#oldみたいないらん配列作ってるしさらに遅い。で、3倍近く差がつく。この点を改良して最速shuffle/take potluckを作ります。

並べ替え

sub shuffle_fast(@) {
  my @old = \(@_);
  my $n; my $i = @_;
  map {
    (${$old[$n = rand $i--]}, $old[$n] = $old[$i])[0];
  } @_;
}

ええパクリです。でも僕の環境だとpure perlのList::Util::shuffleの倍は出ます。何故か。mapの中を1行にしただけなのに。

参考ベンチ(試行回数1000)

              Rate      shuffle  L_U_shuffle shuffle_fast
shuffle      216/s           --         -46%         -72%
L_U_shuffle  396/s          84%           --         -49%
shuffle_fast 774/s         259%          95%           --

適当に抜き出す

sub potluck_fast($;$) {
  my $i = my @a = \(@{+shift});
  my $n = shift || int rand $i;
     $n = $i if $n > $i;
  map {
    (${$a[$n = rand $i--]}, $a[$n] = $a[$i])[0];
  } 0 .. $n-1;
}
warn potluck_fast([0..9,A..Z,a..z],20);
# XK7kgQq6Dn1RLVa8ozOW

ぱくぱく。使い方は前回同様、第1引数に配列のリファレンスを、第2引数に抜き出したい数を渡します。

参考ベンチ(試行回数1000)

              Rate      potluck potluck_fast
potluck      248/s           --         -73%
potluck_fast 925/s         273%           --

おしまい

爆速って程でもなかったかな。しかし既存のshuffleよりはずっと速くなったはず。そのへんのよりは3倍速い。

List::Util使えるんだったらshuffleはList::Util使いましょう。爆速です。potluckみたいなことしたいときも

(List::Util::shuffle('Aa'..'Zz'))[0..rand(676)]

とかすれば爆速間違いなし。XSにはどう頑張っても勝てんわ。

cf.

• List::AllUtils - search.cpan.org