コレクションからランダムなサブセットを選択する最良の方法は？

StackOverflow https://stackoverflow.com/questions/136474

質問

ベクターに一連のオブジェクトがあり、そこからランダムなサブセットを選択します（たとえば、100個のアイテムが戻ってきます。ランダムに5個を選択します）。私の最初の（非常に急いで）パスでは、非常にシンプルで、おそらく非常に賢いソリューションを実行しました。

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

これには素晴らしくシンプルであるという利点がありますが、あまりうまくスケールしないと思います。つまり、少なくともCollections.shuffle（）はO（n）でなければなりません。私のあまり賢くない代替手段は

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

コレクションからランダムなサブセットを引き出すより良い方法に関する提案はありますか？

役に立ちましたか？

解決

Jon Bentleyは、「Programming Pearls」または「More Programming Pearls」でこれについて説明しています。 N of Mの選択プロセスに注意する必要がありますが、表示されているコードは正しく機能していると思います。すべてのアイテムをランダムにシャッフルするのではなく、最初のNポジションだけシャッフルするランダムシャッフルを実行できます。これは、N <！> lt; <！> lt; M。

Knuthはこれらのアルゴリズムについても説明しています-それはVol 3 <！> quot; Sorting and Searching <！> quot;になると思いますが、私のセットは家の移動が保留されているので正式には確認できません。

他のヒント

@ジョナサン、

これがあなたが話している解決策だと思います：

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

Jon BentleyによるProgramming Pearlsの127ページにあり、Knuthの実装に基づいています。

編集：129ページでさらに修正を加えました：

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

これは、<！> quot; ...配列の最初の m 要素のみをシャッフルする必要があるという考えに基づいています... <！> quot;

nのリストからk個の個別の要素を選択しようとしている場合、上記のメソッドはO（n）またはO（kn）になります。ベクターから要素を削除するとarraycopyがすべてシフトするため要素を下に。

最良の方法を求めているので、入力リストで何が許可されているかによって異なります。

例のように入力リストを変更することが許容される場合、k個のランダムな要素をリストの先頭に単純に交換し、次のようにO（k）時間でそれらを返すことができます：

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

リストを開始時と同じ状態にする必要がある場合は、交換した位置を追跡し、選択したサブリストをコピーした後、リストを元の状態に戻すことができます。これはまだO（k）ソリューションです。

ただし、入力リストをまったく変更できず、kがnよりもはるかに小さい場合（100から5など）、選択した要素を毎回削除せずに、各要素を選択するだけの方がはるかに良いでしょう。複製を取得し、それを捨てて再選択します。これにより、O（kn /（n-k））が得られます。これは、nがkを支配している場合でもO（k）に近い値です。 （たとえば、kがn / 2より小さい場合、O（k）になります）。

kがnに支配されておらず、リストを変更できない場合、O（n）はO（k）と同じであるため、元のリストをコピーして最初のソリューションを使用することもできます。

他の人が指摘しているように、すべてのサブリストが可能な（そして公平な）強いランダム性に依存している場合、java.util.Randomよりも強力なものが必要になります。 java.security.SecureRandomを参照してください。

これの効率的な実装数週間前。 C＃ですが、Javaへの変換は簡単です（基本的に同じコード）。プラス面は、完全に偏りがないことです（既存の回答のいくつかはそうではありません）-テストの方法はこちら。

DishtenfeldによるFisher-Yatesシャッフルの実装に基づいています。

Randomを使用して要素を選択する2番目のソリューションは適切に思えます：

費用はどれくらいかかりますか？配列を新しいメモリチャンクに書き換える必要がある場合、以前のO（n）ではなく、2番目のバージョンでO（5n）操作を行ったためです。

falseに設定されたブール値の配列を作成すると、次のようになります。

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

このアプローチは、サブセットが合計サイズよりも大幅に小さい場合に機能します。これらのサイズが互いに近づくと（つまり、サイズの1/4など）、その乱数ジェネレーターでさらに衝突が発生します。その場合、整数のリストをより大きな配列のサイズにして、その整数のリストをシャッフルし、そこから最初の要素を取り出して、（衝突しない）インデックスを取得します。その方法では、整数配列の構築にO（n）のコストがあり、シャッフルに別のO（n）がありますが、内部whileチェッカーからの衝突はなく、削除する可能性のあるO（5n）よりも少ない可能性があります。

最初の実装を個人的に選択します。非常に簡潔です。パフォーマンステストでは、スケーリングの程度が示されます。適切に悪用された方法で非常によく似たコードブロックを実装しましたが、十分に拡張されました。特定のコードは、<！> gt; 10,000個のアイテムも含む配列に依存していました。

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

これは非常によく似た質問ですstackoverflow。

そのページのお気に入りの回答を要約するには（ユーザーKyleの最後の回答）：

  • O（n）ソリューション：リストを反復処理し、要素（またはその参照）を確率（#needed / #remaining）でコピーします。例：k = 5およびn = 100の場合、prob 5/100で最初の要素を取得します。それをコピーする場合、prob 4/99で次を選択します。しかし、最初のものを取らなかった場合、問題は5/99です。
  • O（k log k）またはO（k 2 ）：k個のインデックス（{0、1、...、nの番号）のソート済みリストを作成します-1}）番号をランダムに選択することにより<！> lt; n、次にランダムに数字を選択<！> lt; n-1など。各ステップで、衝突を避け、確率を均等に保つために、選択を思い出す必要があります。例として、k = 5およびn = 100で、最初の選択肢が43の場合、次の選択肢は範囲[0、98]にあり、<！> gt; = 43の場合、1を追加します。 2番目の選択肢が50の場合、1を追加すると{43、51}になります。次の選択肢が51の場合、 2 を追加して{43、51、53}を取得します。

ここにいくつかの擬似Pythonがあります-

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

時間の複雑さはO（k 2 ）または O（k log k）であると言っていますsのコンテナ。 sが通常のリストの場合、これらの演算の1つは線形であり、k ^ 2を取得します。ただし、バランスの取れたバイナリツリーとしてsを作成する場合は、O（k log k）時間を取得できます。

ここに表示されないと思われる2つの解決策-対応は非常に長く、いくつかのリンクが含まれていますが、すべての投稿がセットからK要素を選択する問題に関連するとは思いませんN個の要素。 [<！> quot; set <！> quot;で、数学用語を参照します。つまり、すべての要素が一度表示されます。順序は重要ではありません。]

ソル1：

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

これはダニエルが出した答えに似ていますが、実際には非常に異なっています。 O（k）ランタイムのものです。

別の解決策は、数学を使用することです。 配列のインデックスをZ_nとみなし、ランダムに2つの数字を選択できます。xはnと同じ数で、つまりgcd（x、n）= 1を選択し、別のaは<！> quot; startingpoint < ！> quot; -その後、シリーズ：a％n、a + x％n、a + 2 * x％n、... a +（k-1）* x％nは一連の個別の数字です（k <！> lt; = n）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top