アレイからの重み付きランダム選択

質問

配列からランダムに1つの要素を選択したいのですが、各要素は選択される確率が分かっています。

すべての確率を合わせると（配列の中で）1になります。

最も高速で、巨大な計算に適したアルゴリズムは何でしょうか？

例を挙げます。

id => chance
array[
    0 => 0.8
    1 => 0.2
]

この擬似コードでは、問題のアルゴリズムは、複数の呼び出しで統計的にidの4つの要素を返す必要があります。 0 の1つの要素に対して、id 1 .

どのように解決するのですか？

リストの離散累積密度関数(CDF)、簡単に言えば重みの累積和の配列を計算します。 次に、0 とすべての重みの合計 (あなたの場合は 1 かもしれません) の間の範囲で乱数を生成し、離散 CDF 配列でこの乱数を見つけるためにバイナリ検索を行い、このエントリに対応する値を取得します。