リンクされたリストからランダムな要素のセットを効率的に選択する
https://stackoverflow.com/questions/54059
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
長さの数値のリンクされたリストがあるとします N. N は非常に大きいため、正確な値は事前にわかりません N.
を返す関数を最も効率的に作成するにはどうすればよいですか k 完全に 乱数 リストから?
解決
これには、と呼ばれるメソッドを使用する非常に優れた効率的なアルゴリズムがあります。 貯留層のサンプリング.
まずはその内容をお届けしましょう 歴史:
クヌース このアルゴリズムを p.2 で R と呼んでいます。彼の 1997 年版 Seminumerical Algorithms (The Art of Computer Programming の第 2 巻) の 144 に、いくつかのコードが記載されています。Knuth 氏は、このアルゴリズムは Alan G の功績であると考えています。ウォーターマン。長い検索にもかかわらず、ウォーターマンの元の文書が存在するとしても見つけることができませんでした。このアルゴリズムのソースとしてクヌースが引用されているのをよく見かけるのはそのためかもしれません。
マクロードとベルハウス、1983 年 (1) Knuth よりも徹底的な議論と、アルゴリズムが機能することを示す最初の公開された証拠 (私が知っている限り) を提供します。
ヴィッター 1985 (2) アルゴリズム R をレビューし、同じ出力を提供する追加の 3 つのアルゴリズムを提示しますが、ひねりが加えられています。彼のアルゴリズムは、各受信要素を含めるかスキップするかを選択するのではなく、スキップする受信要素の数を事前に決定します。彼のテスト (明らかに、現在では最新ではありません) では、乱数の生成と受信する各数値の比較を回避することで、実行時間が大幅に短縮されました。
で 疑似コード アルゴリズムは次のとおりです。
Let R be the result array of size s
Let I be an input queue
> Fill the reservoir array
for j in the range [1,s]:
R[j]=I.pop()
elements_seen=s
while I is not empty:
elements_seen+=1
j=random(1,elements_seen) > This is inclusive
if j<=s:
R[j]=I.pop()
else:
I.pop()
入力のサイズを指定しないように特別にコードを作成したことに注意してください。これは、このアルゴリズムの優れた特性の 1 つです。入力のサイズを事前に知る必要がなくても実行できます。 まだ 遭遇する各要素が同じ確率で最終的に到達することを保証します。 R （つまり、偏見はありません）。さらに、 R アルゴリズムが常に考慮した要素の公正で代表的なサンプルが含まれています。これは、これを次のように使用できることを意味します オンラインアルゴリズム.
なぜこれが機能するのでしょうか?
McLeod と Bellhouse (1983) は、組み合わせの数学を使用して証明を提供しています。きれいですが、ここで再構築するのは少し難しいでしょう。したがって、説明しやすい別の証明を作成しました。
帰納法による証明を進めていきます。
のセットを生成したいとします。 s 要素と私たちがすでに見たもの n>s 要素。
現在の状況を仮定しましょう s 要素はそれぞれ確率ですでに選択されています s/n.
アルゴリズムの定義により、要素を選択します n+1 確率的に s/(n+1).
すでに結果セットの一部となっている各要素には確率があります 1/s 置き換えられること。
の要素が n-seen 結果セットは n+1したがって、-seen 結果セットは (1/s)*s/(n+1)=1/(n+1). 。逆に、要素が置換されない確率は次のようになります。 1-1/(n+1)=n/(n+1).
したがって、 n+1-seen 結果セットには、要素が要素の一部である場合、その要素が含まれます。 n- 結果セットが表示されたが置換されなかった---この確率は (s/n)*n/(n+1)=s/(n+1)---または要素が選択された場合---確率で s/(n+1).
アルゴリズムの定義によれば、最初の s 要素は自動的に最初に組み込まれます n=s 結果セットのメンバー。したがって、 n-seen 結果セットには、次の各要素が含まれます。 s/n (=1) 帰納法に必要な基本ケースを与える確率。
参考文献
他のヒント
これはと呼ばれます 貯留層のサンプリング 問題。簡単な解決策は、ご覧のようにリストの各要素に乱数を割り当て、上位 (または下位) k 個の要素を乱数の順序に従って保持することです。
私は次のように提案します:まず、k 個の乱数を見つけます。並べ替えてください。次に、リンクされたリストと乱数の両方を 1 回調べます。
リンクされたリストの長さがどういうわけかわからない場合 (どうやって?)、最初の k を配列に取得し、ノード r に対して [0, r) に乱数を生成します。それより短い場合は、 k よりも、配列の r 番目の項目を置き換えます。(それが偏見ではないという確信はありません...)
それ以外：「もし私があなただったら、私はここから始めないだろう。」リンクされたリストは問題に適していますか？古き良きフラット配列リストなど、もっと優れたデータ構造はないのでしょうか。
リストの長さがわからない場合は、リストを完全に調べてランダムに選択する必要があります。この場合に私が使用した方法は、Tom Hawtin によって説明された方法です (54070）。保存したリストを確認しながら k その時点までのランダムな選択を形成する要素。(最初は最初のものを追加するだけです k 遭遇する要素。）そして、確率で k/i, 、選択した要素からランダムな要素を iリストの 番目の要素 (つまり、その瞬間にあなたがいる要素）。
これによりランダムな選択が行われることを示すのは簡単です。見た後 m 要素 (m > k)、最初のそれぞれの m リストの要素は確率でランダムに選択されたものです k/m. 。これが最初から成り立つことは些細なことです。次に要素ごとに m+1, 、確率でそれを選択範囲に入れます（ランダムな要素を置き換えます）。 k/(m+1). 。次に、他のすべての要素にも確率があることを示す必要があります。 k/(m+1) 選ばれること。確率は次のとおりです。 k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (すなわち、要素がリストに存在する確率と、それがまだ存在する確率の積です)。微積分を使用すると、これが以下に等しいことを直接示すことができます。 k/(m+1).
そうですね、リストをカウントするために追加のパスを実行する必要がある場合でも、少なくとも実行時には N が何であるかを知る必要があります。これを行う最も簡単なアルゴリズムは、N から乱数を選択し、その項目を削除することを k 回繰り返すことです。または、繰り返し番号を返すことが許可されている場合は、項目を削除しないでください。
N が非常に大きく、非常に厳しいパフォーマンス要件がない限り、このアルゴリズムは次のように実行されます。 O(N*k) 複雑さは許容できるはずです。
編集：気にしないでください、トム・ホーティンの方法ははるかに優れています。最初に乱数を選択し、次にリストを 1 回調べます。理論的な複雑さは同じですが、期待される実行時間ははるかに優れていると思います。
なぜ次のようなことができないのですか
List GetKRandomFromList(List input, int k)
List ret = new List();
for(i=0;i<k;i++)
ret.Add(input[Math.Rand(0,input.Length)]);
return ret;
そんな単純なことを言っているわけではないと思いますので、さらに具体的に教えていただけますか？
