40

長さの数のリンクリストがあるとしますN。Nは非常に大きく、の正確な値は事前にわかりませんN。

リストからk完全に乱数を返す関数を最も効率的に作成するにはどうすればよいですか？

4

6 に答える 6

42

これには、貯水池サンプリングと呼ばれる方法を使用した非常に優れた効率的なアルゴリズムがあります。

その歴史を紹介することから始めましょう：

Knuthは、こ​​のアルゴリズム R を p で呼び出します。彼の 1997 年版の Seminumerical Algorithms (The Art of Computer Programming の第 2 巻) の 144 で、そのコードがいくつか提供されています。Knuth は、こ​​のアルゴリズムを Alan G. Waterman に帰属させます。長時間の検索にもかかわらず、Waterman の元の文書が存在するとしても見つけることができませんでした。これが、このアルゴリズムのソースとしてクヌースが引用されているのを最も頻繁に目にする理由かもしれません.

McLeod と Bellhouse、1983 年(1) は、Knuth よりも徹底的な議論を提供し、アルゴリズムが機能することを (私が知っている) 最初に公開された証明を提供します。

Vitter 1985 (2) は Algorithm 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置き換えられる可能性があります。

したがって、 -seen 結果セットの要素がn-seen 結果セットで置き換えられる確率n+1は です(1/s)*s/(n+1)=1/(n+1)。逆に、要素が置き換えられない確率は です1-1/(n+1)=n/(n+1)。

したがって、n+1-seen 結果セットには、要素がn-seen 結果セットの一部であり、置換されていない場合、要素が含まれます --- この確率は(s/n)*n/(n+1)=s/(n+1)--- または、要素が選択された場合 --- 確率s/(n+1)です。

アルゴリズムの定義は、最初のs要素がn=s結果セットの最初のメンバーとして自動的に含まれることを示しています。したがって、n-seen結果セットには、s/n(=1) の確率で各要素が含まれ、誘導に必要な基本ケースが得られます。

参考文献

  1. マクラウド、A. イアン、デビッド R. ベルハウス。「単純なランダム サンプルを描画するための便利なアルゴリズム。」王立統計学会誌。シリーズ C (応用統計) 32.2 (1983): 182-184。(リンク)

  2. Vitter、Jeffrey S.「リザーバーによるランダムサンプリング」。ACM Transactions on Mathematical Software (TOMS) 11.1 (1985): 37-57. (リンク)

于 2014-01-18T07:31:39.577 に答える
34

これは、リザーバーサンプリングの問題と呼ばれます。簡単な解決策は、リストの各要素にランダムな番号を割り当ててから、上位（または下位）のk個の要素を乱数順に保持することです。

于 2008-09-10T13:54:13.030 に答える
2

私は提案します：最初にあなたのk個の乱数を見つけてください。それらを並べ替えます。次に、リンクリストと乱数の両方を1回トラバースします。

リンクリストの長さがわからない場合は（どのように？）、最初のkを配列に取り込み、ノードrについて、[0、r）で乱数を生成します。 kよりも、配列のr番目の項目を置き換えます。（バイアスがないことを完全に確信しているわけではありません...）

それ以外は、「もし私があなただったら、ここから始めないだろう」。リンクリストがあなたの問題に適していると確信していますか？古き良きフラット配列リストなど、より良いデータ構造はありませんか。

于 2008-09-10T13:45:28.900 に答える
1

リストの長さがわからない場合は、ランダムに選択するためにリストを完全にトラバースする必要があります。この場合に使用した方法は、Tom Hawtin（54070）によって説明された方法です。リストをトラバースしている間、kその時点までランダムな選択を形成する要素を保持します。（最初は、最初kに遭遇した要素を追加するだけです。）次に、確率k/iで、選択したランダムな要素をiリストのth番目の要素（つまり、その時点での要素）に置き換えます。

これがランダムな選択を与えることを示すのは簡単です。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)。

于 2008-09-10T14:22:07.487 に答える
-3

ええと、たとえこれがそれらを数えるためにリストの上に余分なパスをすることを含むとしても、あなたは少なくとも実行時にNが何であるかを知る必要があります。これを行う最も簡単なアルゴリズムは、Nの乱数を選択し、そのアイテムを削除して、k回繰り返すことです。または、繰り返し番号を返すことが許可されている場合は、アイテムを削除しないでください。

Nが非常に大きく、パフォーマンス要件が非常に厳しい場合を除いて、このアルゴリズムはO(N*k)複雑に実行されますが、これは許容できるはずです。

編集：気にしないでください、トムホーティンの方法ははるかに優れています。最初に乱数を選択してから、リストを1回トラバースします。同じ理論上の複雑さだと思いますが、予想される実行時間ははるかに優れています。

于 2008-09-10T13:45:55.187 に答える
-3

なぜあなたはただのようなことをすることができないのですか

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;

そんなに単純なことではないと思いますので、さらに具体的にご指定いただけますか？

于 2008-09-10T13:49:25.617 に答える