1

与えられたS個の要素のセットからk<=Sとなるk個の要素を選択するリザーバーサンプリングアルゴリズムを理解したいと思います。

ウィキで与えられたアルゴリズムでは：

array R[k];    // result
integer i, j;

 // fill the reservoir array

for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability

for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

これを正しく理解していれば、最初にセットからk個の要素を選択し、次にSのi個の要素を連続的に解析し、1からiの範囲のランダムなno jを生成し、要素jをS[i]に置き換えます。

サンプリングされるセットKが非常に大きい場合は問題ないように見えますが、無限サイズ（少なくとも未知のサイズ）のリンクリストから1つの要素だけをランダムに選択したい場合は、このアルゴリズムでどのように行いますか... ？

4

2 に答える 2

3

リザーバーサンプリングアルゴリズムは、長さが事前に不明なものも含め、任意のサイズのリンクリストで機能します。実際、貯留層サンプリングの主なセールスポイントの1つは、サイズが事前にわかっていないデータストリームで機能することです。

k = 1に設定してから、通常のリザーバーサンプリングアルゴリズムを実行すると、リストから均一にランダムな要素を正しく取得する必要があります。

お役に立てれば！

于 2013-01-20T21:25:50.133 に答える
0

この問題を解決するために別のアルゴリズムを実装しました。これが私のコードです

static char[] solution2(String stream, int K) {
    HashSet<Integer> set = new HashSet();
    char[] list = new char[K];
    stream = stream.concat(stream2);
    Random ran = new Random();
    for (int i = 0; i < K; i++) {
        int y = ran.nextInt(stream.length());
        if (set.add(y)) {
            list[i] = stream.charAt(y);
        } else {
            i--; //skip this iteration since its duplicate number
        }
    }
    return list;
}

すべてのストリーム値を反復処理する代わりに、ランダムな値Jを選択して、ストリームからN[J]を取得します。

于 2016-09-23T17:08:50.430 に答える