PL 
EnglishDomyślny
Українська🪣 Próbkowanie rezerwuarowe — sprawiedliwe próby ze strumienia
Wybierz k jednostajnych próbek ze strumienia o nieznanej długości w jednym przebiegu: element i zastępuje miejsce w rezerwuarze z prawdopodobieństwem k/i. Histogram potwierdza, że każdy element ma równe szanse.
O tej symulacji
Ta symulacja uruchamia Algorytm R, klasyczną jednoprzebiegową metodę próbkowania rezerwuarowego do wybrania k jednostajnie losowych elementów ze strumienia o długości N bez znajomości N z góry. Element i (indeksowany od 1) trafia bezpośrednio do rezerwuaru, jeśli i ≤ k; w przeciwnym razie losowana jest liczba całkowita j z przedziału 1..i, a element zastępuje miejsce j w rezerwuarze tylko wtedy, gdy j ≤ k. Histogram na dole gromadzi wyniki z tysięcy niezależnych przebiegów, by empirycznie potwierdzić, że każdy element trafia do końcowego rezerwuaru z dokładnie takim samym prawdopodobieństwem k/N.
🔬 Co pokazuje
Pojedyncze strumieniowe przejście przez N elementów (5–60), wypełniające rezerwuar o k miejscach (1–12), z podświetlonym aktualnie przetwarzanym elementem i komunikatem na żywo pokazującym, czy zapełnił puste miejsce, zastąpił istniejące, czy został odrzucony. Poniżej rosnący histogram wykreśla empiryczną częstość włączenia każdego elementu w wielu zakończonych przebiegach na tle teoretycznej linii docelowej k/N, wraz z maksymalnym zaobserwowanym odchyleniem od tego celu.
🎮 Jak korzystać
Ustaw Długość strumienia N i Rozmiar rezerwuaru k suwakami, a następnie naciśnij Odtwórz, aby animować Algorytm R element po elemencie, lub Krok, aby przejść jeden element naraz. Użyj Uruchom 5000×, aby cicho wykonać 5000 pełnych przebiegów i obserwować, jak słupki histogramu spłaszczają się w kierunku przerywanej linii docelowej k/N, empirycznie potwierdzając gwarancję jednostajnego włączenia, a nie tylko według wzoru. Reset czyści wszystkie zgromadzone statystyki i rozpoczyna nowy przebieg.
💡 Czy wiesz, że?
Algorytm R spopularyzował Donald Knuth w dziele The Art of Computer Programming i wciąż jest standardową techniką jednostajnego próbkowania ze strumieni danych zbyt dużych, by zmieściły się w pamięci — na przykład próbkowania linii logów z działającego serwera bez przechowywania całego logu. Jego poprawność wynika z pięknie prostego argumentu probabilistycznego: pomnożenie szansy, że element zostanie wybrany w swojej kolejce (k/i), przez szansę, że przetrwa każdą kolejną próbę wyparcia, teleskopowo redukuje się do dokładnie k/N.
Najczęściej zadawane pytania
Jak Algorytm R decyduje, czy zachować, czy odrzucić każdy element?
Dla pierwszych k elementów (i ≤ k) element trafia od razu do miejsca i−1 w rezerwuarze z pewnością. Dla każdego kolejnego elementu i algorytm losuje jednostajnie liczbę całkowitą j z przedziału od 1 do i włącznie; jeśli j ≤ k, element zastępuje to, co było w miejscu j−1, w przeciwnym razie zostaje odrzucony. Oznacza to, że element i jest zachowywany z prawdopodobieństwem dokładnie k/i, a jeśli zostanie zachowany, wypiera jednostajnie losowe istniejące miejsce.
Dlaczego ta prosta reguła daje każdemu elementowi to samo ogólne prawdopodobieństwo k/N?
Element i przetrwa do końcowego rezerwuaru tylko wtedy, gdy zostanie wybrany w swojej kolejce (prawdopodobieństwo k/i), a następnie nigdy nie zostanie wyparty w żadnej kolejnej kolejce m > i, gdzie szansa na niewyparcie za każdym razem wynosi 1 − 1/m. Pomnożenie k/i przez iloczyn (1 − 1/m) dla m od i+1 do N teleskopuje się do dokładnie (k/i)·(i/N) = k/N — identycznie dla każdego elementu, niezależnie od tego, kiedy przepłynął przez strumień, co dokładnie pokazuje histogram tej symulacji.
Co dokładnie robi przycisk „Uruchom 5000×” inaczej niż Odtwórz?
Odtwórz i Krok animują pojedyncze przejście przez strumień z wizualnym podświetleniem bieżącego elementu i miejsca w rezerwuarze, co ułatwia śledzenie mechaniki Algorytmu R. Uruchom 5000× zamiast tego wywołuje cichą, nieanimowaną wersję tego samego algorytmu 5000 razy w ciasnej pętli, zliczając, który element trafił do rezerwuaru po każdym pełnym przebiegu, dzięki czemu histogram gromadzi wystarczająco próbek, by empiryczna częstość włączenia wyraźnie zbiegała do teoretycznej linii k/N.
Co właściwie przedstawiają „Maks. odchylenie” i słupki histogramu?
Każdy słupek histogramu pokazuje, dla jednego konkretnego indeksu elementu, ułamek zakończonych przebiegów, w których ten element znalazł się gdzieś w końcowym rezerwuarze — dosłownie counts[i] podzielone przez łączną liczbę przebiegów. Maks. odchylenie to największa bezwzględna różnica między obserwowaną częstością włączenia dowolnego elementu a teoretycznym celem k/N; wraz ze wzrostem liczby przebiegów to maksymalne odchylenie powinno maleć do zera, co wizualnie potwierdza gwarancję jednostajności algorytmu.
Dlaczego próbkowanie rezerwuarowe jest przydatne, gdy nie można przechować całego strumienia?
Cała idea Algorytmu R polega na tym, że wymaga on przechowywania w pamięci tylko k elementów (samego rezerwuaru) plus licznika elementów, niezależnie od tego, jak długi okaże się strumień N — nie musi znać N z góry i nigdy nie przechowuje wcześniej widzianych, odrzuconych elementów. To czyni go standardowym wyborem do jednostajnego próbkowania ze źródeł danych, takich jak logi serwera, ruch sieciowy czy dowolny zbiór danych zbyt duży lub zbyt ciągły, by załadować go do pamięci na raz.