asin:479736100X
数学ガール/乱択アルゴリズム
結城浩

同意なのだけど…

Perlで生でrand関数をごちゃごちゃ使うコードはもう嫌だ | hirobanex.net
とにかく、プログラムッチクというとなにかとランダムという要件が多いし、こんなコードばかりグチャグチャ書くのはもういやですね。

これを一般化するという問題はアルゴリズムの実習にちょうど手頃なサイズなので。

JavaScriptによる実装

頻度を高い順に並べて、乱数＜合計頻度となったところでそれを選択します。O(n)ですが選択肢を頻度順に並べることでその分ループが回る確率を抑えています。

(function(global){

var make_random_picker = function(picks){
    var choices = Array.prototype.slice.call(picks)     /* copy */
        .sort(function(a, b){ return b[1] - a[1] }),    /* sort by weight */
        i = 0, l = choices.length, t = 0;
    /* normalize the probability */
    for (i = 0; i < l; i++){ t += choices[i][1] };
    for (i = 0; i < l; i++){ choices[i][1] /= t };
    return function(){
        var i, choice, p = 0, r = Math.random();
        for (i = 0; i < l; i++){
            choice = choices[i];
            p += choice[1];
            if (r < p){  return choice[0] }
        }
        /* last resort -- very unlikely to happen where p < 1 */
        return choices[choices.length-1][0];
    }
};

global.make_random_picker = make_random_picker;

})(this);





Perlによる実装


JavaScriptとやっていることは同じですが、いくぶん楽です。




use strict;
use warnings;

sub make_random_picker {
    my $picks = shift;
    my @choices = sort { $b->[1] <=> $a->[1] } @$picks;
    my $t;
    $t += $_->[1] for @choices;
    $_->[1] /= $t for @choices;
    return sub {
        my ( $p, $r ) = ( 0, rand() );
        for my $choice (@choices) {
            $p += $choice->[1];
            return $choice->[0] if $r < $p;
        }
        return $choices[-1][0];
      }
}

my $pick = make_random_picker([
    [ foo  => 20 ],
    [ bar  => 10 ],
    [ baz  => 10 ],
    [ hoge => 30 ],
    [ moge => 30 ],
]);
print $pick->(), "\n" for ( 1 .. 20 );





別解


重みを全て整数で指定するなら、富豪プログラミング的にこうも出来ます。O(1)なところが素晴らしい。




use strict;
use warnings;
sub make_random_picker {
    my ( $t, @choices );
    for my $choice ( @{ shift @_ } ) {
        push @choices, ( $choice->[0] ) x $choice->[1];
        $t += $choice->[1];
    }
    return sub { $choices[ int( rand() * $t ) ] };
}

my $pick = make_random_picker([
    [ foo  => 20 ],
    [ bar  => 10 ],
    [ baz  => 10 ],
    [ hoge => 30 ],
    [ moge => 30 ],
]);
print $pick->(), "\n" for (1..20);





JSに書き直すとこうですか。




var make_random_picker = function(picks){
    var i, j, l = picks.length, t = 0, choices = [];
    for (i = 0; i < l; i++){
        for (j = 0; j < picks[i][1]; j++) choices.push( picks[i][0] );
        t += picks[i][1];
    }
    return function(){ return choices[ Math.floor(Math.random() * t)] };
};

var pick = make_random_picker([
    ['foo',     20],
    ['bar',     10],
    ['baz',     10],
    ['hoge',    30],
    ['moge',    30]
]);
for(var i = 0; i < 20; i++) p(pick());





Enjoy!


Dan the Random Picker