データファイルには多数の値（53,000,000+）があり、n（たとえば、2,000,000）というランダムなサブセットを取り出したいと思います。私はリストをメモリにプルするPerlスクリプトを実装し、Fisher-Yates methodを使って配列をシャッフルし、シャッフルリストの最初のnの値を出力します。しかし、このシャッフル処理は、さらに小さなテストセット（50,000値）であっても、の多くの時間をとしています。巨大リストからの効率的なランダムサンプリング
私は、より効率的でスケーラブルな方法で、巨大な値のセットのランダムな部分集合を特定し、それを印刷する方法を探しています。助言がありますか？
更新：回答といくつかのより多くの検索に基づいて、正しい用語が「ランダムサンプリング」であるように見えます。
上記のaixの答えを精緻化し、項目の流れからkを選択するには、項目を一度に1つずつ読みます。最初のkの項目はセットSのままにしておきます。
m番目のアイテムI（現在はm>k）を読むときは、確率k/mで保管してください。このままにしておく場合は、Uをランダムにランダムに選択してSから選択し、UをIに置き換えてください。
等しい確率でサイズkのすべてのサブセットが得られるという証明は、mの誘導に基づいています。 n（アイテムの総数）を事前に知る必要はなく、各ステップでSが適切であることに注意してください。アルゴリズムは「ストリーミング」です。すべてのアイテムを格納する必要はなく、2回目のパスを作成する必要もありません。
これはオンラインアルゴリズムであり、未知のサイズのストリームに最適です。サイズはここで分かりますので、それ以上のことができます –
nが事前にわかっているときは、乱数ジェネレータ（nではなくk）への呼び出しを減らす必要があります。メモリ内のセット。 （N） – adnan
ではなく、O（1）空間を使用します。このセットがすでにメモリ内にある場合、時間の複雑さはO（k）にすぎません。 。そうでなければ、それはメモリ対スピードのトレードオフなので、そういう意味ではあなたは正しい。 –
まず、シャッフルの実装を確認します。あなたが線形時間を与える必要があります正しく実装されている場合。また、必要な数の要素がシャッフルされた後に、アルゴリズムが停止するように修正します。実際に出力する数よりも多くの数値をシャッフルする必要はありません（実際的かつ理論的に）。
k個の番号を尋ねると、これは基本的な操作にかかります。私はあなたがそれよりずっと良いことをすることはできないと思う。
メモリが豊富な場合は、これがタスクのための最良のアルゴリズムです –
シャッフルしないでください。不必要に高価です。
ジョンベントレーの"Programming Pearls"（ベントレーはKnuthの"Seminumerical Algorithms"から学んだと言います）に記載されているsimple linear algorithmがあります。この方法を代わりに使用してください。
これら二つのスニペットは、プログラミングのKnuthのアートからAlgortihm S（3.4.2）とAlgortihm R（3.4.2） を実装：
は、いくつかのPerl implementations程度あります。最初の要素は要素の配列からN個の項目 をランダムに選択し、要素を含む配列 への参照を返します。リスト内のすべての要素が必ずしも とはみなされないことに注意してください。
第2は、不確定サイズ のファイルからN個の項目をランダムに選択し、選択された要素を含む配列を返します。 ファイル内のレコードは1行であるとみなされ、の読み取り中に行がチャンプされます。これは、リストを1回だけ通過する必要があります。わずか 変更がN レコードはメモリの制限を超えてしまう状況でスニペットを使うようにすることができる（あなたがこの説明が必要な場合は/ MSG）、しかしこれは わずか1以下のパスを必要と
読書とシャッフル配列には多くの不必要なデータの移動が含まれます。ここで
はいくつかのアイデアです：
ワン：あなたはランダムなサブセットを必要と言うとき、あなたはこの文脈では「ランダム」で正確に何を意味するのですか？つまり、レコードが特定の順序であるか、ランダム化しようとしているものと関連する順序ですか？
私の最初の考えは、レコードが関連する順序にない場合は、合計サイズをサンプルサイズで割って計算し、次にn番目のレコードを選択することによってランダムな選択を得ることができるということです。たとえば、5300万のレコードがあり、200万のサンプルが必要な場合は、5300万/ 200万~26の値を取るので、26レコードごとに読み取ります。
2：これで十分でない場合は、重複がないことを保証して、ゼロから5300万の範囲で200万の乱数を生成することがより厳密な解決策になります。
Two-A：サンプルサイズがレコードの総数に比べて小さかった場合、数百から数千を選んでいるような場合は、各エントリについて、前のすべてのエントリと比較して重複をチェックします。重複している場合は、周りを回り、ユニークな値が見つかるまで再度試してください。
Two-B：数字が単なる例ではなく実際の値であると仮定すると、サンプルサイズは総人口に比べて大きくなります。その場合、現代のコンピュータに十分なメモリがあれば、偽に初期化された5300万のブール値の配列を作成することで、効率的にこれを行うことができます。その後、200万回ループを実行します。反復ごとに、0から5300万の乱数を生成します。配列の対応するブール値を確認します。falseの場合はtrueに設定します。それが本当であれば、別の乱数を生成してやり直してください。
3つ：または、比較的大きな割合を考えれば、より良いアイデアはまだあります。含めるレコードの割合を計算します。次に、すべてのレコードのカウンタをループします。それぞれに対して、0から1までの乱数を生成し、それを所望の割合と比較する。それが少ない場合は、そのレコードを読んでサンプルに含める。それが大きい場合は、レコードをスキップします。
サンプルレコードの正確な数を取得することが重要な場合は、各レコードの割合を再計算できます。たとえば、例を単純にすると、100レコードのうち10レコードが必要です。
10/100 = .1で始めるので、乱数を生成します。 .04 < .1だから、私たちはレコード＃1を含む。
ここで、パーセンテージを再計算します。私たちは残りの99のうち9つのレコードを残したい9/99〜= .0909私たちの乱数は.87です。それは大きいので、レコード＃2はスキップします。
もう一度再計算してください。残りの98個のうち9個のレコードが必要です。だからマジックナンバーは9/98です。等
私たちが望むだけの数のレコードを取得すると、将来のレコードの確率はゼロになるので、決して進まないでしょう。終わり近くに十分なレコードを拾っていないと、確率は100％に非常に近くなります。同様に、まだ8つのレコードが必要で、8つのレコードしか残っていない場合、確率は8/8 = 100％になりますので、次のレコードを取得することが保証されます。
どうやって交換していますか？ I/Oがボトルネックかシャッフルしていますか？おそらく、いくつかのコードも役に立ちます。 – delnan
@delnanリンクされたスレッドで説明されている両方の方法を試しました。 I/Oは間違いなく問題ありません。それはかなり素早くメモリにロードされますが、シャフリングのステップで*多くの時間を費やします。決して印刷を終了せずに印刷を開始します。今私はそれを試してみましたが、シャッフルアプローチがこのような多くの価値に対して十分に効率的になるとは思わないので、私はおそらく代替アプローチにもっと興味があります。 –
どのようにランダムにデータが必要ですか？ランダムな記号でジャンプし、重複を避けるために要素を検索した後、その要素を「使用済み」とマークするループを使用することができます。 –