Linear Counting: cum estimăm numărul de valori unice

Cum am putea număra valorile unice dintr-un set de date, dacă datele sunt cu adevărat foarte multe? Putem avea, de exemplu, un serviciu care măsoară numărul de utilizatori unici ai unui site mare sau chiar ai întregului domeniu .ro/.com/.whatever sau ceva de felul acesta.

Abordarea naivă

Ok, nu e nimic de discutat, parcurgem datele și memorăm fiecare valoare exact o dată într-o structură de date potrivită. În Python am putea scrie așa (codul este inutil de vorbăreț, e intenționat):

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

Funcționează. Bine, dar ce se întâmplă dacă datele sunt identificatori unici uuid v4 de 36 de caractere și dacă ID-urile unice sunt, să zicem, zece milioane? Ei bine… programul calculează în continuare valoarea corectă, dar cât de multă memorie ocupă? Putem încerca să calculăm. Pentru simplitate presupunem că uuid-ul îl stocăm chiar ca string de 36 de caractere. Un uuid ocupă deci 36 de octeți, iar zece milioane de ID-uri ocupă 360 MB.

Nu e chiar puțin, să recunoaștem. Dacă ID-urile unice ar fi o sută de milioane, am ajunge deja la ordinul gigaocteților de memorie ocupată. Și încă numărăm doar ce ocupă datele propriu-zise. Adaugă și overhead-ul pe care îl ocupă Python/JavaScript și poți ajunge la ordinul gigaocteților și cu zece milioane de ID-uri:

Nu vrei asta. Cum scăpăm?

Putem încerca să stocăm mai eficient ID-urile în sine, putem folosi C în loc de Python, ceea ce reduce esențial consumul de memorie, dar tot nu e ce trebuie, iar un astfel de program ar ocupa în continuare o cantitate uriașă de memorie. Rămâne întrebarea: chiar avem nevoie să știm exact, până la ultima unitate, dacă numărul de valori unice este tocmai 9.563.618? S-ar întâmpla ceva dacă am lucra cu 9.547.666? Dacă răspunsul tău este că da, s-ar întâmpla, și vrei exact, atunci te rog, cum dorești. Altfel, hai să vedem procedee prin care putem estima numărul de valori unice dintr-un set de date cât mai precis, cât mai rapid și cu cerințe minime de memorie.

Funcția hash – salvarea noastră

Să considerăm o funcție hash care primește la intrare un string și returnează la ieșire un număr de n biți. Dacă ești obișnuit mai degrabă cu funcții hash care „returnează un string”, imaginează-ți pur și simplu că acel string este apoi convertit în număr, nu e nimic special. Numărul de biți arată cât de mare este numărul. O funcție de 8 biți returnează un număr care ocupă opt biți, iar în opt biți pot fi stocate 2⁸ valori diferite, de obicei numerele întregi de la 0 la 255. Vom lucra în continuare cu o funcție hash de 24 de biți. O astfel de funcție returnează 2²⁴ valori diferite, adică 16.777.216.

În loc să stocăm valorile în sine, vom stoca valorile lor hash de 24 de biți. Pentru a stoca zece milioane de valori hash de 24 de biți avem nevoie de 30 MB. Este cu un ordin de mărime mai bine decât cei 360 MB de mai înainte. Codul ar putea arăta astfel:

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

Funcția hash este o funcție nativă din Python și returnează un număr întreg, iar funcția nhash arată o implementare naivă a unei funcții hash de n biți; nu e important să înțelegi cum funcționează, pentru că oricum nu funcționează corect – rezultatul ei nu ocupă 24 de biți, dar asta nu contează acum, mă interesează principiul.

Urmează funcția count_unique_using_nhash, care numără valorile unice. Parcurge toate valorile, calculează valoarea hash a fiecăreia și o stochează în variabila found, dacă acolo nu se află deja.

Problema acestei abordări este că funcția hash poate returna aceeași valoare (checksum) pentru șiruri diferite – poate apărea o coliziune. Cu cât apar mai multe coliziuni, cu atât rezultatul este mai imprecis. Funcția count_unique_using_nhash returnează aproape întotdeauna un număr de valori unice mai mic decât cel real.

Și ce funcție hash să alegem? Nu contează chiar atât de mult, dar în general se recomandă o variantă de MurmurHash.

Bitmap-uri

Ai fost atent la cursul de bazele programării în C? Dacă da, cunoști bitmap-urile (vectorii de biți). Cum le-am putea folosi?

Schițăm ideea pe un tablou. Noi nu trebuie să păstrăm valorile hash calculate, putem crea un tablou de lungime 2²⁴ și inițializa toate elementele cu zero. Apoi, când întâlnim o valoare hash – care este un număr! –, scriem un unu în acest tablou la indexul checksum, marcând astfel că am găsit deja această valoare. Numărul de elemente unice va fi atunci aproximativ egal cu numărul de unu din tablou. Codul ar putea arăta astfel:

def count_unique_using_array(values):
    # lista de lungime 2^24 initializata cu zerouri
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Totuși, folosirea unui tablou este în acest caz foarte costisitoare ca memorie, pentru că în fiecare celulă trebuie să stocăm fie un unu, fie un zero. În loc de asta putem folosi un vector de biți. Ca să înțelegi, un număr întreg (integer) poate fi stocat, de exemplu, pe 32 de biți. Dacă scriem numărul 354 în baza 2, obținem 101100010. Numărul 354 ar fi deci stocat în calculator ca integer pe 32 de biți (nu ne ocupăm de detalii, da?) astfel:

00000000 00000000 00000001 01100010

Este un format destul de drăguț, pe care l-am putea folosi, nu? Noi vrem în funcția noastră să stocăm doar unu și zero și tocmai am aflat că un număr obișnuit nu este altceva decât o grămadă de zerouri și unu (la fel ca orice altceva în calculator…). Pe scurt, cu ajutorul operatorilor pe biți putem stoca un unu astfel încât să ocupe într-adevăr un singur bit.

Revenim la funcția noastră cu tablou. Dacă am rescrie-o cu vectori de biți, pentru o funcție hash de 24 de biți ne-ar ajunge un vector de biți de 2²⁴ biți, adică 2 MiB. Este un upgrade serios!

Dacă folosim o funcție hash de 32 de biți, care are 2³² valori de ieșire diferite, adică 4.294.967.296, am avea nevoie de un vector de biți de o jumătate de gigaoctet. Nu e deloc rău, având în vedere că astfel putem număra valori unice până pe undeva prin ordinul miliardelor.

Linear Counting

Am menționat deja că, folosind o funcție hash, obținem doar o estimare a numărului de valori unice. Această estimare este cu atât mai imprecisă, cu cât numărul de valori unice se apropie mai mult de numărul de valori de ieșire diferite ale funcției hash. Este logic că, dacă avem un set de date cu cinci miliarde de valori unice, pur și simplu nu le putem număra cu o funcție hash de 24 de biți.

Totuși, estimarea pe care o calculăm cu ajutorul funcțiilor hash poate fi precizată în continuare. Se folosește o idee simplă – cu cât sunt mai multe valori unice în setul de date, cu atât este mai probabil ca, în timp, să apară coliziuni. (Coliziune = două intrări diferite au aceeași valoare de ieșire a funcției hash, același checksum.) Acum vom face puțin calcul, așa că introducem câteva variabile:

Vom lucra cu o funcție hash h de n biți.
Numărul tuturor ieșirilor posibile ale funcției h este deci 2ⁿ. Acest număr îl notăm cu litera m, adică: m=2ⁿ.
Vectorul de biți în care vom stoca ce valori hash am găsit îl notăm cu litera mare A. Vectorul A are lungimea m.
Dacă parcurgem cu algoritmul nostru întregul set de date, unele valori din vectorul de biți vor fi zero, iar altele unu. Ne va interesa mai ales raportul „numărul de zerouri împărțit la lungimea vectorului”, care ne dă ponderea relativă a zerourilor în vectorul de biți. La început acest raport este egal cu 1, pentru că vectorul este inițializat cu zerouri. Dacă ar fi fifty-fifty, raportul ar fi egal cu o jumătate etc. Această valoare o notăm cu Z și o calculăm ca Z = numărul de zerouri / m.

În acest moment are loc: cu cât valoarea Z este mai mare, cu atât avem mai multă siguranță că estimarea numărului de valori unice este precisă. Dacă, de exemplu, parcurgem un set de date vid, în vectorul de biți rămân doar zerouri și valoarea Z va fi egală cu unu – avem deci siguranță deplină că în setul nostru de date sunt atâtea elemente unice câte valori de unu sunt în vectorul de biți – zero.

Dacă valoarea Z este egală cu 0,99, înseamnă că vectorul de biți este plin cu unu în proporție de o sutime. 99% din vector conține zerouri. Asta este încă bine, este probabil că în timpul calculului nu au apărut prea multe coliziuni și nu va fi nevoie de nicio corecție sau doar de una minimă. Dar dacă valoarea Z este egală cu 0,05, doar 5% din vector a rămas cu zerouri și probabil am întâlnit în timpul calculului foarte multe coliziuni – va fi nevoie de o corecție mare.

Dar cum calculăm această corecție? Ne ajutăm de logaritm, o funcție care are această formă:

Ne interesează partea roșie de pe intervalul (0, 1]. Dacă pe axa x reprezentăm valoarea Z, obținem că, cu cât Z este mai mare, cu atât valoarea y se apropie mai mult de zero. Și invers – cu cât Z este mai mic, cu atât y este mai mic. Estimarea finală o calculăm înmulțind acest număr cu -m. Observă că pentru o valoare Z suficient de mică obținem un număr chiar mai mic decât -1, iar dacă îl înmulțim cu -m, obținem o estimare mai mare decât m: am estimat că numărul de valori unice este mai mare decât numărul tuturor valorilor hash posibile pe care le poate da funcția hash h.

Formula completă pentru calculul numărului p de valori unice ar arăta astfel:

$p = - m \cdot \ln Z$

Implementarea (fără vectori de biți, doar cu tablouri obișnuite) ar putea arăta astfel:

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 este aici logaritmul natural in baza 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)

În funcția linear_counting calculăm mai întâi prima estimare cu algoritmul anterior, care folosește o funcție hash de n biți. Apoi calculăm ponderea zerourilor din tablou și facem corecția după formulă. Logaritmul din cod este logaritmul natural. Variabila nonunique_values conține number_of_unique_values șiruri unice, deci în acest exemplu lista nonunique_values conține zece mii de valori unice. Codul ciudat de pe rândul al șaselea face ca în tablou să existe mai multe valori identice: pur și simplu adăugăm la sfârșitul listei aceeași listă de valori, astfel că fiecare valoare apare de două ori. Și apoi numărăm. Ideal, funcția ar trebui să returneze că lista conține zece mii de valori unice. Ieșirea:

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

Pentru că lista nonunique_values se generează de fiecare dată altfel, rezultatele vor diferi la fiecare apel. Am folosit o funcție hash de 16 biți. Vedem că prima estimare, dată de funcția count_unique_using_array, a fost că lista conține 9289 de valori unice. Această estimare am precizat-o prin corecție la 10.017, ceea ce e deja destul de bine: estimarea noastră este mai mare doar cu 0,17%, în timp ce înainte era mai mică cu 7,11% – asta e destul de mult.

Dacă luăm o funcție hash „mai mare”, de exemplu de 24 de biți, obținem un rezultat mai precis:

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

Chiar estimarea inițială era OK, iar corecția a ajuns la zece mii fix. Ca demonstrație, putem încerca un milion de ID-uri unice, adică number_of_unique_values = 1000000. Cu o funcție hash de 24 de biți obținem aceste rezultate:

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

Merge. Iar dacă îl implementăm ca vector de biți, vectorul ar ocupa doar cei doi megaocteți menționați (+ ce ocupă limbajul). Pentru mine e destul de bine. But we can do better! Much better. Dar abia data viitoare.

Între timp poți citi articolul A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Sau poți continua cu următoarea parte a seriei: algoritmul Min Value.

Capitole: Linear Counting, Min Value, LogLog, HyperLogLog

« Anterior: Din automat în expresie

Următor: Min Value »