置換ありまたはなしで効率的な加重ランダム選択を実行するにはどうすればよいですか?

置換ありおよび置換なしの重み付きランダム選択

プログラミングの課題に応えて、リストからの重み付きランダム選択のための効率的なアルゴリズムを求めます。

置換による重み付き選択

置換による重み付き選択の効果的な方法の 1 つは、エイリアス メソッドです。この手法では、重み付けされた要素ごとに同じサイズのビンのセットが作成されます。ビット操作を利用することで、二分探索に頼ることなく、これらのビンに効率的にインデックスを付けることができます。各ビンには、元の重み付けされた要素間の境界を表す単一のパーセンテージが格納されます。

等しい重みを持つ 5 つの要素の例を考えてみましょう: (a、b、c、d、e)。

エイリアス メソッドの実装

1. 重みを正規化: 各重みを合計で除算して合計 1.0 にします。
2. その数値以上の 2 の最小累乗を決定します。要素の数 (ここでは 8)。
3. 各要素に空のパーティションを割り当てます。

4. すべての重みが分散されるまで次の手順を繰り返します。

   • 残りの重みが最も少ない要素を空のパーティションにできるだけ多く配置します。
   • パーティションが埋まっていない場合は、残っている最も重い要素を追加します。

この例では、数回の反復の後、次のパーティションが得られます:

• p1: {a, 1.0}
• p2: {a, b, 0.6}

実行時選択

1. 0 から 1 までの乱数を生成します。
2. 乱数をビットシフトしてパーティション インデックスを見つけます。
3. パーティションが分割されている場合は、ビットシフトされた数値の小数部分を使用して、どの要素を返すかを決定します。

置換なしの重み付け選択

アルゴリズム重み付けリザーバー法と同様に、置換なしの重み付けなしの選択に対しても存在しますが、この問題は未解決のままです。

以上が置換ありまたはなしで効率的な加重ランダム選択を実行するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。