0

以下は、Knuth の Reservoir Sampling の疑似コードです (k一連の数値から数値を選択nし、すべての数値の確率が同じであることを確認する方法)。

Init: サイズ：<code>k のリザーバー。

for i = k+1 to N
    M = random(1, i);

    if (M < k) // should this be if (M <= k)
       SWAP the Mth value and ith value
    end if    
end for

このコードから、 の確率M < Kは(k-1)/iではなくであるため、ループ本体のステートメントは である必要があるk/iと思います。それらの違いをテストしようとしましたが、どこにも行きませんでした。ifif (M < =k)

4

2 に答える 2

4

あなたが正しいです。ただし、あなたのコードはアルゴリズム R を正しく実装していません。バグはあなた (またはこのコードを書いた人) のものであり、Knuth のものではありません ;-)

Knuth からの引用 (The Art of Computer Programming Vol.2 3Ed 1998, p.144):

... アルゴリズム S では N の正確な値が重要であるため、N の値が事前にわからないと問題が発生します。ファイルから n 個のアイテムをランダムに選択するとします。そのファイルに存在します。最初にレコードを調べて数え、次に 2 回目のパスでレコードを選択することができます。ただし、通常は、最初のパスで m > n の元のアイテムをサンプリングすることをお勧めします。ここで、m は N よりもはるかに小さいため、2 番目のパスでは m 個のアイテムのみを考慮する必要があります。もちろん、秘訣は、最終結果が元のファイルの真にランダムなサンプルになるようにこれを行うことです。

入力がいつ終了するかわからないため、これまでに見た入力レコードのランダムなサンプルを追跡し、常に終了に備える必要があります。入力を読み取ると、前のサンプルに表示されたレコードのみを含む「リザーバー」を構築します。最初の n レコードは常にリザーバーに入ります。(t + 1) 番目のレコードが入力されると、t>n の場合、最初の t の中から選択したレコードを指す n 個のインデックスのテーブルがメモリに保持されます。問題は、t を 1 増やしてもこの状況を維持することです。つまり、現在存在することがわかっている t + 1 レコードの中から新しいランダム サンプルを見つけることです。n/(t + 1) の確率で新しいサンプルに新しいレコードを含める必要があることを理解するのは難しくありません。

したがって、次の手順でジョブを実行します。

アルゴリズム R (リザーバー サンプリング)。未知のサイズ > n のファイルからランダムに n レコードを選択するには、n > 0 を指定します。「リザーバー」と呼ばれる補助ファイルには、最終サンプルの候補となるすべてのレコードが含まれます。このアルゴリズムは、1 < j < n に対して個別のインデックスI [j] のテーブルを使用します。各インデックスは、リザーバー内のレコードの 1 つを指します。

R1. [初期化] 最初の n レコードを入力し、それらをリザーバーにコピーします。1 < j < n に対してI [j] ← j を設定し、t ← m ← n を設定します。(サンプリングされているファイルのレコードが n 未満の場合は、もちろんアルゴリズムを中止して失敗を報告する必要があります。このアルゴリズムの間、インデックスI [1]、...、I [n] は、現在のサンプル、m はリザーバーのサイズ、t はこれまでに処理された入力レコードの数です。)

R2. ［ファイル終了？］ 入力するレコードがなくなったら、手順 R6 へ。

R3. [生成してテストする。] t を 1 増やしてから、1 から t (両端を含む) の間のランダムな整数 M を生成します。M > n の場合、R5 に進みます。

R4. [リザーバーに追加] 入力ファイルの次のレコードをリザーバーにコピーし、m を 1 増やし、I[M] ← m とする。(以前に I[M] が指していたレコードは、サンプル内で新しいレコードに置き換えられています。) R2 に戻ります。

R5. [Skip.] 入力ファイルの次のレコードをスキップして (リザーバーには含めないでください)、ステップ R2 に戻ります。

R6. [2 回目のパス] IテーブルのエントリをI [1] < ... < I [n] となるように並べ替えます。次にリザーバーを通過し、これらのインデックスを持つレコードを最終サンプルを保持する出力ファイルにコピーします。

アルゴリズム R の疑似コードは次のようになります。

for j= 1 to n
    Reservoir[j]= File.GetNext()
    I[j]= j

t=n // number of input records so far
m=n // size of the reservoir

while not File.EOF()
    x= File.GetNext()
    t++
    M= Random(1..t)
    if (M<=n)
        m++
        Reservoir[m]= x
        I[M]= m

Sort(I[1..n])

for j= 1 to n
    Output[j]= Reservoir[I[j]]
于 2013-07-14T20:22:35.577 に答える