Liczenie liniowe: jak oszacować liczbę unikalnych wartości

Jak moglibyśmy policzyć liczbę unikalnych wartości w zbiorze danych, gdyby było ich naprawdę dużo? Na przykład, moglibyśmy mieć usługę, która mierzy liczbę unikalnych użytkowników na jakiejś dużej stronie internetowej lub może w całej domenie .cz/.com/.whatever czy coś takiego.

Naiwne podejście

Ok, nie ma nic do rozwiązania, po prostu przechodzimy przez dane i zawsze przechowujemy każdą wartość tylko raz w odpowiedniej strukturze danych. W Pythonie moglibyśmy napisać to tak (kod jest niepotrzebnie rozwlekły, to celowo):

nonunique_values = [1, 2, 3, 2, 4, 1, 1, 3, 5, 2] def count_unique(values): found = set() for item in values: if item not in found: found.add(item) return len(found) print count_unique(nonunique_values) # 5

To działa. No dobrze, ale co jeśli dane to 36-znakowe unikalne identyfikatory v4, a unikalnych identyfikatorów jest dziesięć milionów? Cóż... program nadal oblicza poprawną wartość, ale ile pamięci zajmuje? Możemy spróbować policzyć. Dla uproszczenia przyjmiemy, że tak naprawdę przechowujemy uuid jako 36-znakowy ciąg znaków. Tak więc jeden uuid zajmuje 36 bajtów, a dziesięć milionów identyfikatorów zajmuje 360 MB.

Nie do końca małe, spójrzmy prawdzie w oczy. Gdyby istniało sto milionów unikalnych identyfikatorów, bylibyśmy w zakresie gigabajtów. I wciąż liczymy wyłącznie to, co zajmują dane. Dodajmy do tego pewien narzut, który zajmuje, powiedzmy, Python/JavaScript, a możemy dostać się do rzędu gigabajtów z dziesięcioma milionami identyfikatorów:

Nie chcemy tego. Jak z tego wybrnąć?

Moglibyśmy spróbować w jakiś sposób przechowywać same identyfikatory bardziej efektywnie, moglibyśmy użyć C zamiast Pythona, co znacznie zmniejszyłoby zapotrzebowanie na pamięć, ale to wciąż nie byłoby to samo, a taki program nadal zajmowałby niesamowitą ilość miejsca. Pozostaje pytanie: czy naprawdę musimy wiedzieć co do joty, czy tych unikalnych wartości jest dokładnie 9 563 618? Czy coś by się stało, gdybyśmy pracowali z liczbą 9 547 666? Jeśli twoja odpowiedź brzmi, że tak i że chcesz, aby było to dokładnie, to proszę, rób, co chcesz. W przeciwnym razie zademonstrujmy procedury szacowania liczby unikalnych wartości w zbiorze danych tak dokładnie, szybko i przy minimalnym zapotrzebowaniu na pamięć, jak to tylko możliwe.

Funkcja haszująca - nasz ratunek

Rozważymy funkcję skrótu, która przyjmuje ciąg znaków jako dane wejściowe i zwraca pewną liczbę n-bitową jako dane wyjściowe. Jeśli jesteś bardziej przyzwyczajony do funkcji hashujących, które "zwracają ciąg znaków", to po prostu pomyśl o tym jako o dalszej konwersji ciągu znaków z powrotem na liczbę, nie ma w tym nic złego. Liczba bitów wskazuje, jak duża jest liczba. Funkcja 8-bitowa zwraca liczbę, która zajmuje osiem bitów, a osiem bitów może przechowywać²⁸ różnych wartości, zazwyczaj liczb całkowitych od 0 do 255. Będziemy kontynuować pracę z 24-bitową funkcją skrótu. Taka funkcja zwraca²²⁴ różne wartości, czyli 16 777 216.

Zamiast przechowywać same wartości, będziemy przechowywać ich 24-bitowe skróty. Do przechowywania dziesięciu milionów 24-bitowych skrótów potrzebujemy 30 MB. Jest to o rząd wielkości lepsze rozwiązanie niż poprzednie 360 MB. Kod może wyglądać następująco:

def nhash(item, n): return hash(item) % (2 ** n) nonunique_values = [1, 2, 3, 2, 4, 1, 1, 3, 5, 2] def count_unique_using_nhash(values): found = set() for item in values: checksum = nhash(item, 24) if checksum not in found: found.add(checksum) return len(found) print count_unique_using_nhash(nonunique_values) # 5

Funkcja hash jest natywną funkcją Pythona i zwraca liczbę całkowitą, funkcja nhash pokazuje naiwną implementację n-bitowej funkcji hash; nie jest ważne, aby zrozumieć, jak to działa, ponieważ i tak nie działa poprawnie - wynik funkcji nie zajmuje 24 bitów, ale to nie ma teraz znaczenia, chodzi mi o zasadę.

Następnie pojawia się funkcja count_unique_using_nhash, która zlicza unikalne wartości. Przechodzi ona przez wszystkie wartości, oblicza ich hash i przechowuje ten hash w znalezionej zmiennej, jeśli wartość jeszcze tam nie jest.

Problem z tą procedurą polega na tym, że funkcja hash może zwrócić tę samą sumę kontrolną dla różnych ciągów - może wystąpić kolizja. Im więcej takich kolizji, tym bardziej niedokładny wynik. Funkcja count_unique_using_nhash prawie zawsze zwraca mniej unikalnych wartości niż jest ich w rzeczywistości.

A którą funkcję haszującą wybrać? Tak naprawdę nie ma to większego znaczenia, ale ogólnie zalecany jest jakiś wariant MurmurHash.

Bitmapy

Czy uważałeś na Podstawach programowania w języku C? Jeśli tak, to znasz bitmapy. Jak można je wykorzystać?

Naszkicujmy ten pomysł w terenie. Ponieważ nie musimy przechowywać obliczonych sum kontrolnych, możemy utworzyć tablicę o długości²²⁴ i zainicjować wszystkie elementy na zero. Następnie w momencie, gdy trafimy na sumę kontrolną - która jest liczbą! - zapisujemy jedynkę w polu indeksu sumy kontrol nej, aby wskazać, że już znaleźliśmy tę sumę kontrolną. Liczba unikalnych elementów będzie wtedy w przybliżeniu równa liczbie jedynek w tym polu. Kod może wyglądać następująco:

def count_unique_using_array(values): # lista 2^24 zainicjalizowana na same zera array = [0] * (2 ** 24) for item in values: array[nhash(item, 24)] = 1 return sum(array) print count_unique_using_array(nonunique_values)

Jednak użycie tablic w tym przypadku jest bardzo pamięciochłonne, ponieważ zawsze musimy przechowywać jedynkę lub zero w każdej komórce. Zamiast tego możemy użyć tablicy bitów. Aby to zrozumieć, liczba całkowita może być przechowywana na przykład w 32 bitach. Jeśli przekonwertujemy liczbę 354 na binarną, otrzymamy 101100010. Tak więc liczba 354 byłaby przechowywana w komputerze jako 32-bitowa liczba całkowita (zignorujmy szczegóły, dobrze?) w następujący sposób:

00000000 00000000 00000001 01100010

To taki ładny format, którego moglibyśmy użyć, prawda? Ponieważ chcemy przechowywać tylko jedynki i zera w naszej funkcji, a teraz właśnie dowiedzieliśmy się, że zwykła liczba jest w rzeczywistości niczym innym jak zbiorem zer i jedynek (jak wszystko w komputerze, jak sądzę...). Krótko mówiąc, możemy użyć operatorów bitowych do zapisania jedynki tak, aby faktycznie zajmowała jeden bit.

Wróćmy do naszej funkcji tablicowej. Jeśli przepiszemy ją na tablice bitowe, to dla 24-bitowej funkcji haszującej będziemy potrzebować tylko tablicy bitowej o długości²²⁴ bitów, czyli 2 MB. To przyzwoity wzrost!

Używając 32-bitowej funkcji haszującej, która ma²³² różne wartości wyjściowe, czyli 4 294 967 296, potrzebowalibyśmy tablicy bitów o wielkości pół gigabajta. Nie jest to całkowicie złe, biorąc pod uwagę fakt, że w ten sposób jesteśmy w stanie zliczać unikaty do miliardów.

Liczenie liniowe

Wspomniałem wcześniej, że kiedy używamy funkcji haszującej, otrzymujemy jedynie szacunkową liczbę unikalnych wartości. Oszacowanie to staje się tym bardziej niedokładne, im liczba unikalnych wartości jest bliższa liczbie różnych wartości wyjściowych funkcji hashującej. Ma to sens, że jeśli mamy zbiór danych, który ma pięć miliardów unikalnych wartości, to po prostu nie możemy tego policzyć za pomocą 24-bitowej funkcji skrótu.

Jednak szacunki, które obliczamy za pomocą funkcji skrótu, można dalej udoskonalać. Wykorzystuje się do tego prosty pomysł - im więcej unikalnych wartości znajduje się w zbiorze danych, tym bardziej prawdopodobne jest, że z czasem pojawią się kolizje. (Kolizja = dwa różne wejścia mają ten sam wynik funkcji skrótu, tę samą sumę kontrolną). Teraz zajmiemy się trochę matematyką, więc wprowadzimy kilka zmiennych:

• Będziemy pracować z n-bitową funkcją skrótu h.
• Zatem liczba wszystkich możliwych wyjść funkcji h jest równa ²ⁿ. Oznaczymy tę liczbę przez m, a więc: ^m=2n.
• Tablica bitów, w której będziemy przechowywać znalezione sumy kontrolne, będzie oznaczona dużą literą A. Tablica A ma długość m.
• Jeśli przeprowadzimy nasz algorytm przez cały zestaw danych, niektóre wartości w polu bitowym będą równe zero, a niektóre będą równe jeden. Będziemy głównie zainteresowani stosunkiem "liczba zer podzielona przez długość tablicy", który daje nam względną proporcję zer w tablicy bitów. Początkowo proporcja ta wynosi 1, ponieważ tablica jest inicjowana na wszystkie zera. Gdyby było to pięćdziesiąt pięćdziesiąt, proporcja byłaby równa połowie itd. Oznaczamy tę wartość przez Z i obliczamy ją jako Z = liczba zer / m.

W tym momencie, im wyższa wartość Z, tym bardziej jesteśmy pewni, że nasze oszacowanie liczby unikatów jest dokładne. Na przykład, jeśli przejdziemy przez pusty zbiór danych, w tablicy bitów pozostaną same zera, a wartość Z wyniesie jeden - mamy więc absolutną pewność, że w naszym zbiorze danych jest tyle samo unikalnych elementów, co jedynek w tablicy bitów - zero.

Jeśli wartość Z jest równa 0,99, oznacza to, że tablica bitów jest w jednej setnej pełna jedynek. 99% tablicy zawiera zera. Jest to nadal dobry wynik, prawdopodobnie nie wystąpiło zbyt wiele kolizji podczas obliczeń i nie będzie potrzebna żadna lub minimalna korekta. Jeśli jednak wartość Z wynosi 0,05, tylko 5% tablicy zawiera zera i prawdopodobnie podczas obliczeń doszło do wielu kolizji - potrzebna będzie duża poprawka.

Ale jak obliczyć tę poprawkę? Skorzystamy z logarytmu, który jest funkcją o takiej właśnie postaci:

Interesować nas będzie czerwona część na przedziale (0, 1>. Jeśli naniesiemy Z na oś x, otrzymamy, że im wyższe Z, tym wartość y będzie bliższa zeru. I odwrotnie, im mniejsze Z, tym mniejsza będzie wartość y. Obliczamy wynikowy szacunek, mnożąc tę liczbę przez -m. Zauważ, że dla wystarczająco niskiej wartości Z otrzymujemy liczbę, która jest nawet mniejsza niż -1, a jeśli pomnożymy tę wartość przez -m, otrzymamy oszacowanie, które jest większe niż m: oszacowaliśmy, że liczba unikatów jest większa niż liczba wszystkich możliwych sum kontrolnych, które mogą pochodzić z funkcji haszującej.

Pełny wzór na obliczenie liczby p unikalnych wartości wyglądałby następująco:

$$\Large p=-m\cdot \ln Z$$

Implementacja (bez pól bitowych, tylko zwykłe pola) może wyglądać następująco:

from uuid import uuid4 from math import log number_of_unique_values = 10000 nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)] nonunique_values += nonunique_values def nhash(item, n):
    return hash(item) % (2 ** n) def count_unique_using_array(values, n): array = [0] * (2 ** n) for item in values: array[nhash(item, n)] = 1 return sum(array) def linear_counting(values, n):
    estimate = count_unique_using_array(values, n) m = 2 ** n number_of_zeros = m - estimate Z = float(number_of_zeros) / m # log tutaj jest logarytmem naturalnym podstawy e p = (-m) * log(Z) p = int(round(p)) print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \ (estimate, m, number_of_zeros, Z, p) return p print "Cardinality: %s" % linear_counting(nonunique_values, 16)

W funkcji linear_counting najpierw obliczamy pierwsze oszacowanie przy użyciu poprzedniego algorytmu, który wykorzystuje n-bitową funkcję skrótu. Następnie obliczamy odsetek zer w tablicy i wykonujemy korektę za pomocą wzoru. Logarytm w kodzie jest logarytmem naturalnym. Zmienna nonunique_values zawiera number_of_unique_values unikalnych ciągów, więc w tym przykładzie na liście nonunique_values znajduje się dziesięć tysięcy unikalnych wartości. Dziwny kod w linii 6 zapewnia, że w tablicy znajduje się wiele identycznych wartości: po prostu dołączamy tę samą listę rang do końca listy, więc każda wartość znajduje się w tablicy dwa razy. A potem liczymy. W idealnym przypadku funkcja powinna zwrócić, że lista zawiera dziesięć tysięcy unikatów. Wyjście:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, Z=0.858261108398, p=10016 Cardinality: 10016

Ponieważ zawsze generowana jest inna lista nonunique_values, wyniki będą się różnić przy każdym wywołaniu. Użyliśmy 16-bitowej funkcji skrótu. Widzimy, że pierwsze przypuszczenie z funkcji count_unique_using_array było takie, że lista zawierała 9289 unikatów. Udoskonaliliśmy to oszacowanie do 10 016, korygując je, co jest już całkiem dobre: nasze oszacowanie jest tylko o 0,16% większe, podczas gdy wcześniej było o 7,11% mniejsze - to całkiem sporo.

Gdybyśmy wzięli "większą" funkcję haszującą, na przykład 24-bitową, uzyskalibyśmy dokładniejszy wynik:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, Z=0.999404132366, p=10000 Cardinality: 10000

Samo pierwotne oszacowanie było w porządku, udoskonalenie osiągnęło już nawet dziesięć tysięcy. Dla przykładu możemy wypróbować milion unikalnych identyfikatorów, tj. number_of_unique_values = 1000000. Przy użyciu 24-bitowej funkcji skrótu otrzymujemy następujące wyniki:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, Z=0.94212192297, p=1000267 Kardynalność: 1000267

Idzie. Jednocześnie, jeśli zaimplementujemy to jako tablicę bitów, tablica powinna zjeść tylko wspomniane dwa megabajty (+ to, co zjada język). Całkiem nieźle jak dla mnie. Ale możemy zrobić to lepiej! Dużo lepiej. Ale o tym następnym razem.

W międzyczasie możesz przeczytać artykuł A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Możesz też przejść do następnej części serii: algorytm min-wartości.