Wählen Sie ein element aus einem Satz ein Prädikat befriedigend gleichmäßig zufällig in $O(1)$ space

Question

Wir erhalten eine Reihe von Objekten, sagen Ganzzahlen $N$.Neben, wir sind ein Prädikat $P$, zum Beispiel $P(i):\Leftrightarrow i \geq 0$.Wir wissen nicht im Voraus, wie viele Elemente von $S$, die das Prädikat erfüllen $P$, aber wir würden gerne Muster oder wählen Sie ein element gleichmäßig zufällig aus $S' = \{ i \mid i \in S \wedge P(i) \}$.

Der naive Ansatz ist zum Scannen von $S$ und zum Beispiel das aufzeichnen aller ganzen zahlen oder Indizes, für die $P$ enthält, dann wählen Sie eine von Ihnen gleichmäßig nach dem Zufallsprinzip.Der Nachteil ist, dass im schlimmsten Fall müssen wir $|S|$ Raum.

Für große Mengen oder sagen in einer streaming-Umgebung der naive Ansatz ist nicht akzeptabel.Gibt es eine in-place-Algorithmus für das problem?

Answer 1

Der folgende Ansatz wird oft als reservoir sampling.Starten Sie das scanning der Satz $S$ und erhalten Sie einen index $j$ für das set.Das erste element, das Sie begegnen, befriedigend, das Prädikat, gesetzt $j$ mit Wahrscheinlichkeit $1/1$.Aktualisieren Sie Ihre Wahl für $j$, wenn Sie auf das zweite element mit der Wahrscheinlichkeit $1/2$.Wenn Sie auf die $k$ - th element befriedigend, das Prädikat, gesetzt $j$ mit Wahrscheinlichkeit $1/k$.

Der Algorithmus arbeitet in $ heta(n)$ Zeit und in constant space.Für die Richtigkeit, es sollte gezeigt werden, dass jedes Element die gleiche Wahrscheinlichkeit, ausgewählt zu sein, und dass die Ereignisse, die Sie abgetastet werden unabhängig sind.Die zweite Behauptung der Unabhängigkeit liegt auf der Hand:unsere Entscheidungen basieren nicht auf, ob wir früher gesampelte Elemente.Die erste Forderung (gleicher Wahrscheinlichkeit) nachgewiesen werden kann ganz leicht mit Induktion.

Für details, siehe J.S.Vitter, Stichproben Mit Reservoir, Algorithmus-R.Für eine kompaktere Darstellung, siehe zum Beispiel diese Folien.