【再訪】重みを持つ要素の配列から、ランダムに1つ選択する。

http://hirobanex.net/article/2011/12/1324792864
http://blog.livedoor.jp/dankogai/archives/51761113.html

似たようなのを 以前 書いたので、改めてまとめただけ。

使い方

/**
 * weight は 1 以上の整数。
 * 合計を 100 にしなければならない……なんてことはない。
 * weight が大きいほうが選択されやすい。
 */
var weighted = new Weighted([
    {value: "hoge", weight: 30},
    {value: "moge", weight: 30},
    {value: "foo",  weight: 20},
    {value: "bar",  weight: 10},
    {value: "jar",  weight: 10},
]);
/**
 * weight の合計が 100 なので、それぞれの出る確率は
 * hoge = 30 / 100
 * moge = 30 / 100
 * foo  = 20 / 100
 * bar  = 10 / 100
 * jar  = 10 / 100
 * となる。
 */

var result = {};
for (var i = 0; i < 100000; ++i) {
    // 重みを考慮して、ランダムに選択する。
    var value = weighted.select();
    if (value in result) {
        ++result[value];
    } else {
        result[value] = 1;
    }
}

var text = [];
for (var p in result) {
    text.push(p + ": " + result[p]);
}
alert(text.join("\n"));

/*
hoge: 29823
jar: 9943
foo: 20224
moge: 30099
bar: 9911

確率的には正しそうな結果になった。
*/

定義

function Weighted(input)
{
    var i = 0,
        length = input.length,
        pair = null,
        offset = null,
        sorted = new Array(length * 2),
        values = new Array(length),
        parameter = 0;

    for (; i < length; ++i) {
        pair = input[i];
        values[i] = pair.value;
        parameter += pair.weight;
        offset = i * 2;
        sorted[offset] = i;
        sorted[offset + 1] = parameter;
        sorted.push(i, parameter);
    }
    sorted.pop(); // 最後の要素は parameter と同じなのでいらない。

    this.sorted = sorted;
    this.parameter = parameter;
    this.values = values;
}

Weighted.prototype.select = function Weighted_select()
{
    var sorted = this.sorted,
        length = sorted.length,
        left = 1,
        right = length - 2,
        middle = null,
        ceil = Math.ceil,
        rand = Math.floor(Math.random() * this.parameter);

    if (length < 2) {
        return length == 1 ? this.values[0] : null;
    }
    do {
        middle = ceil((left + right) / 2);
        if (!(middle & 1)) {
            ++middle;
        }
        if (sorted[middle] > rand) {
            right = middle - 2;
            if (right < left) {
                return this.values[sorted[middle - 1]];
            }
        } else {
            left = middle + 2;
            if (left > right) {
                return this.values[sorted[middle + 1]];
            }
        }
    } while (true);
};

わざわざ二分探索を使った理由は、

  • 1000 種類のアイテムのうち、 500 種類は同じ確率で、 200 種類はより低い確率で、 100 種類はより低い確率で……

なんていう状況をターゲットにしていた為。
データ量が少なければ、重い順に舐めていったほうがいいだろうけど、量が多い場合はこうしないときつかった。