多数の値 (53,000,000+) を含むデータ ファイルがあり、これらの値のn 個のランダムなサブセット(たとえば、2,000,000) を取り出したいと考えています。リストをメモリに取り込み、 Fisher-Yates メソッドを使用して配列をシャッフルし、シャッフルされたリストの最初のn 個の値を出力する Perl スクリプトを実装しました。ただし、このシャッフル プロセスは、はるかに小さなテスト セット (50,000 値) であっても、かなりの時間を要します。
膨大な値のセットのランダムなサブセットを識別して出力する、より効率的でスケーラブルな方法を探しています。助言がありますか？
更新：回答とさらに検索に基づいて、正しい用語は「ランダムサンプリング」のようです。
上記のaixの回答を詳しく説明kすると、アイテムのストリームから選択するには、一度に1つずつアイテムを読んでください。セット内の最初のk項目を保持しSます。
m今度は- 番目のアイテムI(今)を読むときm>k、確率でそれを保持しk/mます。残す場合はUから一律ランダムに選び、にS置き換える。UI
これが等しい確率でサイズのすべてのサブセットを生成するという証明は、 のk帰納法に基づいていmます。n事前に (項目の総数)を知る必要はなくS、各ステップで適切であることに注意してください。アルゴリズムは「ストリーミング」です。すべてのアイテムを保存したり、2 回目のパスを作成したりする必要はありません。
まず、シャッフルの実装を確認してください。正しく実装されていれば、線形時間が得られるはずです。また、必要な数の要素がシャッフルされた後に停止するようにアルゴリズムを変更します。実際に出力するよりも多くの数をシャッフルする必要は (実際的および理論的に) ありません。
k 個の数を要求すると、k 個の要素操作が必要になります。私はあなたがそれよりもはるかにうまくできるとは思わない。
シャッフルしないでください。不必要に高価です。
Jon Bentley の"Programming Pearls"で説明されている単純な線形アルゴリズムがあります(Bentley は、Knuth の"Seminumerical Algorithms"から学んだと言います)。代わりにこの方法を使用してください。
以下に関するいくつかのPerl 実装があります。
これらの 2 つのスニペットは、Knuth の Art Of Programming の Algortihm S(3.4.2) と Algortihm R(3.4.2) を実装しています。1 つ目は、要素の配列から N 個のアイテムをランダムに選択し、要素を含む配列への参照を返します。リスト内のすべての要素が考慮されるとは限らないことに注意してください。
2 つ目は、不確定なサイズのファイルから N 個の項目をランダムに選択し、選択した要素を含む配列を返します。ファイル内のレコードは行単位であると見なされ、読み取り中に行が切り詰められます。これには、リストを 1 回だけ通過する必要があります。N レコードがメモリ制限を超える状況でスニペットを使用するようにわずかな変更を加えることができますが、これには 1 回よりもわずかに多くのパスが必要です (説明が必要な場合は /msg)。
配列の読み取りとシャッフルには、多くの不要なデータ移動が含まれます。
ここにいくつかのアイデアがあります：
1: ランダムなサブセットが必要だと言うとき、このコンテキストでの「ランダム」とは正確には何を意味しますか? つまり、レコードは特定の順序になっていますか、それともランダム化しようとしているものに関連する順序ですか?
私の最初の考えは、レコードが適切な順序になっていない場合、合計サイズをサンプルサイズで割って計算し、n 番目のレコードごとに選択するだけでランダムに選択できるということです。たとえば、5,300 万件のレコードがあり、200 万件のサンプルが必要な場合、5,300 万 / 200 万 ~= 26 となり、26 番目のレコードごとに読み取ります。
2: それが十分でない場合、より厳密な解決策は、0 から 5,300 万の範囲で 200 万の乱数を生成して、重複がないことを保証することです。
2-A: レコードの総数に比べてサンプル サイズが小さい場合、たとえば、数百または数千を選択する場合のように、多数のエントリの配列を生成し、エントリごとに、それを以前のすべてのエントリと比較して重複をチェックします。重複している場合は、一意の値が見つかるまでループして再試行します。
Two-B: 数値が単なる例ではなく実際の値であると仮定すると、サンプル サイズは母集団全体に比べて大きくなります。その場合、最新のコンピューターに十分なメモリがある場合、false に初期化された 5,300 万個のブール値の配列を作成することで、これを効率的に行うことができます。もちろん、それぞれが 1 つのレコードを表します。次に、ループを 200 万回実行します。反復ごとに、0 ～ 5,300 万の乱数を生成します。配列内の対応するブール値を確認します。false の場合は、true に設定します。正しい場合は、別の乱数を生成して再試行してください。
3: または、待ってください。割合が比較的大きいことを考えると、さらに良いアイデアがあります。含めるレコードの割合を計算します。次に、すべてのレコードのカウンターをループします。それぞれについて、0 から 1 までの乱数を生成し、それを目的のパーセンテージと比較します。少ない場合は、そのレコードを読み取り、サンプルに含めます。それより大きい場合は、レコードをスキップします。
サンプル レコードの正確な数を取得することが重要な場合は、各レコードの割合を再計算できます。たとえば、例を単純にするために、100 レコード中 10 レコードが必要であると仮定しましょう。
10 / 100 = .1 から始めると、乱数が生成され、.04 になるとします。.04<.1 なので、レコード #1 を含めます。
ここで、パーセンテージを再計算します。残りの 99 レコードのうち、あと 9 レコードが必要です 9/99~=.0909 が得られます 乱数が .87 であるとします。それは大きいので、レコード #2 をスキップします。
再計算します。残りの 98 件のレコードのうち、まだ 9 件のレコードが必要です。つまり、マジック ナンバーは 9/98 です。等。
必要な数のレコードを取得すると、将来のレコードの可能性はゼロになるため、決して超えません。終わりに近づいて十分なレコードを取得していない場合、確率は 100% に非常に近くなります。同様に、まだ 8 つのレコードが必要で、8 つのレコードしか残っていない場合、確率は 8/8=100% になるため、次のレコードを取得することが保証されます。