Algorytmy i struktury danych · Senior · Pytanie 17 z 75
Jak wybrać równomiernie losową próbkę k elementów ze strumienia o nieznanej długości?
- 1Brać co k-ty element w miarę napływu danych
- ✓Poprawna odpowiedź: Reservoir sampling: zachować element i z szansą k/i
- 3Zapisać cały strumień, przetasować i wziąć k
Wyjaśnienie
Po dowolnej liczbie elementów każdy jest w „rezerwuarze” z jednakowym prawdopodobieństwem k/n, przy O(k) pamięci i jednym przejściu. Co k-ty element to nie jest próba równomierna i zależy od długości strumienia.