java - 要素ごとに特定の確率を持つ配列からランダムに要素を選択する

Question

各要素が特定の確率で選択される配列からランダムに要素を選択したいと考えています。これを行う効率的な方法はありますか、またはこれを既に達成しているJavaに組み込まれている可能性がありますか?

Answer 1

1 つの方法は、次のような加重確率を使用することです。

MyClass getRandomElement(MyClass[] elements)
{
    int totalWeight = 0;
    for (MyClass element : elements)
    {
       totalWeight += element.weight;
    }

    int position = new Random().nextInt(totalWeight);

    for (MyClass element : elements)
    {
       if (position < element.weight)
       {
           return element;
       }
       position -= element.weight;
    }
    throw new IllegalStateException("Should never get here");
}

Answer 2

O(log(n)) アプローチ (これは、非常によく似た質問への回答から直接引き出されます):

通常の手法は、配列を累積和の配列に変換することです。

 [10 60 5 25]  --> [10 70 75 100]

ゼロから累積合計までの範囲で乱数を選択します (例: 0 <= x < 100)。次に、累積配列で二分法を使用して、元の配列のインデックスを見つけます。

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25 

たとえば、確率変数xが 4 の場合、累積配列を 2 等分すると、元の配列の 10 に対応する 0 の位置インデックスが得られます。

また、確率変数xが 72 の場合、累積配列を 2 等分すると、元の配列の 5 に対応する 2 の位置インデックスが得られます。

Answer 3

配列内の要素を選択する確率の重みをエンコードする場合 (おそらく配列内のオブジェクトのメンバー変数を介して)、次のことができます。

1. 重みが整数の要素があるとします。
2. すべての要素の重みを合計します。
3. 1 からその重みの間のランダムな値を作成します。
4. ランダム値に一致するまでカウントアップしながら、配列をウォークスルーします。

例：

[1, 3, 2, 5, 2] 合計 = 13 ランダムロール = 5

element[0] .. (1 まで数えました)

element[1] .. (4 つまで数えました)

element[2] .. (6 まで数えました) 6 > 5 したがって、2 を選択します。

現在、これには O(n) 時間かかります。ここで、n は配列内の値の数です。効率のためにこれを行うより良い方法は、値によって示される位置に値を配置することです。これは次のようなものです。

[a、b、b、b、c、c、d、d、d、d、d、e、e]。

これに関する詳細については、counting sortを参照してください。O(1) アクセスが可能です。

Answer 4

これを行う 1 つの方法は、確率を表すために必要に応じて項目を繰り返す配列を作成することです。したがって、配列内の項目 A の確率が .3 で、項目 B の確率が .7 の場合、それらを 10 項目の配列に入れることができ、A は 3 回繰り返され、B は 7 回繰り返されます。

次に、乱数ジェネレーターを使用して、配列からインデックスを選択できます。

別の解決策は、代わりに各項目とその確率をデータ構造にロードし、各確率を範囲として表して (つまり、項目 A は範囲 .5 ～ .8 を表すことができます)、次に 0 ～ 1 のランダムな値を生成します。乱数が入る範囲の値を取得します。