Linear counting: miten arvioidaan uniikkien arvojen lukumäärä

Miten voisimme laskea uniikkien arvojen lukumäärän jostakin dataryhmästä, jos dataa olisi todella paljon? Meillä voisi olla esimerkiksi palvelu, joka mittaa uniikkien käyttäjien määrää jollakin suurella verkkosivustolla tai vaikka koko .fi/.com/.whatever-verkkotunnuksessa tai jossakin sen tapaisessa.

Naiivi menetelmä

No, eihän tässä ole mitään pohdittavaa: käydään data läpi ja tallennetaan jokainen arvo täsmälleen kerran johonkin sopivaan tietorakenteeseen. Pythonilla sen voisi kirjoittaa suunnilleen näin (koodi on turhan sanavalmista, se on tarkoituksellista):

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

Se toimii. Hyvä on, mutta entä jos data on 36-merkkisiä uniikkeja v4-tunnisteita ja uniikkeja tunnisteita on vaikkapa kymmenen miljoonaa? No… ohjelma laskee edelleen oikean arvon, mutta kuinka paljon se vie muistia? Voimme yrittää laskea sen. Yksinkertaisuuden vuoksi oletamme, että tallennamme uuid:n todella 36-merkkisenä merkkijonona. Yksi uuid vie siis 36 tavua, kymmenen miljoonaa tunnistetta vie 360 MB.

Myönnetään, ettei se ole ihan vähän. Jos uniikkeja tunnisteita olisi sata miljoonaa, olisimme jo gigatavujen suuruusluokassa varatussa muistissa. Ja silloin laskemme edelleen pelkästään sitä, mitä data vie. Lisää siihen jokin Pythonin tai JavaScriptin viemä lisäkulu, ja gigatavujen suuruusluokkaan voi päästä jo kymmenellä miljoonalla tunnisteella:

Sitä et halua. Miten tästä päästään eteenpäin?

Voimme yrittää tallentaa tunnisteet itse tehokkaammin, voimme käyttää Pythonin sijasta C-kieltä, mikä vähentää muistivaatimuksia ratkaisevasti, mutta ei se vieläkään ole se oikea, ja sellainenkin ohjelma veisi silti uskomattoman paljon tilaa. Jää kysyttäväksi: tarvitsemmeko todella tietää aivan täsmälleen, onko uniikkeja arvoja juuri nyt 9 563 618? Tapahtuisiko mitään, jos työskentelisimme luvulla 9 547 666? Jos vastauksesi on, että tapahtuisi ja että haluat sen täsmälleen, olkoon niin, ole hyvä vain. Muussa tapauksessa katsotaan menetelmiä, joilla uniikkien arvojen lukumäärä dataryhmässä arvioidaan mahdollisimman tarkasti, nopeasti ja pienillä muistivaatimuksilla.

Tiivistefunktio — pelastuksemme

Tarkastellaan tiivistefunktiota, joka ottaa syötteenä merkkijonon ja palauttaa tulosteena jonkin n-bittisen luvun. Jos olet tottunut enemmän tiivistefunktioihin, jotka ”palauttavat merkkijonon”, kuvittele vain, että se merkkijono muunnetaan vielä edelleen luvuksi, siinä ei ole mitään ihmeellistä. Bittien määrä kertoo, kuinka suuri luku on. 8-bittinen funktio palauttaa luvun, joka vie kahdeksan bittiä, ja kahdeksaan bittiin mahtuu 2⁸ eri arvoa, tyypillisesti kokonaisluvut 0:sta 255:een. Työskentelemme jatkossa 24-bittisellä tiivistefunktiolla. Tällainen funktio palauttaa 2²⁴ eri arvoa, eli 16 777 216.

Sen sijaan, että tallentaisimme itse arvot, tallennamme niiden 24-bittiset tiivisteet. Kymmenen miljoonan 24-bittisen tiivisteen tallentamiseen tarvitaan 30 MB. Se on suuruusluokan verran parempi kuin edelliset 360 MB. Koodi voisi näyttää tältä:

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

Funktio hash on Pythonin natiivifunktio ja palauttaa kokonaisluvun, funktio nhash esittää n-bittisen tiivistefunktion naiivin toteutuksen; sen toiminnan ymmärtäminen ei ole tärkeää, koska se ei joka tapauksessa toimi oikein — funktion tulos ei vie 24 bittiä, mutta sillä ei nyt ole väliä, tärkeintä on periaate.

Sitten seuraa funktio count_unique_using_nhash, joka laskee uniikit arvot. Se käy läpi kaikki arvot, laskee niiden tiivisteen ja tallentaa sen muuttujaan found, jos kyseistä arvoa ei vielä ole siellä.

Tämän menetelmän ongelma on, että tiivistefunktio voi palauttaa eri merkkijonoille saman tarkistussumman — voi syntyä törmäys. Mitä enemmän törmäyksiä syntyy, sitä epätarkempi tulos saadaan. Funktio count_unique_using_nhash palauttaa lähes aina pienemmän uniikkien arvojen määrän kuin niitä todellisuudessa on.

Ja minkä tiivistefunktion pitäisi valita? Sillä ei ole niin väliä, mutta yleisesti suositellaan jotakin MurmurHashin muunnelmaa.

Bittikartat

Olitko hereillä C-kielen ohjelmoinnin perusteiden kurssilla? Jos olit, tunnet bittikartat. Miten niitä voisi hyödyntää?

Hahmottelemme ajatuksen taulukon avulla. Meidän ei nimittäin tarvitse säilyttää laskettuja tarkistussummia, voimme luoda taulukon, jonka pituus on 2²⁴, ja alustaa kaikki alkiot nollaksi. Sitten kun kohtaamme jonkin tarkistussumman — joka on luku! — kirjoitamme tähän taulukkoon indeksiin checksum ykkösen, ja merkitsemme näin, että olemme jo löytäneet tämän tarkistussumman. Uniikkien alkioiden määrä on silloin suunnilleen yhtä suuri kuin ykkösten määrä tässä taulukossa. Koodi voisi näyttää tältä:

def count_unique_using_array(values):
    # 2^24 pituinen lista, jossa on pelkkiä nollia
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Taulukon käyttäminen on tässä tapauksessa kuitenkin muistin kannalta hyvin raskasta, koska jokaiseen soluun täytyy tallentaa joko ykkönen tai nolla. Sen sijaan voimme käyttää bittikenttää. Selvennykseksi: kokonaisluku (integer) voidaan tallentaa esimerkiksi 32 bittiin. Kun muunnamme luvun 354 kaksijärjestelmään, saamme 101100010. Luku 354 olisi tietokoneessa 32-bittisenä kokonaislukuna tallennettuna (yksityiskohdista emme välitä, vai mitä?) näin:

00000000 00000000 00000001 01100010

Tämä on aika mukava muoto, jota voisimme hyödyntää, eikö? Haluamme nimittäin funktiossamme tallentaa vain ykkösiä ja nollia, ja nyt juuri havaitsimme, että tavallinen luku ei ole oikeastaan mitään muuta kuin kasa nollia ja ykkösiä (kuten oikeastaan kaikki tietokoneessa…). Bittioperaatioiden avulla voimme siis tallentaa ykkösen niin, että se vie todella vain yhden bitin.

Palataan taulukkoa käyttävään funktioomme. Jos kirjoittaisimme sen uudelleen bittikentille, 24-bittiselle tiivistefunktiolle riittäisi 2²⁴ bitin kokoinen bittikenttä, mikä on 2 MiB. Se on kunnon parannus!

Jos käytämme 32-bittistä tiivistefunktiota, jolla on 2³² eri tulosarvoa, eli 4 294 967 296, tarvitsisimme puoli gigatavua suuruisen bittikentän. Se ei ole ollenkaan hullumpi, kun otetaan huomioon, että sillä pystymme laskemaan uniikkeja jonnekin miljardien suuruusluokkaan asti.

Linear Counting

Mainitsin jo, että tiivistefunktiota käytettäessä saamme vain arvion uniikkien arvojen lukumäärästä. Tämä arvio on sitä epätarkempi, mitä lähempänä uniikkien arvojen lukumäärä on tiivistefunktion eri tulosarvojen lukumäärää. On loogista, että jos meillä on dataryhmä, jossa on viisi miljardia uniikkia arvoa, sitä ei yksinkertaisesti voi laskea 24-bittisellä tiivistefunktiolla.

Tiivistefunktioilla laskettua arviota voi kuitenkin tarkentaa edelleen. Siihen käytetään yksinkertaista ajatusta — mitä enemmän dataryhmässä on uniikkeja arvoja, sitä todennäköisemmin ajan mittaan syntyy törmäyksiä. (Törmäys = kaksi eri syötettä antavat saman tulosteen tiivistefunktiosta, saman tarkistussumman.) Nyt laskemme vähän, joten otamme käyttöön muutaman muuttujan:

• Työskentelemme n-bittisellä tiivistefunktiolla h.
• Funktion h kaikkien mahdollisten tulosteiden lukumäärä on siis 2n. Merkitsemme tämän lukumäärän kirjaimella m, eli: m=2n.
• Bittikenttää, johon tallennamme, mitkä tarkistussummat olemme löytäneet, merkitsemme isolla kirjaimella A. Kentän A pituus on m.
• Kun olemme käyneet algoritmillamme läpi koko dataryhmän, osa bittikentän arvoista on nollia ja osa ykkösiä. Meitä kiinnostaa ennen kaikkea osamäärä ”nollien lukumäärä jaettuna kentän pituudella”, joka kertoo nollien suhteellisen osuuden bittikentässä. Alussa osuus on 1, koska kenttä on alustettu pelkillä nollilla. Jos jakauma olisi fifty-fifty, osuus olisi 1/2 jne. Merkitsemme tätä arvoa Z ja laskemme sen kaavalla Z = nollien lukumäärä / m.

Tällöin pätee, että mitä suurempi arvo Z, sitä varmempia voimme olla siitä, että arviomme uniikkien lukumäärästä on tarkka. Jos esimerkiksi käymme läpi tyhjän dataryhmän, bittikenttään jää pelkkiä nollia ja arvo Z on yksi — meillä on siis täysi varmuus siitä, että dataryhmässämme on niin monta uniikkia alkiota kuin bittikentässä on ykkösiä — nolla.

Jos arvo Z on 0,99, se tarkoittaa, että bittikentästä on ykkösillä täytetty sadasosa. 99 % kentästä sisältää nollia. Se on vielä hyvä, on todennäköistä, ettei laskennan aikana syntynyt kovin paljon törmäyksiä, ja korjausta tarvitaan ehkä ei lainkaan tai vain vähän. Mutta jos arvo Z on 0,05, vain 5 % kentästä jäi nollaksi ja laskennan aikana on todennäköisesti syntynyt hyvin paljon törmäyksiä — tarvitaan suuri korjaus.

Miten korjaus sitten lasketaan? Apuna on logaritmi, eli funktio, jolla on tämä muoto:

Meitä kiinnostaa punainen osa välillä ]0, 1]. Jos merkitsemme x-akselille arvon Z, saamme sen, että mitä suurempi Z, sitä lähemmäs nollaa arvo y tulee. Ja päinvastoin — mitä pienempi Z, sitä pienempi on arvo y. Lopullisen arvion laskemme kertomalla tämän luvun luvulla -m. Huomaa, että riittävän pienelle arvolle Z saamme luvun, joka on jopa pienempi kuin -1, ja kun kerromme tämän arvon luvulla -m, saamme arvion, joka on suurempi kuin m: olemme arvioineet, että uniikkien lukumäärä on suurempi kuin kaikkien mahdollisten tarkistussummien lukumäärä, joita tiivistefunktiosta h voi tulla ulos.

Koko kaava uniikkien arvojen lukumäärän p laskemiseksi näyttäisi tältä:

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

Toteutus (ilman bittikenttiä, vain tavallisilla taulukoilla) voisi näyttää tältä:

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 on tassa luonnollinen logaritmi, kantaluku 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)

Funktiossa linear_counting laskemme ensin ensimmäisen arvion edellisellä algoritmilla, joka käyttää n-bittistä tiivistefunktiota. Sitten laskemme nollien osuuden taulukossa ja teemme korjauksen kaavan mukaan. Koodissa logaritmi on luonnollinen logaritmi. Muuttuja nonunique_values sisältää number_of_unique_values uniikkia merkkijonoa, tässä esimerkissä listassa nonunique_values on siis kymmenentuhatta uniikkia arvoa. Se outo koodi kuudennella rivillä huolehtii siitä, että taulukossa on useita samoja arvoja: yksinkertaisesti liitämme arvolistan loppuun saman listan, ja jokainen arvo on siis taulukossa kahdesti. Ja sitten laskemme. Funktion pitäisi ideaalisesti palauttaa, että lista sisältää kymmenentuhatta uniikkia. Tuloste:

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

Koska nonunique_values-lista generoidaan aina uudelleen, tulokset vaihtelevat jokaisella kutsulla. Käytimme 16-bittistä tiivistefunktiota. Näemme, että funktion count_unique_using_array ensimmäinen arvio oli, että lista sisältää 9 289 uniikkia. Tarkensimme tämän arvion korjauksella lukuun 10 017, mikä on jo aika kelvollinen: arviomme on vain 0,17 % liian suuri, kun taas aiemmin se oli 7,11 % liian pieni — se on aika paljon.

Jos ottaisimme ”suuremman” tiivistefunktion, esimerkiksi 24-bittisen, saisimme tarkemman tuloksen:

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

Jo alkuperäinen arvio oli OK, tarkennus saavutti tasan kymmenentuhatta. Esimerkiksi voimme kokeilla miljoonaa uniikkia tunnistetta, eli number_of_unique_values = 1000000. 24-bittisellä tiivistefunktiolla saamme nämä tulokset:

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

Tuo menee. Ja jos toteutamme sen bittikenttänä, kenttä veisi vain mainitut kaksi megatavua (+ sen, minkä kieli vie). Minusta aika hyvä. But we can do better! Much better. Mutta vasta seuraavalla kerralla.

Sillä välin voit lukea artikkelin A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Tai voit jatkaa sarjan seuraavaan osaan: algoritmi min-value.