Algorithmen und Datenstrukturen · Senior · Frage 17 von 75
Wie zieht man aus einem Stream unbekannter Länge eine gleichverteilte Stichprobe von k Elementen?
- 1Jedes k-te Element behalten, während der Stream vorbeiläuft
- 2Reservoir Sampling: Element i mit Wahrscheinlichkeit k/i behalten
- 3Den ganzen Stream speichern, dann mischen und k nehmen
Antwort zeigen
Richtige Antwort: Reservoir Sampling: Element i mit Wahrscheinlichkeit k/i behalten
Erklärung
Nach beliebig vielen Elementen ist jedes mit gleicher Wahrscheinlichkeit k/n im Reservoir, mit O(k) Speicher und einem Durchlauf. Jedes k-te Element zu nehmen ist nicht gleichverteilt und hängt von der Länge des Streams ab.