Linear counting: slik anslår du antall unike verdier

Hvordan kunne vi telle antall unike verdier i en datamengde hvis det var veldig mye data? Vi kan for eksempel ha en tjeneste som måler antall unike brukere på et stort nettsted, eller for den saks skyld på hele .no/.com/.whatever-domenet eller noe slikt.

Den naive framgangsmåten

Ok, det er jo ikke noe å fundere på, vi går bare gjennom dataene og lagrer hver verdi nøyaktig én gang i en passende datastruktur. I Python kunne vi skrevet det omtrent slik (koden er unødvendig ordrik, det er med vilje):

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

Det fungerer. Ja vel, men hva om dataene er unike v4-identifikatorer på 36 tegn, og hva om det er for eksempel ti millioner unike ID-er? Vel… programmet regner fortsatt ut riktig verdi, men hvor mye minne tar det? Vi kan prøve å regne det ut. For enkelhets skyld antar vi at vi virkelig lagrer uuid-en som en streng på 36 tegn. Én uuid tar altså 36 byte, og ti millioner ID-er tar 360 MB.

Det er ikke akkurat lite, la oss innrømme det. Hvis det var hundre millioner unike ID-er, ville vi allerede være oppe i gigabyte med brukt minne. Og da regner vi fortsatt bare det dataene selv tar. Legg til litt overhead som for eksempel Python/JavaScript tar, så kan du komme opp i gigabyte allerede med ti millioner ID-er:

Det vil du ikke ha. Hvordan kommer vi oss ut av dette?

Vi kan prøve å lagre selve ID-ene mer effektivt, vi kan bruke C i stedet for Python, og da reduserer vi minnebehovet vesentlig, men det blir fortsatt ikke helt det, og et slikt program ville fortsatt brukt en enorm mengde plass. Da gjenstår det å stille seg spørsmålet: trenger vi virkelig å vite helt nøyaktig om det er akkurat 9 563 618 unike verdier? Ville det skjedd noe om vi hadde jobbet med tallet 9 547 666? Hvis svaret ditt er at det ville det, og at du vil ha det nøyaktig, så vær så god, gjør som du vil. I motsatt fall kan vi se på framgangsmåter for å anslå antall unike verdier i en datamengde så nøyaktig og raskt som mulig og med minimalt minnebehov.

Hashfunksjoner — redningen vår

Vi tenker oss en hashfunksjon som tar en streng som input og gir et n-bits tall som output. Hvis du er vant til hashfunksjoner som «gir tilbake en streng», kan du bare tenke deg at strengen så blir gjort om til et tall, det er ikke noe mer med det. Antall bits sier hvor stort tallet er. En 8-bits funksjon gir et tall som tar opp åtte bits, og i åtte bits kan vi lagre 2⁸ ulike verdier, typisk heltallene fra 0 til 255. Videre kommer vi til å jobbe med en 24-bits hashfunksjon. En slik funksjon gir 2²⁴ ulike verdier, altså 16 777 216.

I stedet for å lagre selve verdiene lagrer vi 24-bits hashene deres. For å lagre ti millioner 24-bits hasher trenger vi 30 MB. Det er en størrelsesorden bedre enn de forrige 360 MB. Koden kunne se slik ut:

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

Funksjonen hash er en innebygd funksjon i Python og gir et heltall, og funksjonen nhash viser en naiv implementasjon av en n-bits hashfunksjon; det er ikke viktig å forstå hvordan den virker, for den virker ikke riktig likevel — resultatet av den funksjonen tar ikke opp 24 bits, men det spiller ingen rolle nå, det er prinsippet jeg er ute etter.

Så kommer funksjonen count_unique_using_nhash, som teller unike verdier. Den går gjennom alle verdiene, regner ut hashen deres og lagrer den i variabelen found hvis den verdien ikke allerede er der.

Problemet med denne framgangsmåten er at hashfunksjonen kan gi den samme sjekksummen for ulike strenger — det kan oppstå en kollisjon. Jo flere slike kollisjoner som oppstår, jo mer unøyaktig blir resultatet. Funksjonen count_unique_using_nhash gir nesten alltid et mindre antall unike verdier enn det som faktisk finnes.

Og hvilken hashfunksjon skal vi velge? Det spiller ikke så stor rolle, men generelt anbefales en variant av MurmurHash.

Bitmap

Fulgte du med da du lærte å programmere i C? Hvis du gjorde det, kjenner du bitmap. Hvordan kunne vi bruke den?

Vi skisserer ideen med en tabell (array). Vi trenger nemlig ikke å lagre de utregnede sjekksummene, vi kan lage en tabell med lengde 2²⁴ og sette alle elementene til null. Så, i det øyeblikket vi møter en sjekksum — som er et tall! — skriver vi en ener i denne tabellen på indeksen checksum, og slik noterer vi at vi allerede har funnet denne sjekksummen. Antall unike elementer blir da omtrent lik antall enere i tabellen. Koden kunne se slik ut:

def count_unique_using_array(values):
    # liste med lengde 2^24 satt til bare nuller
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Men å bruke en tabell er i dette tilfellet veldig minnekrevende, for i hver celle må vi lagre enten en ener eller en null. I stedet kan vi bruke en bitvektor. For at du skal forstå det: et heltall (integer) kan for eksempel lagres i 32 bits. Når vi gjør tallet 354 om til totallsystemet, får vi 101100010. Tallet 354 ville dermed vært lagret i datamaskinen som et 32-bits heltall slik (vi bryr oss ikke om detaljene, ok?):

00000000 00000000 00000001 01100010

Det er et ganske hyggelig format som vi kunne utnytte, ikke sant? Vi vil nemlig i funksjonen vår bare lagre enere og nuller, og nå fant vi akkurat ut at et vanlig tall egentlig ikke er noe annet enn en haug med nuller og enere (omtrent som alt i en datamaskin…). Kort sagt kan vi ved hjelp av bitvise operatorer lagre en ener slik at den virkelig bare tar opp én bit.

Vi går tilbake til funksjonen vår med tabellen. Hvis vi skrev den om til bitvektor, ville det for en 24-bits hashfunksjon være nok med en bitvektor på 2²⁴ bits, som er 2 MiB. Det er en solid oppgradering!

Ved bruk av en 32-bits hashfunksjon, som har 2³² ulike verdier som output, altså 4 294 967 296, ville vi trengt en bitvektor på en halv gigabyte. Det er ikke så ille, siden vi dermed kan telle unike verdier opp til noen milliarder.

Linear Counting

Jeg har allerede nevnt at vi ved bruk av en hashfunksjon bare får et anslag på antall unike verdier. Dette anslaget blir jo mer unøyaktig, jo nærmere antall unike verdier kommer antall ulike outputverdier fra hashfunksjonen. Det er logisk at hvis vi har en datamengde med fem milliarder unike verdier, kan vi rett og slett ikke telle det med en 24-bits hashfunksjon.

Likevel kan anslaget vi regner ut ved hjelp av hashfunksjoner, gjøres mer nøyaktig. Det brukes en enkel tanke — jo flere unike verdier det er i datamengden, jo mer sannsynlig er det at det etter hvert oppstår kollisjoner. (Kollisjon = to ulike input har samme output fra hashfunksjonen, samme sjekksum.) Nå skal vi regne litt, så vi innfører noen variabler:

• Vi jobber med en n-bits hashfunksjon h.
• Antall mulige outputverdier fra funksjonen h er dermed lik 2n. Dette antallet kaller vi m, altså: m=2n.
• Bitvektoren der vi lagrer hvilke sjekksummer vi har funnet, kaller vi med stor bokstav A. Vektoren A har lengde m.
• Når vi har gått gjennom hele datamengden med algoritmen vår, vil noen verdier i bitvektoren være lik null og noen lik én. Det vi først og fremst er interessert i, er andelen «antall nuller delt på lengden av vektoren», som forteller oss den relative andelen nuller i bitvektoren. I begynnelsen er denne andelen lik 1, for vektoren er fylt med bare nuller. Hvis det var fifty-fifty, ville andelen vært lik en halv osv. Denne verdien kaller vi Z, og vi regner den ut som Z = antall nuller / m.

Nå gjelder det at jo høyere verdi Z har, jo større sikkerhet har vi for at anslaget vårt på antall unike verdier er nøyaktig. Hvis vi for eksempel går gjennom en tom datamengde, blir det bare nuller i bitvektoren, og verdien Z blir lik én — da har vi full sikkerhet for at det i datamengden vår er like mange unike elementer som det er enere i bitvektoren — null.

Hvis verdien Z er lik 0,99, betyr det at en hundredel av bitvektoren er fylt med enere. 99 % av vektoren inneholder nuller. Det er fortsatt bra, det er sannsynlig at det ikke oppsto for mange kollisjoner under utregningen, og at det trengs ingen eller bare en minimal korreksjon. Men hvis verdien Z er lik 0,05, er bare 5 % av vektoren fortsatt null, og vi har sannsynligvis støtt på mange, mange kollisjoner under utregningen — da trengs en stor korreksjon.

Men hvordan regner vi ut denne korreksjonen? Vi bruker logaritmen, som er en funksjon med denne formen:

Vi er interessert i den røde delen på intervallet ⟨0, 1]. Hvis vi setter verdien Z av på x-aksen, oppnår vi at jo høyere Z, jo mer nærmer verdien y seg null. Og omvendt — jo mindre Z, jo mindre blir verdien y. Det endelige anslaget regner vi ut ved å multiplisere dette tallet med -m. Legg merke til at vi for en tilstrekkelig lav verdi av Z får et tall som til og med er mindre enn -1, og når vi multipliserer denne verdien med -m, får vi et anslag som er større enn m: vi har anslått at antall unike verdier er større enn antall alle mulige sjekksummer som kan komme ut av hashfunksjonen h.

Hele formelen for å regne ut antallet p unike verdier ville se slik ut:

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

Implementasjonen (uten bitvektor, bare med vanlige tabeller) kunne se slik ut:

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 er her den naturlige logaritmen med grunntall 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)

I funksjonen linear_counting regner vi først ut det første anslaget med den forrige algoritmen, som bruker en n-bits hashfunksjon. Deretter regner vi ut andelen nuller i tabellen og gjør korreksjonen etter formelen. Logaritmen i koden er den naturlige logaritmen. Variabelen nonunique_values inneholder number_of_unique_values unike strenger, så i dette eksempelet er det ti tusen unike verdier i listen nonunique_values. Den rare koden på linje seks sørger for at det er flere like verdier i tabellen: vi setter rett og slett den samme listen med verdier på slutten av listen, og dermed finnes hver verdi to ganger. Og så regner vi. Funksjonen bør helst gi svaret at listen inneholder ti tusen unike verdier. Output:

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

Siden det hver gang genereres en ny liste nonunique_values, vil resultatene være forskjellige for hvert kall. Vi brukte en 16-bits hashfunksjon. Vi ser at det første anslaget fra funksjonen count_unique_using_array var at listen inneholder 9289 unike verdier. Dette anslaget gjorde vi mer nøyaktig med korreksjonen til 10 017, og det er ganske bra: anslaget vårt er bare 0,17 % for stort, mens det tidligere var 7,11 % for lite — og det er ganske mye.

Hvis vi tok en «større» hashfunksjon, for eksempel en 24-bits, ville vi fått et mer nøyaktig resultat:

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

Selve det opprinnelige anslaget var allerede OK, og korreksjonen tok det helt til ti tusen. Som demonstrasjon kan vi prøve en million unike ID-er, altså number_of_unique_values = 1000000. Med en 24-bits hashfunksjon får vi disse resultatene:

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

Det går an. Og hvis vi implementerer det som en bitvektor, ville vektoren bare tatt de nevnte to megabytene (+ det språket selv bruker). Ganske bra, synes jeg. But we can do better! Much better. Men det tar vi neste gang.

I mellomtiden kan du lese artikkelen A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Eller du kan fortsette til neste del i serien: algoritmen min-value.