2011年12月27日 17:15 [Edit]

algorithm - 重みをつけて乱択する

同意なのだけど…

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


この記事へのトラックバックURL

この記事へのトラックバック
http://hirobanex.net/article/2011/12/1324792864 http://blog.livedoor.jp/dankogai/archives/51761113.html 似たようなのを 以前 書いたので、改めてまとめただけ。 わざわざ二分探索を使った理由は、 1000 種類のアイテムのうち、 500 種類は同じ確率で、 200 種類はよ
【再訪】重みを持つ要素の配列から、ランダムに1つ選択する。【xif ノート】at 2011年12月27日 18:52