Linear counting: Jak odhadnout počet unikátních hodnot

Jak bychom mohli spočítat počet unikátních hodnot v nějaké sadě dat, pokud by těchto dat bylo opravdu hodně? Můžeme mít například službu, která měří počet unikátních uživatelů na nějakém velkém webu nebo klidně na celé .cz/.com/.whatever doméně či tak něco.

Naivní postup

Ok, není přece co řešit, zkrátka projdeme data a vždy si každou hodnotu uložíme právě jednou do nějaké vhodné datové struktury. V Pythonu bychom to mohli napsat asi takto (kód je zbytečně ukecaný, to je schválně):

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

Funguje to. No dobře, ale co když ta data budou 36znakové unikátní v4 identifikátory a co když těch unikátních idéček bude třeba deset milionů? No… program stále vypočítá správnou hodnotu, ale kolik zabere paměti? Můžeme si to zkusit spočítat. Pro jednoduchost budeme předpokládat, že uuid ukládáme opravdu jako 36znakový string. Jedno uuid tak zabírá 36 bajtů, deset milionů idéček zabírá 360 MB.

Není to úplně málo, přiznejme si. Pokud by těch unikátních idéček bylo sto milionů, šli bychom už do řádů gigabajtů zabrané paměti. A to stále počítáme čistě jen to, co zaberou data. Přidejte si nějaký overhead, který zabere třeba Python/JavaScript a můžete se do řádů gigabajtů dostat i s deseti miliony idéček:

To nechceš. Jak z toho ven?

Můžeme zkusit nějak efektivněji uložit samotná idéčeka, můžeme místo Pythonu použít Céčko, čímž zásadně snížíme paměťové nároky, ale pořád to nebude ono a stále by takový program zabíral neskutečné množství místa. Zbývá si položit otázku: opravdu potřebujeme na chlup přesně vědět, jestli těch unikátních hodnot je zrovna 9 563 618? Stalo by se něco, kdybychom pracovali s počtem 9 547 666? Pokud vaše odpověď zní, že stalo a že to chcete přesně, tak prosím, jak račte. V opačném případě si pojďme ukázat postupy, jak počet unikátních hodnot v sadě dat co nejpřesněji, nejrychleji a s minimálními paměťovými nároky odhadnout.

Hashovací funkce — naše záchrana

Budeme uvažovat hashovací funkci, která bere na vstupu string a na výstupu vrací nějaké n-bitové číslo. Pokud jste zvyklí spíše na hashovací funkce, které „vrací string“, tak si to prostě představte tak, že ten string zase dále zkonvertuje na číslo, na tom nic není. Počet bitů pak udává, jak velké číslo je. 8bitová funkce vrací číslo, které zabírá osm bitů a do osmi bitů lze uložit 2⁸ různých hodnot, typicky pak celá čísla od 0 do 255. Budeme dále pracovat s 24bitovou hashovací funkcí. Taková funkce vrací 2²⁴ různých hodnot, což je 16 777 216.

Místo toho, abychom si ukládali hodnoty samotné, budeme si ukládat jejich 24bitové hashe. Pro uložení deseti milionů 24bitových hashů potřebujeme 30 MB. To je o řád lepší než předešlých 360 MB. Kód by mohl vypadat takto:

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

Funkce hash je nativní funkce Pythonu a vrací celé číslo, funkce nhash ukazuje naivní implementaci n-bitové hashovací funkce; není důležité pochopit jak funguje, protože stejně nefunguje správně — výsledek té funkce nezabírá 24 bitů, ale to je teď jedno, jde mi o princip.

Pak už následuje funkce count_unique_using_nhash, která počítá unikátní hodnoty. Projde všechny hodnoty, spočítá jejich hash a tu uloží do proměnné found, pokud už tam tato hodnota není.

Problémem tohoto postupu je, že hashovací funkce může pro různé řetězce vrátit stejný checksum — může nastat kolize. Čím více takových kolizí nastane, tím nepřesnější výsledek dostáváme. Funkce count_unique_using_nhash téměř vždy vrátí menší počet unikátních hodnot, než kolik jich ve skutečnosti je.

A jakou hashovací funkci zvolit? Zase tak moc na tom nezáleží, ale obecně se doporučuje nějaká varianta MurmurHashe.

Bitové mapy

Dávali jste pozor v Základech programování v jazyku C? Pokud ano, tak znáte bitové mapy. Jak by jich šlo využít?

Myšlenku si nastíníme na poli. My totiž nemusíme uchovávat vypočítané checksumy, my můžeme vytvořit pole o délce 2²⁴ a všechny prvky inicializujeme na nulu. Potom ve chvíli, kdy narazíme na nějaký checksum — což je číslo! — tak do tohoto pole na index checksum zapíšeme jedničku, čímž si zaznačíme, že tento checksum už jsme našli. Počet unikátních prvků pak bude přibližně roven počtu jedniček v tomto poli. Kód by mohl vypadat takto:

def count_unique_using_array(values):
    # seznam o delce 2^24 inicializovany na same nuly
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Nicméně používat pole je v tomto případě paměťově velice náročné, protože si do každé buňky potřebujeme uložit vždy buď jedničku, nebo nulu. Místo toho můžeme použít bitové pole. Abyste rozumněli, celé číslo (integer) lze uložit například do 32 bitů. Když si převedeme číslo 354 do binární soustavy, dostaneme 101100010. Číslo 354 by tak v počítači jako 32bitový integer bylo uloženo (na detaily kašleme, ju?) takto:

00000000 00000000 00000001 01100010

To je takový docela milý formát, který bychom mohli využít, že? My totiž v naší funkci chceme ukládat pouze jedničky a nuly a teď jsme právě zjistili, že obyčejné číslo vlastně není nic jiného než hromada nul a jedniček (asi jako všechno v počítači…). Zkrátka, pomocí bitových operátorů můžeme uložit jedničku tak, že bude opravdu zabírat jeden bit.

Vrátíme se k naší funkci s polem. Pokud bychom to přepsali do bitových polí, stačilo by nám pro 24bitovou hashovací funkci bitové pole o velikosti 2²⁴ bitů, což jsou 2 MiB. To je slušný upgrade!

Při použití 32bitové hashovací funkce, která má 2³² různých výstupních hodnot, což je 4 294 967 296, bychom potřebovali bitové pole o velikosti půl giga. To není úplně špatné na to, že tím jsme schopni počítat unikáty až někam do řádů miliard.

Linear Counting

Už jsem zmínil, že při použití hashovací funkce dostáváme pouze odhad počtu unikátních hodnot. Tento odhad je tím více nepřesný, čím více se počet unikátních hodnot blíží počtu různých výstupních hodnot hashovací funkce. Je logické, že když máme sadu dat, ve které je pět miliard unikátních hodnot, že to 24bitovou hashovací funkcí prostě nespočítáme.

Nicméně odhad, který vypočítáme pomocí hashovacích funkcí, lze dále zpřesnit. Používá se k tomu jednoduchá myšlenka — čím více unikátních hodnot v sadě dat je, tím je pravděpodobnější, že budou časem vznikat kolize. (Kolize = dva různé vstupy mají stejný výstup z hashovací funkce, stejný checksum.) Teď budeme trochu počítat, proto si zavedeme pár proměnných:

• Budeme pracovat s n bitovou hashovací funkcí h.
• Počet všech možných výstupů funkce h je tak roven 2n. Tento počet si označíme písmenem m, tedy: m=2n.
• Bitové pole, do kterého si budeme ukládat, které checksumy jsme našli, si označíme velkým písmenem A. Pole A má délku m.
• Pokud projdeme naším algoritmem celou sadu dat, budou některé hodnoty v bitovém poli rovny nule a některé jedničce. Nás bude hlavně zajímat podíl „počet nul děleno délka pole“, což nám udává relativní podíl nul v bitovém poli. Na začátku je ten podíl rovný 1, protože pole je inicializováno na samé nuly. Pokud by to bylo fifty-fifty, podíl by byl roven jedné polovině atp. Tuto hodnotu si označíme Z a vypočítáme jako Z = počet nul / m.

V tuto chvíli platí, že čím vyšší hodnota Z, tím vyšší máme jistotu, že náš odhad počtu unikátů je přesný. Pokud například projdeme prázdnou sadu dat, zůstanou v bitovém poli samé nuly a hodnota Z bude rovna jedné — máme tak úplnou jistotu, že v naší sadě dat je tolik unikátních prvků, kolik je v bitovém poli jedniček — nula.

Pokud je hodnota Z rovna 0,99, znamená to, že je bitové pole jedničkami zaplněno z jedné setiny. 99 % pole obsahuje nuly. To je ještě dobré, je pravděpodobné, že během výpočtu nenastalo příliš kolizí a bude třeba žádná nebo jen minimální oprava. Pokud je ale hodnota Z rovna 0,05, jen 5 % pole zůstalo nulové a pravděpodobně jsme během výpočtu narazili na mnoho a mnoho kolizí — bude třeba velká oprava.

Jak ale tuto opravu vypočítat? Pomůžeme si logaritmem, což je funkce, která má tento tvar:

Nás bude zajímat ta červená část na intervalu (0, 1>. Pokud budeme na ose x nanášet hodnotu Z, tak docílíme toho, že čím vyšší Z, tím více se bude hodnota y přibližovat nule. A naopak — čím menší Z, tím menší bude hodnota y. Výsledný odhad vypočteme tak, že toto číslo vynásobíme -m. Všimněte si, že pro dostatečně nízkou hodnotu Z dostaneme číslo, které je dokonce menší než -1 a pokud tuto hodnotu vynásobíme -m, získáme odhad, který je větší než m: odhadli jsme, že počet unikátů je větší než počet všech možných checksumů, které mohou vylézt z hashovací funkce h.

Celý vzorec pro výpočet počtu p unikátních hodnot by vypadal takto:

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

Implementace (bez bitových polí, jen s obyčejnými poli) by mohla vypadat takto:

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 je zde prirozeny logaritmus o zakladu 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)

Ve funkci linear_counting nejprve vypočítáme první odhad pomocí předchozího algoritmu, který využívá n-bitovou hashovací funkci. Potom vypočítáme podíl nul v poli a provedeme opravu podle vzorce. Logaritmus v kódu je přirozený logaritmus. Proměnná nonunique_values obsahuje number_of_unique_values unikátních řetězců, v tomto příkladě je tak v seznamu nonunique_values deset tisíc unikátních hodnot. Ten divný kód na šestém řádku zařídí to, aby v poli bylo více stejných hodnot: prostě na konec seznamu připojíme tentýž seznam hodnost a každá hodnota je tak v poli dvakrát. A pak už počítáme. Funkce by ideálně měla vrátit, že seznam obsahuje deset tisíc unikátů. Výstup:

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

Protože se vždy generuje jiný seznam nonunique_values, tak se výsledky budou s každým voláním lišit. Použili jsme 16bitovou hashovací funkci. Vidíme, že první odhad z funkce count_unique_using_array byl, že seznam obsahuje 9289 unikátů. Tento odhad jsme korekcí zpřesnili na 10 016, což už je celkem slušné: náš odhad je větší jen o 0,16 %, zatímco předtím byl menší o 7,11 % — to je docela hodně.

Pokud bychom vzali „větší“ hashovací funkci, například 24bitovou, dostali bychom přesnější výsledek:

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

Už samotný původní odhad byl OK, zpřesnění už se dostalo na rovných deset tisíc. Pro ukázku si můžeme zkusit milion unikátních idéček, tj. number_of_unique_values = 1000000. S 24bitovou hashovací funkcí se dostaneme na tyto výsledky:

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

To jde. Přitom, pokud to implementujeme jako bitové pole, tak by nám pole mělo sežrat jen zmíněné dva megabajty (+ co sežere jazyk). Za mě docela dobré. But we can do better! Much better. Ale až příště.

V mezičase si můžete přečíst článek A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Anebo můžete pokračovat na další díl série: algoritmus min-value.