プログラミングで重み付き乱数を生成する方法: 拒否サンプリングと反復検索?

プログラミングにおける重み付き乱数の生成

重み付き乱数は、範囲内の特定の値が選択される確率が異なるさまざまなシナリオで応用されます。この記事では、これを達成するための 2 つの効果的なアプローチを検討します。

最初の質問者が提案した最初のアプローチには、拒否サンプリングが含まれます。このメソッドは、範囲内の要素が入力されたルックアップ テーブルを作成します。各要素は、その重みに比例した回数表示されます。その後、ルックアップ テーブルからランダムなインデックスが選択され、乱数が取得されます。ここでのトレードオフは、ルックアップ テーブルを構築するための線形時間の複雑さと、大きな重み仕様の潜在的なメモリ消費にあります。

代わりに、反復検索 メソッドは重みの合計を繰り返し計算します。重量仕様を横断しながら。この合計を、ランダムに生成された 0 ～ 1 の数値と比較します。合計が乱数を超える場合は、対応する値が乱数として返されます。拒絶サンプリングとは異なり、このアプローチには初期費用は発生しませんが、平均時間の計算量は重み仕様のエントリ数に比例します。

JavaScript で両方のアプローチをデモするには、次のようにします。

// Rejection Sampling
function weightedRand(spec) {
  var i, j, table = [];
  for (i in spec) 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});

// Iterative Search
function weightedRand2(spec) {
  var i, sum = 0, r = Math.random();
  for (i in spec) { sum += spec[i]; if (r <= sum) return i; }
}

どのアプローチを選択するかは、時間の複雑さ、メモリ使用量、および決定的な動作のバランスを考慮した特定のアプリケーション要件によって異なります。リジェクション サンプリングは、事前のテーブル構築を犠牲にして定数時間のルックアップを提供しますが、反復検索は線形時間のパフォーマンスを備えたよりシンプルな実装を提供します。これらの手法を活用することで、プログラマはさまざまなプログラミング ニーズに合わせて重み付けされた乱数を効果的に生成できます。

以上がプログラミングで重み付き乱数を生成する方法: 拒否サンプリングと反復検索?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。