70

ベクトルに一連のオブジェクトがあり、そこからランダムなサブセットを選択したい (例: 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())));
}

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

4

10 に答える 10

12

Jon Bentley は、「Programming Pearls」または「More Programming Pearls」でこれについて説明しています。N of M の選択プロセスには注意が必要ですが、示されているコードは正しく機能すると思います。すべてのアイテムをランダムにシャッフルするのではなく、最初の N 個の位置のみをシャッフルするランダム シャッフルを実行できます。これは、N << M の場合に便利な節約になります。

Knuth はこれらのアルゴリズムについても説明しています。Vol 3 の「Sorting and Searching」になると思いますが、私のセットは家を引っ越すまで詰め込まれているため、正式に確認することはできません。

于 2008-09-25T22:35:59.303 に答える
9

@ジョナサン、

私はこれがあなたが話している解決策だと信じています：

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--;
         }
}

これは、JonBentleyによるProgrammingPearlsの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";
}

これは、「...配列の最初のm個の要素のみをシャッフルする必要がある...」という考えに基づいています。

于 2008-09-25T22:57:39.093 に答える
5

n個のリストからk個の個別の要素を選択しようとしている場合、上記で指定したメソッドはO（n）またはO（kn）になります。これは、ベクトルから要素を削除すると、アレイコピーによってすべての要素が下にシフトするためです。 。

あなたは最善の方法を求めているので、それはあなたがあなたの入力リストで何をすることが許されているかに依存します。

例のように入力リストを変更できる場合は、次のように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のように）、選択した要素を毎回削除するのではなく、各要素を選択する方がはるかに良いでしょう。複製し、それを捨てて再選択します。これにより、nがkを支配する場合でもO（k）に近いO（kn /（nk））が得られます。（たとえば、kがn / 2未満の場合、O（k）になります）。

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

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

于 2008-09-25T23:26:39.493 に答える
4

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

これは、フィッシャー-イェーツシャッフルのダーステンフェルド実装に基づいています。

于 2008-09-25T23:06:37.107 に答える
2

ただし、ランダムを使用して要素を選択する2番目の解決策は適切なようです。

于 2008-09-25T22:10:18.630 に答える
1

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

そのページからの私のお気に入りの回答を要約するには (ユーザー Kyle からの最初の回答):

  • O(n) ソリューション: リストを反復処理し、要素 (またはそれへの参照) を確率 (#needed / #remaining) でコピーします。例: k = 5 で n = 100 の場合、確率 5/100 の最初の要素を取得します。それをコピーすると、確率 4/99 の次のものを選択します。しかし、最初のものを取らなかった場合、確率は 5/99 です。
  • O(k log k) または O(k 2 ) : n 未満の数値をランダムに選択してから、数値をランダムに選択して、k 個のインデックス ({0, 1, ..., n-1} の数値) のソート済みリストを作成します。 < n-1 など。各ステップで、衝突を回避し、確率を均等に保つために、選択を再調整する必要があります。例として、k=5 および n=100 で最初の選択肢が 43 の場合、次の選択肢は [0, 98] の範囲にあり、それが >=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) の時間を得ることができます。

于 2008-09-26T01:26:30.813 に答える
0 
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));
}
于 2008-09-25T23:05:15.520 に答える
0

撤去費用はどのくらい？配列を新しいメモリ チャンクに書き換える必要がある場合は、以前に必要だった 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) 未満のコストがかかる可能性があります。

于 2008-09-25T22:17:25.307 に答える
0

私はあなたの最初の実装を個人的に選択したいと思います: 非常に簡潔です。パフォーマンス テストにより、その拡張性が示されます。非常によく似たコード ブロックを適切に悪用されたメソッドに実装しましたが、十分にスケーリングされました。特定のコードは、10,000 個を超える項目を含む配列にも依存していました。

于 2008-09-25T22:18:16.053 に答える
0

ここには表示されないと思う2つの解決策-対応するものは非常に長く、いくつかのリンクが含まれていますが、すべての投稿がN要素のセットからK要素のサブストを選択する問題に関連しているとは思いません. [「セット」とは、数学用語を指します。つまり、すべての要素が 1 回出現し、順序は重要ではありません]。

ソル 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) です。

もう 1 つの解決策は、いくつかの数学を使用することです。配列インデックスを Z_n と見なすと、n と互いに素な x をランダムに選択できます。つまり、gcd(x,n)=1 を選択し、別の a を選択します。 「開始点」 - 系列: a % n,a+x % n, a+2*x % n,...a+(k-1)*x%n は、一連の異なる数値です ( k<=n)。

于 2012-03-03T22:09:43.057 に答える