Reservoir-Sampling: eine gleichverteilte Stichprobe aus einem Datenstrom unbekannter Länge

Ziel

k Elemente gleichverteilt und zufällig aus einer Sequenz auswählen, deren Länge erst bei ihrem Ende bekannt ist, und das in einem einzigen Durchlauf mit von der Länge unabhängigem Speicher: etwa Log-Zeilen zur Durchsicht stichprobenartig auswählen, Zeilen aus einem grossen Export auswählen oder Beispiele für einen Bericht bestimmen, ohne alles zu laden.

Voraussetzungen

Ein Pseudozufallsgenerator mit einer Funktion für gleichverteilte Ganzzahlen. Pythons Modul random, laut Dokumentation auf dem Mersenne-Twister basierend, ist für statistisches Sampling ausreichend; dieselbe Dokumentation warnt, dass es nicht für sicherheitskritische Zwecke gedacht ist, deshalb secrets verwenden, wenn ein Angreifer die Stichprobe nicht vorhersagen können darf. Der Datenstrom wird einmal gelesen; k Elemente passen in den Speicher.

Schritte

1. Die ersten k Elemente in einer Liste speichern, dem Reservoir.
2. Für jedes weitere Element, nummeriert mit i (beginnend bei 1), eine ganze Zahl j gleichverteilt zwischen 1 und i ziehen. Ist j höchstens k, den Reservoir-Platz j mit dem Element überschreiben; andernfalls das Element verwerfen.
3. Endet der Datenstrom, ist das Reservoir die Stichprobe. Die Reihenfolge der Plätze trägt keine Bedeutung; bei Bedarf danach mischen, falls die Reihenfolge weiter unten wichtig ist.
4. Sich von der Gleichverteilung überzeugen. Element i tritt mit Wahrscheinlichkeit k/i ein. Ein Reservoir-Element übersteht die Ankunft von Element t mit Wahrscheinlichkeit 1 - 1/t = (t-1)/t. Multipliziert man die Überlebenswahrscheinlichkeit für t von i+1 bis n, teleskopiert das Produkt zu i/n, und (k/i) * (i/n) = k/n, dasselbe für jedes Element, einschliesslich der ersten k, die mit Wahrscheinlichkeit 1 eintreten und mit Wahrscheinlichkeit k/n überleben.
5. Sonderfall k = 1: den einzigen Platz mit Wahrscheinlichkeit 1/i ersetzen.
6. Mit einem kleinen Strom testen, zum Beispiel 10 Elementen und k = 3, indem das Verfahren viele Male wiederholt und geprüft wird, dass sich die Einschlusshäufigkeit jedes Elements 0,3 annähert; auch testen, dass der Code nie nach der Länge fragt.
7. Den Generator in Tests für Reproduzierbarkeit mit einem Seed versehen und den Seed in der Produktion protokollieren, damit sich eine berichtete Stichprobe erneut erzeugen lässt.

Erwartetes Ergebnis

Jedes Element ist mit exakter Wahrscheinlichkeit k/n in der Stichprobe, ein Zufallszug pro Element, Speicher proportional zu k, und die Länge des Datenstroms wird nie benötigt.

Grenzen und Prüfbasis

Die Stichprobe ist gleichverteilt über Elemente, nicht über Zeit oder Bytes; ein stossweiser Datenstrom wird nach Anzahl gesampelt. Bei mehreren parallelen Datenströmen müssen ihre Reservoirs mit Gewichten proportional zu ihrer Elementanzahl zusammengeführt werden. Gewichtete Varianten und Varianten, die zum Sparen von Zufallszügen vorausspringen, existieren, werden hier aber nicht behandelt. Die Korrektheit ergibt sich aus der Rechnung in Schritt 4; es werden keine Messungen behauptet.