これは、選択されたテキスト行の確率が 1/X である X 行のテキストからランダムな行を選択するという元の質問の拡張です。[0,1) の範囲で確率変数 Y をクエリし、1/J 未満の値を返す場合は、J 番目の行を選択するのがコツです。
この問題の新しいバージョンでは、K が X より小さいランダムな行を選択する必要があります。各行の確率は K/X になるはずです。
元のソリューションをK行に拡張する方法に固執しています。出来ますか？どんな説明も素晴らしいでしょう。
2 に答える
8
これは、元のアルゴリズムの一般化を使用して解決できます。直観は次のとおりです。最初に最初の k 行にシードされる、ファイルからの k 候補行のリストを維持します。次に、その時点から、ファイルの n 行目を確認すると、次のようになります。
- 1 から n までのランダムな値 x を選択します。
- x > k の場合、この要素を無視します。
- それ以外の場合は、要素 x をファイルの n 行目に置き換えます。
これが各要素を確率 k / n (n はファイル内の合計行数) で正しくサンプリングすることの証明は次のとおりです。n ≥ k であると仮定します。z 個の要素を見た後、それらの要素のそれぞれが選択される確率 k / z を持つことを示すことによって、各要素が選択される確率 k / n を持つことを帰納法によって証明します。特に、これは n 個の要素を見た後、それぞれが必要に応じて確率 k / n を持つことを意味します。
帰納的基底として、正確に k 個の要素が表示される場合、それぞれが選択されます。したがって、選択される確率は、必要に応じて k / k です。
誘導ステップでは、いくつかの z ≥ k について、最初の z 要素のそれぞれが確率 k / z で選択されていると仮定し、(z + 1) 番目の要素を考えます。[1, z + 1] の範囲のランダムな自然数を選択します。確率 k / (z + 1) で、この要素を選択することを決定し、古い要素を削除します。これは、新しい要素が確率 k / (z + 1) で選択されることを意味します。z 個の元の要素のそれぞれについて、この時点でそれが選択される確率は、最初の z 個の要素が検査された後に選択された確率 (帰納的仮説による確率 k / z) であり、確率 1 / (z + 1) に置き換えるため、z / (z + 1) のままにします。したがって、それが選択される新しい確率は (k / z) (z / (z + 1)) = k / (z + 1) です。
さらに、このアルゴリズムは O(n) 時間で実行され、O(k) スペースのみを使用します。つまり、ランタイムは k の値に依存しません。これを確認するには、各反復が O(1) 回の作業を行い、合計 O(n) 回の反復があることに注意してください。
興味がある方は、このアルゴリズムを C++ STL スタイルのアルゴリズムとして実装したものを、私の個人サイト で入手できます。
お役に立てれば！
于 2011-12-01T02:55:33.903 に答える
-2
最初に、最初のアルゴリズムを使用して、X線からランダムに最初の要素を選択します。次に、残りのX-1行から2番目を選択します。このプロセスをK回実行します。
Kラインの任意のセットの確率はです(X choose K)。このアルゴリズムが目的の一様分布を与えることを確認するのはあなたに任せます。
于 2011-12-01T02:25:46.493 に答える