Effiziente Auswahl einer Reihe zufälliger Elemente aus einer verknüpften Liste

StackOverflow https://stackoverflow.com/questions/54059

Frage

Angenommen, ich habe eine verknüpfte Liste mit Längennummern N. N ist sehr groß und ich kenne den genauen Wert nicht im Voraus N.

Wie kann ich am effizientesten eine Funktion schreiben, die zurückkommt? k vollständig zufällige Zahlen von der Liste?

War es hilfreich?

Lösung

Es ist ein sehr schöner und effizienter Algorithmus für das so genannte Verfahren unter Verwendung von Reservoir Sampling .

Lassen Sie mich beginnen, indem Sie seine Geschichte :

Knuth nennt diesen Algorithmus R auf p. 144 seine Ausgabe 1997 von Seminumerical Algorithmen (Band 2 von The Art of Computer Programming) und stellt es für sie einen Code. Knuth führt den Algorithmus zu Alan G. Waterman. Trotz langer Suche habe ich nicht fündig geworden zu Originaldokument des Waterman, wenn es vorhanden ist, was sein kann, warum Sie am häufigsten sehen Knuth als Quelle dieses Algorithmus angegeben.

McLeod und Bellhouse, 1983 (1) eine gründlichere Diskussion als Knuth sowie den ersten veröffentlichten Beweis (das ich kenne), dass der Algorithmus funktioniert.

Vitter 1985 (2) Bewertungen Algorithmus R und stellt dann weitere drei Algorithmen, die die gleiche Leistung bieten, aber mit einem Twist. Anstatt eine Wahl zu schließen oder jedes eingehende Element zu überspringen, vorgebe seinen Algorithmus die Anzahl der eingehenden Elemente übersprungen. In seinen Tests (die zugegebenermaßen jetzt veraltet sind) verringerte sich diese Ausführungszeit dramatisch durch Erzeugung von Zufallszahlen und Vergleiche zu vermeiden auf jeder in-coming-Nummer.

Pseudo-Code der Algorithmus ist: 

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()

Beachten Sie, dass ich speziell den Code, um die Größe der Eingabe zu vermeiden geschrieben haben, angeben. Das ist einer der coolen Eigenschaften dieses Algorithmus: Sie können es, ohne dass ausführen können die Größe der Eingabe zu vorher wissen, und es noch versichert Ihnen, dass jedes Element, das Sie stoßen eine gleiche Wahrscheinlichkeit enden in R (das heißt, es gibt keine Vorspannung). Weiterhin enthält R eine faire und repräsentative Probe der Elemente der Algorithmus zu jedem Zeitpunkt in Betracht gezogen hat. Dies bedeutet, dass Sie Online-Algorithmus dies als verwenden können.

Warum funktioniert das?

McLeod und Bellhouse (1983) liefern einen Beweis der Mathematik von Kombinationen verwenden. Es ist schön, aber es wäre ein bisschen schwierig sein, sie hier zu rekonstruieren. Deshalb habe ich einen alternativen Beweis erzeugt, die leichter zu erklären ist.

Wir gehen über Induktionsbeweis.

Sagen wir eine Reihe von s Elemente erzeugen wollen und dass wir bereits n>s Elemente gesehen haben.

Nehmen wir an, dass unsere aktuellen s Elemente haben bereits jeweils mit einer Wahrscheinlichkeit von s/n gewählt.

Durch die Definition des Algorithmus, wir Element n+1 mit Wahrscheinlichkeit s/(n+1) wählen.

Jedes Element bereits Teil unserer Ergebnismenge hat eine Wahrscheinlichkeit 1/s von ersetzt werden.

Die Wahrscheinlichkeit, dass ein Element aus der n gesehene Ergebnismenge in der n+1 gesehene Ergebnismenge ersetzt wird, ist daher (1/s)*s/(n+1)=1/(n+1). Im Gegensatz dazu, dass die Wahrscheinlichkeit, ein Element nicht ersetzt wird, ist 1-1/(n+1)=n/(n+1).

Somit wird die n+1 gesehene Ergebnismenge enthält ein Element, entweder, wenn es Teil der n gesehene Ergebnismenge ist und wurde nicht ersetzt --- Diese Wahrscheinlichkeit ist (s/n)*n/(n+1)=s/(n+1) --- oder, wenn das Element ausgewählt wurde --- mit Wahrscheinlichkeit s/(n+1).

Die Definition des Algorithmus sagt uns, dass die ersten s Elemente werden als die ersten n=s Mitglieder der Ergebnismenge automatisch enthalten. Daher umfasst die n-seen Ergebnismenge jedes Element mit s/n (= 1) Wahrscheinlichkeits uns den notwendigen Basisfall für die Induktion ergibt.

Referenzen

  1. McLeod, A. Ian und David R. Bellhouse. „Ein bequemer Algorithmus für eine einfache Stichprobe zu ziehen.“ Journal der Royal Statistical Society. Serie C (AppliedStatistik) 32,2 (1983): 182-184. ( Link-)

  2. Vitter, Jeffrey S. "Stichproben mit einem Reservoir." ACM Transactions on Mathematical Software (TOMS) 11.1 (1985): 37-57. ( Link )

Andere Tipps

Dies ein Reservoir Sampling Problem genannt. Die einfache Lösung ist eine Zufallszahl zu jedem Element der Liste zuweisen, wie Sie es sehen, dann die oben halten (oder unten) k Elemente, wie durch die Zufallszahl bestellt werden.

Ich würde vorschlagen: Erstens Ihre k Zufallszahlen finden. Sortiere sie. Dann durchquert sowohl die verknüpften Liste und Ihre Zufallszahl einmal.

Wenn Sie irgendwie nicht wissen, die Länge der verknüpften Liste (wie?), Dann könnte man die ersten k in ein Array packen, dann für den Knoten r, eine Zufallszahl in [0, r) erzeugen, und wenn das ist weniger als k, r-ten Element des Arrays ersetzen. (Nicht ganz davon überzeugt, dass nicht Bias ...)

Anders als das: „Wenn ich Sie wäre, würde ich nicht von hier beginnen werden.“ Sind Sie sicher, verkettete Liste für Ihr Problem ist richtig? Gibt es nicht eine bessere Datenstruktur, wie eine gute alte flachen Array-Liste.

Wenn Sie nicht über die Länge der Liste kennen, dann werden Sie durchqueren müssen, um es komplett zufällige Picks zu gewährleisten. Die Methode, die ich in diesem Fall verwendet habe, ist die von Tom Hawtin ( 54070 ). Während die Liste durchlaufen halten Sie k Elemente, die bis zu diesem Punkt Ihre zufällige Auswahl bilden. (Zunächst fügen Sie einfach die ersten k Elemente auftreten.) Dann mit einer Wahrscheinlichkeit von k/i Sie ein zufälliges Element aus der Auswahl mit dem ith Element der Liste ersetzen (dh das Element, das Sie sich gerade befinden, in diesem Moment).

Es ist leicht zu zeigen, dass dies eine zufällige Auswahl gibt. m Elemente (m > k) Nach der Besichtigung haben wir, dass jeder der ersten m Elemente der Liste ist ein Teil von Ihnen zufälliger Auswahl mit einer Wahrscheinlichkeit k/m. Dass dies zunächst hält, ist trivial. Dann gilt für jedes Element m+1, setzen Sie es in Ihrer Auswahl mit der Wahrscheinlichkeit k/(m+1) (ein zufälliges Element ersetzt). Sie müssen nun zeigen, dass alle anderen Elemente werden ausgewählt Wahrscheinlichkeit k/(m+1) der auch haben. Wir haben, dass die Wahrscheinlichkeit k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (das heißt Wahrscheinlichkeit, dass das Element in der Liste Zeiten war die Wahrscheinlichkeit dafür, dass es noch da ist). Mit Kalkül können Sie zeigen, ohne weiteres, dass dies zu k/(m+1) gleich ist.

Nun, Sie müssen wissen, was N zur Laufzeit ist zumindest, auch wenn es sich um einen zusätzlichen Pass über die Liste zu tun, sie zu zählen. Der einfachste Algorithmus, dies zu tun ist, um nur eine Zufallszahl in N auswählen und das Element entfernen, K-mal wiederholt. Oder, wenn es erlaubt ist, wiederholen Zahlen zurückzukehren, entfernen Sie nicht das Element.

Wenn Sie eine sehr große N haben, und sehr strenge Leistungsanforderungen dieser Algorithmus läuft mit O(N*k) Komplexität, die akzeptabel sein sollte.

Edit: Nevermind, Tom Hawtin Methode ist viel besser. Wählen Sie die Zufallszahl zuerst, dann überqueren, wenn die Liste. Gleiche theoretische Komplexität, denke ich, aber viel besser erwartete Laufzeit.

Warum können Sie nicht tun, nur so etwas wie 

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;

Ich bin sicher, dass Sie nicht etwas bedeuten, die so einfach können Sie zusätzlich angeben?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top