Nasza strona główna z wideo wyświetla teraz nowy zestaw 24 rekomendacji przy każdym odświeżeniu, dzięki przejściu na ważone próbkowanie rezerwuarowe (A-Res). Zmiana ta wyeliminowała problem „ciągle tego samego układu”, który trapił nasz wcześniejszy kanał sortowany według wyników.

Dlaczego poprzednie podejście psuło doświadczenie użytkownika

Co dwie godziny pobieramy najnowsze popularne filmy z ośmiu regionów i zapisujemy wyniki w tabeli SQLite. Naiwnym rozwiązaniem było posortowanie całego zestawu według wyniku trafności i wybranie 24 najlepszych pozycji. Metoda ta gwarantuje, że pojawią się elementy z najwyższym wynikiem, ale gwarantuje również, że zostaną tam na stałe. Pojedynczy wiralowy klip może dominować na 1. miejscu przez wiele dni, a użytkownicy przy każdym odświeżeniu widzą identyczny układ.

Poza brakiem świeżości, sortowanie całej tabeli przy każdym zapytaniu zmusza SQLite do ładowania do pamięci dużej tymczasowej struktury, co jest marnotrawstwem.

Co daje nam ważone próbkowanie rezerwuarowe

Ważone próbkowanie rezerwuarowe rozwiązuje dwa problemy jednocześnie:

  1. Świeżość z zachowaniem stronniczości – szansa na wybranie każdego filmu jest proporcjonalna do jego wagi (np. wyniku trafności). Film o dwukrotnie większej wadze ma dwukrotnie większą szansę na pojawienie się, ale żadnemu elementowi nie gwarantuje się miejsca.
  2. Efektywność pamięciowa – algorytm przechowuje jedynie „rezerwuar” o stałym rozmiarze $k$ elementów ($k = 24$ dla naszego kanału). Przetwarza strumień w jednym przebiegu, dzięki czemu zużycie pamięci wynosi $O(k)$, niezależnie od liczby napływających kandydatów.

Główna idea jest prosta. Podczas skanowania nadchodzących wierszy przypisujemy każdemu elementowi losowy klucz uwzględniający jego wagę, a następnie zatrzymujemy $k$ elementów z najwyższymi kluczami.

Algorytm w praktyce

Dla każdego filmu:

  1. Losujemy liczbę z rozkładu jednostajnego $u \in (0, 1)$.
  2. Obliczamy klucz $k = u^{1/\text{weight}}$.
    (Im wyższa waga, tym większy oczekiwany klucz.)
  3. Wstawiamy element do kopca o minimalnej wartości (min-heap), który przechowuje $k$ aktualnie najwyższych kluczy.
    Jeśli rozmiar kopca przekroczy $k$, odrzucamy najmniejszy klucz.

Gdy strumień się kończy, kopiec zawiera 24 filmy, które zostaną wyświetlone.

Radzenie sobie z ograniczeniami liczb zmiennoprzecinkowych

Gdy waga filmu jest bardzo duża, $u^{1/\text{weight}}$ zaokrągla się do wartości nieodróżnialnej od 1.0 w arytmetyce podwójnej precyzji, co powoduje, że wiele elementów o dużej wadze dzieli ten sam klucz i traci losowość. Rozwiązaniem jest praca w przestrzeni logarytmicznej:

  • Obliczamy log_key = log(u) / weight zamiast wyrażenia potęgowego.

Ponieważ logarytmy zamieniają potęgowanie na mnożenie, kolejność kluczy zostaje zachowana, unikając jednocześnie problemu utraty precyzji. Obliczenie to nie generuje niemal żadnych dodatkowych kosztów.

Lista kontrolna implementacji

  • Struktura danych: kopiec o minimalnej wartości (kolejka priorytetowa) o rozmiarze $k$ efektywnie przechowuje największe klucze ($O(\log k)$ na wstawienie).
  • Typ numeryczny: należy używać 64-bitowych liczb zmiennoprzecinkowych dla $u$ oraz kluczy opartych na logarytmach; zapewniają one wystarczającą precyzję dla typowych zakresów wag.
  • Statystyczna weryfikacja: przeprowadź szybki test Monte-Carlo na małej próbie. Jeśli elementy o wadze 10 pojawiają się około dziesięć razy częściej niż elementy o wadze 1, implementacja jest poprawna.
  • Strumieniowanie w jednym przebiegu: algorytm nie musi znać całkowitej liczby kandydatów z wyprzedzeniem, co naturalnie pasuje do naszego kursora SQLite, który zwraca wiersze jeden po drugim.

Podsumowanie

Ważone próbkowanie rezerwuarowe pozwala usłudze rekomendacji wideo zachować świeżość strony głównej, uwzględniać wyniki trafności i minimalizować zużycie pamięci – a wszystko to za pomocą jednego przebiegu przez dziesiątki tysięcy kandydatów. Dzięki przeniesieniu obliczania klucza do przestrzeni logarytmicznej i zastosowaniu kopca o minimalnej wartości, metoda pozostaje zarówno precyzyjna, jak i wydajna.