単純無作為抽出のナイーブアルゴリズム(naive algorithm)の欠点は何ですか？
単純なランダムサンプリングのためのいくつかの効率的なアルゴリズムが開発されている。素朴なアルゴリズムは、各ステップで、等確率でセットからそのステップの項目を削除し、サンプルにアイテムを置くドローバイドローアルゴリズムである.目的の大きさのサンプルができるまで続ける
k.この方法の欠点は、集合のランダムアクセスを必要とすることです。

1962年にFanらによって開発された選択-棄却アルゴリズムは、データに対して1回のパスで済むが、逐次アルゴリズムであるため、アイテムの総カウント数を知っている必要があります。
n、ストリーミングシナリオでは利用できない。

1977年にSunterによって非常に単純なランダムソートアルゴリズムが証明されました。このアルゴリズムは、単に一様分布から引いた乱数を
(
0
,
1
)
(0,1)を各項目のキーとし、そのキーで全項目をソートし、最も小さいものを選択します。
k項目です。

J.Vitterは1985年にリザーバー・サンプリング・アルゴリズム(reservoir sampling algorithms)を提案し、広く利用されています。このアルゴリズムでは、母集団の大きさに関する知識は必要ない
nをあらかじめ用意しておき、一定の空間を使用する。
ランダムサンプリングは、サンプル間の隙間の分布からサンプリングし、隙間を飛び越えることによっても高速化することができます。
この方法の欠点は、セット内のランダムアクセスが必要であることです。