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

プログラミングの課題に応えて、リストからの加重ランダム選択の効率的なアルゴリズムを求めます。置換ありと置換なしの両方。

置換ありの加重選択

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

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

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

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

4. すべてのウェイトが分散されるまで次の手順を繰り返します。

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

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

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

実行時選択

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

置換なしの重み付き選択

置換なしの重みなし選択には重み付きリザーバー法のようなアルゴリズムが存在しますが、この問題は未解決のままです。