Algorytmy i struktury danych · Senior · Pytanie 11 z 75
Co szacuje HyperLogLog i dlaczego jest popularny?
- 1Medianę strumienia, w jednym przejściu
- ✓Poprawna odpowiedź: Liczbę unikalnych elementów, w kilku kilobajtach
- 3Najczęstsze elementy, z dokładnymi licznikami
Wyjaśnienie
Haszuje elementy i śledzi najdłuższą serię zer na początku hasza w każdym kubełku; seria k zer wskazuje na około 2ᵏ unikalnych wartości. Przy około 12 KB błąd wynosi mniej więcej 1%. Redis PFCOUNT i systemy analityczne używają go do liczenia unikalnych użytkowników.