私は、範囲内の各数字に重みが与えられている可能な数字の範囲からランダムな数字を選択する (良い) 方法を考案しようとしています。簡単に言うと、数字の範囲 (0、1、2) が与えられ、0 が選択される確率が 80%、1 が選択される確率が 10%、2 が選択される確率が 10% となる数字を選択します。
大学の統計学の授業を受けてから約 8 年が経ちましたので、現時点では、この正しい公式が思い浮かばないことはご想像のとおりです。
私が思いついた「安っぽくて汚い」方法を紹介します。このソリューションでは ColdFusion を使用します。あなたのソリューションでは、好きな言語を使用できます。私はプログラマーなので、移植はできると思います。最終的に、私のソリューションは Groovy で作成する必要があります。CF では簡単にすばやく作成/テストできるため、このソリューションは ColdFusion で作成しました。
public function weightedRandom( Struct options ) {
var tempArr = [];
for( var o in arguments.options )
{
var weight = arguments.options[ o ] * 10;
for ( var i = 1; i<= weight; i++ )
{
arrayAppend( tempArr, o );
}
}
return tempArr[ randRange( 1, arrayLen( tempArr ) ) ];
}
// test it
opts = { 0=.8, 1=.1, 2=.1 };
for( x = 1; x<=10; x++ )
{
writeDump( weightedRandom( opts ) );
}
より良い解決策を探しています。改善点や代替案を提案してください。
ベストアンサー1
拒否サンプリング(あなたのソリューションのように) が最初に思い浮かぶもので、重みの分布によって要素が設定されたルックアップ テーブルを作成し、テーブル内のランダムな場所を選択してそれを返します。実装の選択肢としては、スペックを受け取り、スペック内の分布に基づいて値を返す関数を返す高階関数を作成します。こうすることで、呼び出しごとにテーブルを作成する必要がなくなります。欠点は、テーブルを作成するアルゴリズムのパフォーマンスがアイテムの数に比例し、大きなスペック (またはメンバーの重みが非常に小さいか正確なもの、例: {0:0.99999, 1:0.00001}) ではメモリ使用量が多くなる可能性があることです。利点は、値の選択に一定の時間がかかることです。これは、パフォーマンスが重要な場合に望ましい場合があります。JavaScript の場合:
function weightedRand(spec) {
var i, j, table=[];
for (i in spec) {
// The constant 10 below should be computed based on the
// weights in the spec for a correct and optimal table size.
// E.g. the spec {0:0.999, 1:0.001} will break this impl.
for (j=0; j<spec[i]*10; j++) {
table.push(i);
}
}
return function() {
return table[Math.floor(Math.random() * table.length)];
}
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});
rand012(); // random in distribution...
もう 1 つの戦略は、ランダムな数値を選択し[0,1)
、重み仕様を反復処理して重みを合計し、ランダムな数値が合計より小さい場合は、関連付けられた値を返すことです。もちろん、これは重みの合計が 1 になることを前提としています。このソリューションには初期コストはありませんが、仕様のエントリ数に比例して平均アルゴリズム パフォーマンスが上がります。たとえば、JavaScript では次のようになります。
function weightedRand2(spec) {
var i, sum=0, r=Math.random();
for (i in spec) {
sum += spec[i];
if (r <= sum) return i;
}
}
weightedRand2({0:0.8, 1:0.1, 2:0.1}); // random in distribution...