Zasampling zbiornikowy: Losowe próby z strumienia

Losowanie podczas nieznanej ilości elementów

Wybieranie k losowych elementów z równym prawdopodobieństwem z tablicy o znanej długości n jest proste - przetasuj indeksy, weź pierwsze k. Trudniejszym problemem jest strumień: elementy przychodzą jeden po drugim, nie możesz wrócić do poprzednich i często nie wiesz, ile ich będzie w sumie. Chcesz jednak, aby na każdym etapie, gdyby strumień się zakończył, miało miejsce zdefiniowane k elementy, gdzie każdy widoczny dotychczas miał identyczne prawdopodobieństwo bycia wybranym do próby. To właśnie gwarantuje losowanie z rezerwową zbiornikową, używając tylko O(k) pamięci niezależnie od długości strumienia.

Algorytm R

Algorytm R Jeffrey'ego Vittera (1985) jest niezwykle proste. Wypełnia on zbiornik o rozmiarze k pierwszymi k elementami bezpośrednio. Dla każdego kolejnego elementu, na pozycji i, generuje liczbę całkowitą losową j z zakresu 1 do i. Jeśli j jest mniejsze lub równe k, nadpisuje on slot j w zbiorniku nowym elementem; w przeciwnym razie odrzucany jest nowy element i kontynuuje się proces. Każdy późniejszy element jest rozważany dokładnie raz, mając szansę k/i na wejście do zbiornika, a jeśli to nastąpi, zastępuje on losowy istniejący slot.

const reservoir = [];
let i = 0;
for (const item of stream) {
  i++;
  if (reservoir.length < k) {
    reservoir.push(item);                 // fill the first k slots outright
  } else {
    const j = randomInt(1, i);            // uniform in [1, i]
    if (j <= k) reservoir[j - 1] = item;  // replace with probability k/i
  }
}

Dlaczego każdy element ma taką samą szansę

Dowód jest czystą indukcją. Po przetworzeniu pierwszych k elementów, każdy z nich znajduje się w reservorze z prawdopodobieństwem dokładnie 1, co jest jasno równomiernym. Załóżmy, że po przetworzeniu i-1 elementów, każdy z nich ma prawdopodobieństwo k/(i-1) do obecnej zajęcia miejsca w reservorze. Element i jest przyjmowany z prawdopodobieństwem k/i przez konstrukcję. Aby wcześniejszy element przetrwał ten krok, albo element i jest odrzucony, co się zdarza z prawdopodobieństwem 1-k/i, albo element i jest przyjmowany, ale nie wyprowadza tego konkretnej pozycji, co się zdarza z prawdopodobieństwem (k/i) razy ((k-1)/k). Mnożenie przez wszystko i uproszczenie odzyskuje dokładnie k/i dla każdego z i elementów - więc nieprzerwanie zachowuje się towar w każdym kroku, a nie tylko na końcu.

Wersje z wagi i szybsze

Algorytm R generuje jedną losową liczbę dla każdego elementu, co jest nieefektywne, gdy większość elementów jest odrzucona na bardzo długim strumieniu. Algorytmy L oraz pokrewnych metod skoków przyspieszonych obliczają w zamkniętej formie, ile elementów zostanie pominięto przed kolejnym przyjęciem, skokując bezpośrednio do następnego istotnego indeksu zamiast rzucania kostką dla każdego elementu. Gdy elementy mają nierównych wag, gwarancja bezwagi już nie obowiązuje; wagi w zasamplingu zbiornicowym (Efraimidis i Spirakis, A-ExpJ) przypisują każdemu elementowi klucz wyznaczony przez podnoszenie losowej liczby do potęgi jedna nad wagę tego elementu, a następnie przechowują k elementów o największych kluczach. Te metody pozwalają na próbkowanie proporcjonalnie do wag, jednocześnie pozostając w jednym przepływowym przebiegu.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Reservoir Sampling — Fair Samples from a Stream i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.