Nレコード（N> M）のファイルからランダムにMレコード（ファイル内の各レコードが同じ確率で選択できる）を選択する必要があります。一度しかファイルを読み取ることができないのではないかと思いますか？NレコードのファイルからランダムにMレコードを選択する
私が考えている唯一の方法は、確率M/Nで各レコードを選択することですが、この方法ではM以上のM個のレコードより少なくなる可能性があります。
よりスマートなアイデアは高く評価されます。その後、
に関して、 林
リザーバーサンプリングアルゴリズム（link）が必要なのでしょうか？
あなたは、確率が等しいM個のレコードを正確に取得するだけでなく、入力を1回読むだけで済み、事前にNを知る必要はありません。
複雑さはO（N）です。
選択Mユニーク乱数、それらを並べ替え、配列に入れて、一度にファイルを読み込みます。ファイルのi番目のレコードを読むときは、iが配列に含まれている場合はそのままにしてください。それ以外の場合は破棄してください。これはメモリがO(M)で、実行時間はO(N + M log M)です。
超スマート、すばらしいTheGreatContini！ –
時間が許せば、あなたの返事を答えとして記入してください。あなたがとても速く答えたように。クール。 :) –
私はファイルのサイズがわからない場合は、TheGreatContini、それは重要ですか？ありがとう。 –
ありがとうSorin、スマートに見える、より詳細に読む前に投票する。 :) –
こんにちはソリン、アルゴリズムを研究し、あなたが言及したウィキペディアのページでこの結論に混乱しています - 「すべて私にとって、Sのi番目の要素は確率k/iで貯水池に含まれるように選択されます。」、私の混乱Sの最初のk個の要素がS内の残りの要素と比較して含まれる確率が等しいかどうかにかかわらず、最初のk個の要素については、ありがとう。 –
はい、彼らは等しい確率を持っています。これは、後の要素で置き換えることができるからです。 「k = 1」の貯水池があるとします。したがって、最初の要素がリザーバに残る確率は（デフォルトでそれを追加するので） 'product（i = 2-> N; 1 - 1/i）'であり、これは1/N（あなたが望むもの）です。より一般的なケースではk/Nを得るべきです。後の要素に対して同じ計算を行うことができ、すべてがk/Nになるはずです。このことは、実行中にも当てはまります。したがって、途中で停止すると、貯水池はこれまでに見た要素の等確率サンプルを保持します。 – Sorin