配列内要素のシャッフルを考える

先にグッドプラクティス。

use List::Util;
my @shuffled = shuffle(@array);

さてこの中はどのように実装されているのだろうか。

まずシャッフルとは

配列内の要素をランダムに順番を入れ替える(シャッフル)場合、大きく2種類の方法がある。

偏りのあるシャッフル
偏りのないシャッフル

偏りのあるシャッフル

手持ちの「PerlクックブックVol.1」から「真似するな例」を引用させてもらうと

sub naive_shuffle {   # このコードではいけない
  for (my $i = 0; $i < @_; $i++) {
    my $j = int rand @_;
    ($_[$i], $_[$j]) = ($_[$j], $_[$i]);
  }
}

このコードのアルゴリズムには偏りがあり、すべての要素順列を同じ確率で生成できません。このことは簡単に説明できます。3つの要素を持つリストが渡された場合を考えてみます。この場合、3つの乱数(添え字)が生成されますが、各乱数は3つの要素のどれかに対応するので、27(3x3x3)通りの要素順列が得られることになります。しかし、3つの要素を並べられてできる順列は6通りしかありません。27は6で割り切れないので、いくつかの要素順列は他の要素順列よりも高い確率で生成されることになります。
PerlクックブックVol.1 P176

実際にやってみた。

[0]	[1]	[2]
3	7	9

my %result = ();
for my $i (1 .. 100000) {
  my @args = (3, 7, 9);
  naive_shuffle(@args);
  $result{join(" ",@args)}++;
}
require Data::Dumper;
print Data::Dumper::Dumper(\%result);

$VAR1 = {
'7 3 9' => 18799,
'9 7 3' => 14904,
'9 3 7' => 14828,
'7 9 3' => 18398,
'3 9 7' => 18451,
'3 7 9' => 14620
};

ばらけた。
なるほど、確かに偏りがあるといえる。
ようするに原因は

    my $j = int rand @_;

において$jのとりうる範囲が

ループ回数	$j
1巡目	0≦$j＜3
2巡目	0≦$j＜3
3巡目	0≦$j＜3

とどのターンでも常に同じである点にある。

プロダクションでは決して使うべきではないだろう。

偏りのないシャッフル

ではList::Util::shuffleはこのあたりどのように実装しているのか。
List::UtilはXSで使われるけれど、loadできなかったときの保険のPurePerl版があるのでそちらを参考にする。

List/Util/PP.pm

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

一見では何をしているのかよく分からない。
1行ずつ見ていく。

sub shuffle (@) {

プロトタイプに「@」を使用して、配列を引数にすることを明示している。

  my @a=\(@_);

引数の配列が入った特殊配列「@_」の要素1個1個のリファレンスを「@a」に入れていく。
つまり、

$a[0]; #=> \$_[0]
$a[1]; #=> \$_[1]
$a[2]; #=> \$_[2]
…

こんな感じに「@a」に入っていく。
次。

  my $n;
  my $i=@_;

作業用変数「$n」を用意し、「$i」に引数配列の要素数を代入する。

  map {
    $n = rand($i--);
    (${$a[$n]}, $a[$n] = $a[$i])[0];
  } @_;

一番複雑怪奇な箇所。mapをforeachにしてみる。

  my @shuffled;
  for (@_) {
    $n = rand($i--);
    push @shuffled,
      (${$a[$n]}, $a[$n] = $a[$i])[0];
  }
  return @shuffled;

  for (@_) {

引数の要素の数だけループ。エイリアスである「$_」は、元のmapのループ内で使っていないので、ただ「要素の数の回数ループ」することが重要といえる。

    $n = rand($i--);

ポストデクリメントなので、実際にはこう。

    $n = rand($i);
    $i--;

rand($i)は、「0以上$i未満」のfloatを返すので、それが「$n」に代入され、$iがカウントダウンする。
余談だが、配列の添字は別に整数でなくてもよい、小数点以下は自動的に切り捨てられる。

      (${$a[$n]}, $a[$n] = $a[$i])[0];

まず外側は、配列のスライスだ。
配列要素の添字[0]が最後に評価される。
ではその添字[0]はというと、

${$a[$n]}

なわけだが、配列スライスは、先に元の配列なしには成立しないので、添字[0]以外の要素も決定させておくために、要素の評価が行われる。
つまり残っている添字[1]の

$a[$n] = $a[$i]

である。
つまり評価順序としては、配列内各要素→スライスされる要素なわけで、以下のように置き換えできる。

    $a[$n] = $a[$i];
    push @shuffled, ${$a[$n]};

「shuffle(1..10)」としたときのこの時点の「$n」と「$i」のとりうる範囲について考えてみる。

ループ回数	$n	$i
1巡目	0≦$n＜10	9
2巡目	0≦$n＜9	8
3巡目	0≦$n＜8	7
…	…	…
10巡目	0≦$n＜1	0

……図で表すと一発だった。
配列内要素のシャッフルを考える【図】 - Perl日記

総じて簡単に分かりやすく書き直すと、

sub shuffle (@) {
  my @a=\(@_);
  my $n;
  my $i=@_;
  my @shuffled;
  for (@_) {
    $n = rand($i);
    $i--;
    $a[$n] = $a[$i];
    push @shuffled, ${$a[$n]};
  }
  return @shuffled;
}

こんな感じか。
よし、理解できた。

久しぶりにPerlに触ったので、ちょっと忘れてしまってた(^^;)。。

参考：

perlfaq4 - perldoc.perl.org