Jest to prawdopodobnie pytanie do wywiadu. Próbnik rezerwuaru jest używany przez naukowca danych do przechowywania odpowiednich danych w ograniczonym magazynie z dużego strumienia danych.
Jeśli zbieranie elementów k z tablicy z N elementów, tak, że prawdopodobieństwo każdego elementu pobierane powinny być takie same (K/N), należy wykonać dwa etapy,
1) przechowuje pierwsze elementy k w magazynie. 2) Kiedy następny element (k + 1) pochodzi ze strumienia, oczywiście nie masz już miejsca w kolekcji. Generuj losową liczbę od o do n, jeśli wygenerowana losowa liczba jest mniejsza niż k przypisz l, zastąp pamięć [ l] z elementem (k + 1) ze strumienia.
Teraz powracając do pytania, tutaj rozmiar pamięci to 1. Tak, wybierz pierwszy węzeł, powtórz na liście drugi element. Teraz wygeneruj losową liczbę, jeśli jej 1, zostaw próbkę samodzielnie, w przeciwnym razie zmień element pamięci z listy
@Giacomon Czy istnieje powód czujesz to nie będzie działać dla małych zbiorów. Zrozumiałem, że należy zapewnić jednolity algorytm pobierania próbek w Internecie, co pasuje idealnie, myślę, że –
@Aurojit: Myślę, że Giacomo mówi, że to rozwiązanie jest dobre zarówno dla dużych, jak i małych kolekcji. –
@Chris: nie, nie, nie myliłem się – gd1