【再訪】重みを持つ要素の配列から、ランダムに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 種類はより低い確率で……
なんていう状況をターゲットにしていた為。
データ量が少なければ、重い順に舐めていったほうがいいだろうけど、量が多い場合はこうしないときつかった。