Linear Counting: jak oszacować liczbę unikalnych wartości

Jak moglibyśmy policzyć, ile unikalnych wartości jest w jakimś zbiorze danych, gdyby tych danych było naprawdę dużo? Możemy mieć na przykład usługę, która mierzy liczbę unikalnych użytkowników na jakiejś dużej stronie albo nawet w całej domenie .pl/.com/.whatever czy coś w tym stylu.

Naiwne podejście

Ok, przecież nie ma nad czym się zastanawiać, po prostu przejdziemy przez dane i każdą wartość zapiszemy dokładnie raz w jakiejś odpowiedniej strukturze danych. W Pythonie moglibyśmy to napisać mniej więcej tak (kod jest niepotrzebnie rozgadany, celowo):

nonunique_values = [1, 2, 3, 2, 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

Działa. No dobrze, ale co jeśli tymi danymi będą 36-znakowe unikalne identyfikatory v4 i co jeśli tych unikalnych identyfikatorów będzie, powiedzmy, dziesięć milionów? No… program nadal obliczy poprawną wartość, ale ile zajmie pamięci? Możemy spróbować to policzyć. Dla uproszczenia założymy, że uuid zapisujemy naprawdę jako 36-znakowy string. Jeden uuid zajmuje więc 36 bajtów, dziesięć milionów identyfikatorów zajmuje 360 MB.

Przyznajmy, że to nie jest całkiem mało. Gdyby unikalnych identyfikatorów było sto milionów, zajęta pamięć szłaby już w gigabajty. A wciąż liczymy wyłącznie to, co zajmują same dane. Dodaj do tego narzut, jaki dokłada na przykład Python czy JavaScript, a do gigabajtów dojdziesz nawet z dziesięcioma milionami identyfikatorów:

Tego nie chcesz. Jak z tego wybrnąć?

Możemy spróbować jakoś efektywniej zapisywać same identyfikatory, możemy zamiast Pythona użyć C, przez co zasadniczo zmniejszymy zużycie pamięci, ale to wciąż nie będzie to i taki program nadal zajmowałby niewyobrażalnie dużo miejsca. Pozostaje zadać sobie pytanie: czy naprawdę musimy co do sztuki wiedzieć, że unikalnych wartości jest akurat 9 563 618? Czy stałoby się coś, gdybyśmy pracowali z liczbą 9 547 666? Jeśli twoja odpowiedź brzmi, że tak i że chcesz to mieć dokładnie, to proszę bardzo. W przeciwnym razie pokażmy sobie sposoby, jak liczbę unikalnych wartości w zbiorze danych oszacować możliwie dokładnie, możliwie szybko i przy minimalnym zużyciu pamięci.

Funkcja haszująca — nasz ratunek

Rozważmy funkcję haszującą (funkcję skrótu), która na wejściu przyjmuje string, a na wyjściu zwraca jakąś n-bitową liczbę. Jeśli jesteś przyzwyczajony raczej do funkcji haszujących, które „zwracają string”, to po prostu wyobraź sobie, że ten string zostaje dalej zamieniony na liczbę, nic w tym trudnego. Liczba bitów mówi wtedy, jak duża jest ta liczba. Funkcja 8-bitowa zwraca liczbę, która zajmuje osiem bitów, a w ośmiu bitach można zapisać 2⁸ różnych wartości, typowo liczby całkowite od 0 do 255. Dalej będziemy pracować z 24-bitową funkcją haszującą. Taka funkcja zwraca 2²⁴ różnych wartości, czyli 16 777 216.

Zamiast zapisywać same wartości, będziemy zapisywać ich 24-bitowe hasze. Do zapisania dziesięciu milionów 24-bitowych haszy potrzebujemy 30 MB. To o rząd wielkości lepiej niż wcześniejsze 360 MB. Kod mógłby wyglądać tak:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 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 wbudowaną funkcją Pythona i zwraca liczbę całkowitą, funkcja nhash pokazuje naiwną implementację n-bitowej funkcji haszującej; nie trzeba rozumieć, jak działa, bo i tak nie działa poprawnie — jej wynik nie zajmuje 24 bitów, ale to teraz nieważne, chodzi mi o zasadę.

Potem następuje już funkcja count_unique_using_nhash, która liczy unikalne wartości. Przechodzi przez wszystkie wartości, oblicza ich hasz i zapisuje go w zmiennej found, jeśli jeszcze go tam nie ma.

Problem tego podejścia polega na tym, że funkcja haszująca może dla różnych napisów zwrócić ten sam hasz — może wystąpić kolizja. Im więcej takich kolizji wystąpi, tym mniej dokładny wynik dostajemy. Funkcja count_unique_using_nhash prawie zawsze zwróci mniejszą liczbę unikalnych wartości, niż jest ich w rzeczywistości.

A jaką funkcję haszującą wybrać? Nie ma to aż tak dużego znaczenia, ale ogólnie zaleca się jakiś wariant MurmurHasha.

Mapy bitowe

Czy uważałeś na zajęciach z podstaw programowania w języku C? Jeśli tak, to znasz mapy bitowe. Jak można by ich użyć?

Pomysł naszkicujemy na zwykłej tablicy. Nie musimy bowiem przechowywać obliczonych haszy, możemy utworzyć tablicę o długości 2²⁴ i wszystkie jej elementy zainicjować zerem. Potem, kiedy natrafimy na jakiś hasz — który jest liczbą! — zapiszemy w tej tablicy pod indeksem checksum jedynkę, i w ten sposób zaznaczymy, że ten hasz już znaleźliśmy. Liczba unikalnych elementów będzie wtedy w przybliżeniu równa liczbie jedynek w tej tablicy. Kod mógłby wyglądać tak:

def count_unique_using_array(values):
    # lista o dlugosci 2^24 zainicjowana samymi zerami
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Używanie zwykłej tablicy jest jednak w tym przypadku bardzo kosztowne pamięciowo, bo w każdej komórce potrzebujemy zapisać tylko jedynkę albo zero. Zamiast tego możemy użyć tablicy bitowej. Żeby było jasne: liczbę całkowitą (integer) można zapisać na przykład w 32 bitach. Kiedy zamienimy liczbę 354 na system dwójkowy, dostaniemy 101100010. Liczba 354 byłaby więc w komputerze jako 32-bitowy integer zapisana (szczegóły pomijamy, dobra?) tak:

00000000 00000000 00000001 01100010

To całkiem miły format, który moglibyśmy wykorzystać, prawda? W naszej funkcji chcemy przecież zapisywać tylko jedynki i zera, a właśnie odkryliśmy, że zwykła liczba to w gruncie rzeczy nic innego niż kupka zer i jedynek (jak wszystko w komputerze…). Krótko mówiąc, za pomocą operatorów bitowych możemy zapisać jedynkę tak, żeby naprawdę zajmowała jeden bit.

Wróćmy do naszej funkcji z tablicą. Gdybyśmy ją przepisali na tablice bitowe, dla 24-bitowej funkcji haszującej wystarczyłaby nam tablica bitowa o rozmiarze 2²⁴ bitów, czyli 2 MiB. To porządny upgrade!

Przy użyciu 32-bitowej funkcji haszującej, która ma 2³² różnych wartości wyjściowych, czyli 4 294 967 296, potrzebowalibyśmy tablicy bitowej o rozmiarze pół giga. To nie jest takie złe, biorąc pod uwagę, że w ten sposób jesteśmy w stanie liczyć unikalne wartości gdzieś do rzędu miliardów.

Linear Counting

Już wspomniałem, że przy użyciu funkcji haszującej dostajemy tylko oszacowanie liczby unikalnych wartości. To oszacowanie jest tym mniej dokładne, im bardziej liczba unikalnych wartości zbliża się do liczby różnych wartości wyjściowych funkcji haszującej. To logiczne, że jeśli mamy zbiór danych, w którym jest pięć miliardów unikalnych wartości, to 24-bitową funkcją haszującą po prostu ich nie policzymy.

Oszacowanie, które obliczymy za pomocą funkcji haszujących, można jednak jeszcze poprawić. Wykorzystuje się do tego prostą myśl — im więcej unikalnych wartości jest w zbiorze danych, tym bardziej prawdopodobne, że z czasem będą powstawać kolizje. (Kolizja = dwa różne wejścia dają ten sam wynik funkcji haszującej, ten sam hasz.) Teraz będziemy trochę liczyć, dlatego wprowadzimy kilka zmiennych:

• Będziemy pracować z n-bitową funkcją haszującą h.
• Liczba wszystkich możliwych wyników funkcji h jest więc równa 2n. Tę liczbę oznaczymy literą m, czyli: m=2n.
• Tablicę bitową, w której będziemy zapisywać, jakie hasze znaleźliśmy, oznaczymy wielką literą A. Tablica A ma długość m.
• Kiedy przejdziemy naszym algorytmem cały zbiór danych, niektóre wartości w tablicy bitowej będą równe zeru, a niektóre jedynce. Interesować nas będzie przede wszystkim stosunek „liczba zer podzielona przez długość tablicy”, który mówi, jaką część tablicy bitowej zajmują zera. Na początku ten stosunek jest równy 1, bo tablica jest zainicjowana samymi zerami. Gdyby było pół na pół, stosunek byłby równy jednej drugiej itd. Tę wartość oznaczymy Z i obliczymy jako Z = liczba zer / m.

Teraz już widać, że im wyższa wartość Z, tym większą mamy pewność, że nasze oszacowanie liczby unikalnych wartości jest dokładne. Jeśli na przykład przejdziemy pusty zbiór danych, w tablicy bitowej zostaną same zera i wartość Z będzie równa jeden — mamy więc całkowitą pewność, że w naszym zbiorze danych jest tyle unikalnych elementów, ile jest w tablicy bitowej jedynek — zero.

Jeśli wartość Z jest równa 0,99, oznacza to, że tablica bitowa jest wypełniona jedynkami w jednej setnej. 99% tablicy zawiera zera. To jeszcze dobrze, jest prawdopodobne, że podczas obliczeń nie wystąpiło zbyt wiele kolizji i poprawka nie będzie potrzebna albo wystarczy minimalna. Jeśli jednak wartość Z jest równa 0,05, tylko 5% tablicy zostało zerowe i podczas obliczeń prawdopodobnie natrafiliśmy na mnóstwo kolizji — potrzebna będzie duża poprawka.

Jak jednak tę poprawkę obliczyć? Pomożemy sobie logarytmem, czyli funkcją, która wygląda tak:

Interesować nas będzie ta czerwona część na przedziale (0, 1>. Jeśli na osi x będziemy odkładać wartość Z, osiągniemy to, że im wyższe Z, tym bardziej wartość y będzie się zbliżać do zera. I odwrotnie — im mniejsze Z, tym mniejsza będzie wartość y. Ostateczne oszacowanie obliczymy tak, że tę liczbę pomnożymy przez -m. Zauważ, że dla dostatecznie niskiej wartości Z dostaniemy liczbę, która jest nawet mniejsza niż -1, a jeśli tę wartość pomnożymy przez -m, otrzymamy oszacowanie większe niż m: oszacowaliśmy, że liczba unikalnych wartości jest większa niż liczba wszystkich możliwych haszy, jakie mogą wyjść z funkcji haszującej h.

Cały wzór na obliczenie liczby p unikalnych wartości wyglądałby tak:

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

Implementacja (bez tablic bitowych, tylko ze zwykłymi tablicami) mogłaby wyglądać tak:

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 jest tu logarytmem naturalnym o podstawie 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 za pomocą poprzedniego algorytmu, który wykorzystuje n-bitową funkcję haszującą. Potem obliczamy, jaką część tablicy zajmują zera, i wykonujemy poprawkę według wzoru. Logarytm w kodzie jest logarytmem naturalnym. Zmienna nonunique_values zawiera number_of_unique_values unikalnych napisów, w tym przykładzie jest więc na liście nonunique_values dziesięć tysięcy unikalnych wartości. Ten dziwny kod w szóstym wierszu sprawia, że w tablicy będzie więcej takich samych wartości: po prostu na koniec listy doklejamy tę samą listę wartości i każda wartość jest w tablicy dwa razy. A potem już liczymy. Funkcja powinna w idealnym przypadku zwrócić, że lista zawiera dziesięć tysięcy unikalnych wartości. Wynik:

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

Ponieważ za każdym razem generuje się inna lista nonunique_values, wyniki będą się przy każdym wywołaniu różnić. Użyliśmy 16-bitowej funkcji haszującej. Widzimy, że pierwsze oszacowanie z funkcji count_unique_using_array mówiło, że lista zawiera 9289 unikalnych wartości. To oszacowanie poprawiliśmy korektą do 10 017, co jest już całkiem przyzwoite: nasze oszacowanie jest większe tylko o 0,17%, podczas gdy wcześniej było mniejsze o 7,11% — a to całkiem sporo.

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

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

Już samo pierwotne oszacowanie było OK, a po poprawce doszliśmy do równych dziesięciu tysięcy. Dla przykładu możemy spróbować miliona unikalnych identyfikatorów, tzn. number_of_unique_values = 1000000. Z 24-bitową funkcją haszującą dojdziemy do takich wyników:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Nieźle. A przy tym, jeśli zaimplementujemy to jako tablicę bitową, tablica zjadłaby nam tylko wspomniane dwa megabajty (+ to, co zje język). Jak dla mnie całkiem dobrze. But we can do better! Much better. Ale dopiero następnym razem.

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