Linear Counting: hogyan becsüljük meg az egyedi értékek számát

Hogyan tudnánk megszámolni az egyedi értékeket egy adathalmazban, ha nagyon-nagyon sok adatunk van? Lehet például egy szolgáltatásunk, amely egy nagy weboldalon, vagy akár egy egész .hu/.com/.whatever tartományon méri az egyedi felhasználók számát.

Naiv megoldás

Oké, nincs itt mit törni a fejünket: végigmegyünk az adatokon, és minden értéket pontosan egyszer eltárolunk valamilyen megfelelő adatszerkezetben. Pythonban nagyjából így írhatnánk meg (a kód szándékosan szószátyár):

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

Működik. Jó, de mi van, ha az adatok 36 karakteres egyedi v4 azonosítók, és mondjuk tízmillió egyedi azonosítónk van? Hát… a program továbbra is a helyes értéket számolja ki, de mennyi memóriát foglal? Megpróbálhatjuk kiszámolni. Az egyszerűség kedvéért tegyük fel, hogy az uuid-t tényleg 36 karakteres stringként tároljuk. Egy uuid így 36 bájtot foglal, tízmillió azonosító pedig 360 MB-ot.

Valljuk be, ez nem kevés. Ha az egyedi azonosítók száma százmillió lenne, már gigabájtos nagyságrendű memóriát foglalnánk. És ekkor még mindig csak azt számoljuk, amennyit maguk az adatok foglalnak. Tedd hozzá az overheadet, amelyet mondjuk a Python/JavaScript foglal, és már tízmillió azonosítóval is eljuthatsz a gigabájtos nagyságrendig:

Ezt nem akarod. Hogyan jöjjünk ki ebből?

Megpróbálhatjuk hatékonyabban tárolni magukat az azonosítókat, Python helyett használhatunk C-t, ezzel jelentősen csökkentjük a memóriaigényt, de még mindig nem az igazi, és egy ilyen program még mindig hihetetlen mennyiségű helyet foglalna. Marad a kérdés: tényleg tűpontosan tudnunk kell, hogy az egyedi értékek száma éppen 9 563 618? Történne valami, ha 9 547 666-tal dolgoznánk? Ha a válaszod az, hogy igen, történne, és pontosan akarod, akkor tessék, ahogy tetszik. Ellenkező esetben nézzük meg, hogyan becsülhetjük meg az egyedi értékek számát egy adathalmazban a lehető legpontosabban, leggyorsabban és minimális memóriaigénnyel.

Hash-függvény – a megmentőnk

Vegyünk egy hash-függvényt, amely bemenetként egy stringet kap, kimenetként pedig valamilyen n bites számot ad. Ha inkább olyan hash-függvényekhez szoktál, amelyek „stringet adnak vissza”, képzeld el úgy, hogy azt a stringet még átalakítjuk számmá, nincs ebben semmi ördöngösség. A bitek száma azt mondja meg, mekkora a szám. A 8 bites függvény olyan számot ad, amely nyolc bitet foglal, és nyolc bitbe 2⁸ különböző érték fér, jellemzően a 0-tól 255-ig terjedő egész számok. A továbbiakban 24 bites hash-függvénnyel dolgozunk. Egy ilyen függvény 2²⁴ különböző értéket ad, ez 16 777 216.

Maguk az értékek helyett a 24 bites hasheiket fogjuk tárolni. Tízmillió 24 bites hash tárolásához 30 MB kell. Ez egy nagyságrenddel jobb az előző 360 MB-nál. A kód így nézhet ki:

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

A hash függvény a Python natív függvénye, és egész számot ad vissza, az nhash függvény pedig az n bites hash-függvény naiv megvalósítását mutatja; nem fontos megérteni, hogyan működik, mert úgysem működik helyesen – a függvény eredménye nem 24 bitet foglal, de ez most mindegy, az elv a lényeg.

Ezután jön a count_unique_using_nhash függvény, amely az egyedi értékeket számolja. Végigmegy az összes értéken, kiszámítja a hashüket, és a found változóba menti, ha az az érték még nincs benne.

Ennek a megoldásnak az a baja, hogy a hash-függvény különböző szövegekre ugyanazt a checksumot adhatja vissza – ütközés (kollízió) léphet fel. Minél több ilyen ütközés van, annál pontatlanabb eredményt kapunk. A count_unique_using_nhash függvény szinte mindig kisebb számú egyedi értéket ad vissza, mint amennyi valójában van.

És melyik hash-függvényt válasszuk? Annyira nem számít, de általában valamelyik MurmurHash-változatot ajánlják.

Bittérképek

Figyeltél a C programozás alapjain? Ha igen, ismered a bittérképeket. Hogyan használhatnánk őket?

Az ötletet egy tömbön vázoljuk fel. Nekünk ugyanis nem kell eltárolnunk a kiszámított checksumokat, létrehozhatunk egy 2²⁴ hosszú tömböt, és minden elemét nullára állítjuk. Aztán amikor találkozunk valamelyik checksummal – ami egy szám! –, a tömb checksum indexére egyest írunk, ezzel megjelöljük, hogy ezt a checksumot már megtaláltuk. Az egyedi elemek száma ekkor megközelítőleg egyenlő lesz a tömbben lévő egyesek számával. A kód így nézhet ki:

def count_unique_using_array(values):
    # 2^24 hosszu lista, csupa nullaval inicializalva
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Mindazonáltal tömböt használni ebben az esetben memóriában nagyon költséges, mert minden cellába vagy egyest, vagy nullát kell tárolnunk. Ehelyett használhatunk bitmezőt. Hogy értsd: egy egész számot (integert) például 32 bitben lehet tárolni. Ha a 354-es számot átváltjuk kettes számrendszerbe, 101100010-t kapunk. A 354-es szám tehát a számítógépben 32 bites integerként így lenne tárolva (a részletekre fütyülünk, jó?):

00000000 00000000 00000001 01100010

Ez egy elég kellemes formátum, amelyet kihasználhatnánk, nem? Hiszen a függvényünkben csak egyeseket és nullákat akarunk tárolni, és most jöttünk rá, hogy egy közönséges szám tulajdonképpen nem más, mint egy rakás nulla és egyes (mint ahogy a számítógépben minden…). Röviden: a bitműveletek segítségével úgy tárolhatunk egyest, hogy tényleg csak egy bitet foglaljon.

Térjünk vissza a tömbös függvényünkhöz. Ha bitmezőkre írnánk át, a 24 bites hash-függvényhez elég lenne egy 2²⁴ bit méretű bitmező, ami 2 MiB. Ez tisztességes előrelépés!

32 bites hash-függvénynél, amelynek 2³² különböző kimeneti értéke van, ez 4 294 967 296, fél giga méretű bitmezőre lenne szükségünk. Ez nem is rossz, hiszen így az egyedi elemeket valahová a milliárdos nagyságrendig meg tudjuk számolni.

Linear Counting

Említettem már, hogy hash-függvény használatakor az egyedi értékek számának csak a becslését kapjuk. Ez a becslés annál pontatlanabb, minél jobban megközelíti az egyedi értékek száma a hash-függvény különböző kimeneti értékeinek számát. Logikus, hogy ha van egy adathalmazunk ötmilliárd egyedi értékkel, azt 24 bites hash-függvénnyel egyszerűen nem tudjuk megszámolni.

A hash-függvényekkel kiszámított becslést azonban tovább lehet pontosítani. Ehhez egy egyszerű gondolatot használunk – minél több egyedi érték van az adathalmazban, annál valószínűbb, hogy idővel ütközések keletkeznek. (Ütközés = két különböző bemenetnek ugyanaz a kimenete a hash-függvényből, ugyanaz a checksum.) Most egy kicsit számolni fogunk, ezért bevezetünk néhány változót:

• n bites h hash-függvénnyel dolgozunk.
• A h függvény összes lehetséges kimenetének száma így 2n. Ezt a számot m betűvel jelöljük, tehát: m=2n.
• Azt a bitmezőt, amelybe eltároljuk, hogy mely checksumokat találtuk meg, A nagybetűvel jelöljük. Az A mező hossza m.
• Ha az algoritmusunkkal végigmegyünk a teljes adathalmazon, a bitmezőben egyes értékek nullák lesznek, mások egyesek. Minket főleg a „nullák száma osztva a mező hosszával” hányados érdekel, amely a nullák relatív arányát adja meg a bitmezőben. Az elején ez az arány 1, mert a mező csupa nullával van inicializálva. Ha fele-fele lenne, az arány fél lenne, és így tovább. Ezt az értéket Z-vel jelöljük, és így számítjuk ki: Z = nullák száma / m.

Ekkor igaz, hogy minél nagyobb a Z értéke, annál nagyobb a biztosságunk, hogy a becslésünk az egyedi értékek számáról pontos. Ha például egy üres adathalmazon megyünk végig, a bitmezőben csupa nulla marad, és a Z értéke egy lesz – így teljesen biztosak vagyunk benne, hogy az adathalmazunkban annyi egyedi elem van, ahány egyes a bitmezőben van – nulla.

Ha a Z értéke 0,99, az azt jelenti, hogy a bitmezőnek egy századrésze van egyesekkel kitöltve. A mező 99%-a nullát tartalmaz. Ez még jó, valószínű, hogy a számítás során nem történt túl sok ütközés, és talán semmilyen vagy csak minimális javításra lesz szükség. Ha viszont a Z értéke 0,05, a mezőnek csak 5%-a maradt nulla, és valószínűleg a számítás során nagyon-nagyon sok ütközéssel találkoztunk – nagy javításra lesz szükség.

De hogyan számítsuk ki ezt a javítást? Segít a logaritmus, ez egy olyan függvény, amelynek ilyen az alakja:

Minket a piros rész érdekel a ]0; 1] intervallumon. Ha az x tengelyen a Z értékét vesszük fel, akkor azt érjük el, hogy minél nagyobb a Z, annál jobban közelít az y értéke a nullához. És fordítva – minél kisebb a Z, annál kisebb lesz az y értéke. A végső becslést úgy számítjuk ki, hogy ezt a számot megszorozzuk -m-mel. Vedd észre, hogy elég alacsony Z értékre olyan számot kapunk, amely még -1-nél is kisebb, és ha ezt az értéket megszorozzuk -m-mel, m-nél nagyobb becslést kapunk: azt becsültük, hogy az egyedi értékek száma nagyobb, mint a h hash-függvényből kijöhető összes lehetséges checksum száma.

Az egyedi értékek p számának kiszámítására szolgáló teljes képlet így nézne ki:

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

A megvalósítás (bitmezők nélkül, csak közönséges tömbökkel) így nézhet ki:

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
    # a log itt az e alapu termeszetes logaritmus
    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)

A linear_counting függvényben először kiszámítjuk az első becslést az előző algoritmussal, amely n bites hash-függvényt használ. Aztán kiszámítjuk a nullák arányát a tömbben, és a képlet szerint elvégezzük a javítást. A kódban a logaritmus természetes logaritmus. A nonunique_values változó number_of_unique_values egyedi stringet tartalmaz, ebben a példában tehát a nonunique_values listában tízezer egyedi érték van. Az a fura kód a hatodik sorban azt éri el, hogy a tömbben több azonos érték legyen: egyszerűen a lista végére fűzzük ugyanazt az értéklistát, így minden érték kétszer szerepel. És aztán már számolunk. A függvénynek ideális esetben azt kellene visszaadnia, hogy a lista tízezer egyedit tartalmaz. A kimenet:

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

Mivel mindig más nonunique_values lista generálódik, az eredmények minden híváskor eltérnek. 16 bites hash-függvényt használtunk. Látjuk, hogy a count_unique_using_array függvény első becslése az volt, hogy a lista 9289 egyedit tartalmaz. Ezt a becslést a korrekcióval 10 017-re pontosítottuk, ami már egész szép: a becslésünk csak 0,17%-kal nagyobb, míg korábban 7,11%-kal volt kisebb – ez elég sok.

Ha „nagyobb” hash-függvényt vennénk, például 24 bitest, pontosabb eredményt kapnánk:

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

Már az eredeti becslés is rendben volt, a pontosítás pedig pont tízezerig vitte. Bemutatóként kipróbálhatunk egymillió egyedi azonosítót is, azaz number_of_unique_values = 1000000. 24 bites hash-függvénnyel ezeket az eredményeket kapjuk:

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

Nem rossz. Közben ha bitmezőként valósítjuk meg, a mezőnek csak az említett két megabájtot kellene felfalnia (+ amit a nyelv felfal). Szerintem egész jó. But we can do better! Much better. De csak legközelebb.

Addig elolvashatod az A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] cikket. Vagy folytathatod a sorozat következő részével: a min-value algoritmus.