重複しない乱数の生成

perl

Perlで乱数生成 - ハブ君の寝言


を見て、昔自分もそんな感じで書いてたなぁと思い出しつつ、
今の知識で書いてみました。

手法1

  1. 0から nまでの配列を生成
  2. 0から nまでの乱数を生成
  3. (2)で得られた indexと配列の最後の要素を交換
  4. n = n-1とし, (2)に戻る.

これを n > 1の間繰り返す


都合上コードでは若干順番がずれてます・・・

sub use_swap {
    my $num = shift;
    my @array = (0..($num-1));

    my $random_range = $num;
    while ($random_range > 1) {
        my $n = int( rand($random_range) );
        $random_range -= 1;

        @array[$n, $random_range] = @array[$random_range, $n];
    }

    return @array;
}

手法2

  1. 0からnまでの配列を生成
  2. 乱数を生成。特に範囲はない
  3. 0から nについて (2)で生成した乱数を加算し, ハッシュに追加
  4. keys関数でハッシュのキーを取得, そのキーから (2)で生成した乱数を減算し,配列に詰める
sub use_hash_key {
    my $num = shift;
    my $rand = int( rand(time) );

    my %a;
    $a{$_ + $rand} = 1 for 0..($num-1);

    return map { $_ - $rand } keys %a;
}

手法3

List::Utilの shuffleを使う

use List::Util qw(shuffle)
sub list_util_shuffle {
    return shuffle (0..(shift()-1));;
}

比較

引用元に載っていたものと合わせて計測を行ってみました。

# 引用したものを少し修正
sub too_simple {
    my $num = shift;
    my @rands;

    while (scalar @rands != $num) {
        my $n = int(rand($num));

        my $is_existed = 0;
        for my $r (@rands) {
            if ($n == $r) {
                $is_existed = 1;
                last;
            }
        }

        if ($is_existed == 0) {
            push @rands, $n;
        }
    }

    return @rands;
}

my $range = 100;
cmpthese(-10, {
    simple => sub { too_simple($range) },
    swap   => sub { use_swap($range) },
    hash_key => sub { use_hash_key($range) },
    shuffle  => sub { list_util_shuffle($range) },
});

比較結果

                     Rate     simple   hash_key     swap    shuffle
simple         377/s          --          -95%     -97%     -100%
hash_key   7970/s    2013%             --      -30%       -93%
swap       11366/s    2913%           43%          --       -90%
shuffle  116478/s  30780%       1362%     925%           --

shuffleがやたらと早い。XSだからでしょうかね。
変に自分で書くなら shuffleがいいかなと思います。
本当にランダムかって問題も伴うのでそのあたりは
ちゃんと検証した方がいいかもしれないですね。

最後に

重複しない乱数の生成について示しました。