Linear counting: come stimare il numero di valori distinti

Come potremmo contare i valori distinti in un insieme di dati, se i dati sono davvero moltissimi? Potremmo avere, per esempio, un servizio che misura il numero di utenti unici di un grande sito web, o magari di un intero dominio .it/.com/.whatever o giù di lì.

L’approccio ingenuo

Ok, non c’è niente da discutere: scorriamo i dati e salviamo ogni valore esattamente una volta in una struttura dati adatta. In Python potremmo scriverlo più o meno così (il codice è inutilmente prolisso, ma è voluto):

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

Funziona. Va bene, ma cosa succede se i dati sono identificatori univoci uuid v4 di 36 caratteri e di questi identificatori distinti ce ne sono, poniamo, dieci milioni? Beh… il programma calcola comunque il valore corretto, ma quanta memoria occupa? Proviamo a calcolarlo. Per semplicità supponiamo di salvare gli uuid davvero come stringhe di 36 caratteri. Un uuid occupa quindi 36 byte e dieci milioni di identificatori occupano 360 MB.

Non è proprio poco, ammettiamolo. Se gli identificatori distinti fossero cento milioni, arriveremmo già all’ordine dei gigabyte di memoria occupata. E stiamo ancora contando solo lo spazio occupato dai dati. Aggiungi l’overhead di Python/JavaScript e puoi arrivare all’ordine dei gigabyte anche con dieci milioni di identificatori:

Non è quello che vuoi. Come uscirne?

Possiamo provare a salvare in modo più efficiente gli identificatori stessi, possiamo usare il C al posto di Python, riducendo drasticamente il consumo di memoria, ma non sarà ancora la soluzione giusta e un programma del genere occuperebbe comunque una quantità incredibile di spazio. Resta da chiedersi: ci serve davvero sapere con esattezza assoluta se i valori distinti sono proprio 9.563.618? Cambierebbe qualcosa se lavorassimo con 9.547.666? Se la tua risposta è che cambierebbe e che vuoi il valore esatto, allora prego, accomodati. Altrimenti vediamo come stimare il numero di valori distinti in un insieme di dati nel modo più preciso e veloce possibile e con un uso minimo di memoria.

Le funzioni di hash: la nostra salvezza

Consideriamo una funzione di hash che riceve in ingresso una stringa e restituisce un numero a n bit. Se sei abituato alle funzioni di hash che «restituiscono una stringa», immagina semplicemente che questa stringa venga poi convertita in un numero: non c’è niente di complicato. Il numero di bit indica quanto è grande il numero. Una funzione a 8 bit restituisce un numero che occupa otto bit e in otto bit si possono salvare 2⁸ valori diversi, in genere i numeri interi da 0 a 255. D’ora in poi lavoreremo con una funzione di hash a 24 bit. Una funzione del genere restituisce 2²⁴ valori diversi, cioè 16.777.216.

Invece di salvare i valori stessi, salveremo i loro hash a 24 bit. Per salvare dieci milioni di hash a 24 bit servono 30 MB. È di un ordine di grandezza meglio dei 360 MB di prima. Il codice potrebbe essere così:

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

La funzione hash è una funzione nativa di Python e restituisce un numero intero, mentre nhash mostra un’implementazione ingenua di una funzione di hash a n bit; non è importante capire come funzioni, perché comunque non funziona correttamente (il risultato non occupa 24 bit), ma non importa: mi interessa il principio.

Segue la funzione count_unique_using_nhash, che conta i valori distinti. Scorre tutti i valori, ne calcola l’hash e lo salva nella variabile found, se quel valore non c’è già.

Il problema di questo approccio è che la funzione di hash può restituire lo stesso checksum per stringhe diverse: può verificarsi una collisione. Più collisioni si verificano, più il risultato è impreciso. La funzione count_unique_using_nhash restituisce quasi sempre un numero di valori distinti inferiore a quello reale.

E quale funzione di hash scegliere? In fondo non conta molto, ma in generale si consiglia una variante di MurmurHash.

Bitmap

Hai fatto attenzione ai corsi di fondamenti di programmazione in C? Se sì, conosci le bitmap. Come potremmo usarle?

Illustriamo l’idea con un array. Non siamo costretti a conservare i checksum calcolati: possiamo creare un array di lunghezza 2²⁴ e inizializzare tutti gli elementi a zero. Poi, ogni volta che incontriamo un checksum – che è un numero! – scriviamo un uno nell’array all’indice checksum, segnando così che quel checksum l’abbiamo già trovato. Il numero di elementi distinti sarà allora circa uguale al numero di uni presenti nell’array. Il codice potrebbe essere così:

def count_unique_using_array(values):
    # lista di lunghezza 2^24 inizializzata con tutti zeri
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Tuttavia, usare un array è in questo caso molto costoso in termini di memoria, perché in ogni cella dobbiamo salvare ogni volta o un uno o uno zero. Possiamo invece usare un array di bit. Per capirci, un numero intero (integer) si può salvare, per esempio, in 32 bit. Se convertiamo il numero 354 in binario, otteniamo 101100010. Il numero 354 sarebbe quindi salvato nel computer come integer a 32 bit così (lasciamo perdere i dettagli, ok?):

00000000 00000000 00000001 01100010

È un formato piuttosto comodo, che potremmo sfruttare, no? Nella nostra funzione vogliamo salvare soltanto uni e zeri e abbiamo appena scoperto che un numero qualsiasi non è altro che un mucchio di zeri e uni (come tutto, del resto, nel computer…). Insomma, con gli operatori bit a bit possiamo salvare un uno in modo che occupi davvero un solo bit.

Torniamo alla nostra funzione con l’array. Se la riscrivessimo con i array di bit, per una funzione di hash a 24 bit ci basterebbe un array di bit di 2²⁴ bit, cioè 2 MiB. Un bel miglioramento!

Con una funzione di hash a 32 bit, che ha 2³² valori di uscita diversi, cioè 4.294.967.296, ci servirebbe un array di bit di mezzo giga. Non è affatto male, visto che così riusciamo a contare i valori distinti fino all’ordine dei miliardi.

Linear counting

Ho già detto che usando una funzione di hash otteniamo solo una stima del numero di valori distinti. Questa stima è tanto più imprecisa quanto più il numero di valori distinti si avvicina al numero di valori di uscita possibili della funzione di hash. È logico che, se in un insieme di dati ci sono cinque miliardi di valori distinti, con una funzione di hash a 24 bit non riusciremo semplicemente a contarli.

Tuttavia la stima che otteniamo con le funzioni di hash si può ulteriormente affinare. Si usa un’idea semplice: più valori distinti ci sono nell’insieme di dati, più è probabile che col tempo si verifichino collisioni. (Collisione = due ingressi diversi hanno la stessa uscita della funzione di hash, lo stesso checksum.) Ora faremo qualche calcolo, quindi introduciamo alcune variabili:

• Lavoreremo con una funzione di hash h a n bit.
• Il numero di tutte le possibili uscite della funzione h è quindi 2n. Indichiamo questo numero con la lettera m, cioè: m=2n.
• L’array di bit in cui salveremo quali checksum abbiamo trovato lo indichiamo con la lettera maiuscola A. L’array A ha lunghezza m.
• Dopo aver scorso con il nostro algoritmo tutto l’insieme di dati, alcuni valori nell’array di bit saranno uguali a zero e altri a uno. Ci interessa soprattutto il rapporto «numero di zeri diviso lunghezza dell’array», che dà la frazione relativa di zeri nell’array di bit. All’inizio questo rapporto è uguale a 1, perché l’array è inizializzato con tutti zeri. Se fosse fifty-fifty, il rapporto sarebbe uguale a un mezzo, e così via. Indichiamo questo valore con Z e lo calcoliamo come Z = numero di zeri / m.

A questo punto vale che, quanto più alto è il valore di Z, tanto maggiore è la certezza che la nostra stima del numero di valori distinti sia precisa. Se, per esempio, scorriamo un insieme di dati vuoto, nell’array di bit resteranno solo zeri e il valore di Z sarà uguale a uno: abbiamo quindi la certezza assoluta che nel nostro insieme di dati ci siano tanti valori distinti quanti sono gli uni nell’array di bit, cioè zero.

Se il valore di Z è uguale a 0,99, significa che l’array di bit è riempito di uni per un centesimo. Il 99% dell’array contiene zeri. Va ancora bene: è probabile che durante il calcolo non si siano verificate troppe collisioni e che serva forse nessuna correzione, o una minima. Ma se il valore di Z è uguale a 0,05, solo il 5% dell’array è rimasto a zero e probabilmente durante il calcolo abbiamo incontrato moltissime collisioni: servirà una correzione importante.

Ma come calcolare questa correzione? Ci aiuta il logaritmo, una funzione che ha questo grafico:

Ci interessa la parte rossa nell’intervallo (0; 1]. Se riportiamo sull’asse x il valore di Z, otteniamo che, quanto più alto è Z, tanto più il valore di y si avvicina a zero. E viceversa: quanto più piccolo è Z, tanto più piccolo sarà il valore di y. La stima finale si calcola moltiplicando questo numero per -m. Osserva che, per un valore di Z sufficientemente basso, otteniamo un numero addirittura minore di -1 e, moltiplicando questo valore per -m, otteniamo una stima maggiore di m: abbiamo stimato che il numero di valori distinti sia maggiore del numero di tutti i possibili checksum che possono uscire dalla funzione di hash h.

L’intera formula per calcolare il numero p di valori distinti sarebbe questa:

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

L’implementazione (senza array di bit, solo con array normali) potrebbe essere questa:

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 qui è il logaritmo naturale in base 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)

Nella funzione linear_counting calcoliamo prima la stima iniziale con l’algoritmo precedente, che usa una funzione di hash a n bit. Poi calcoliamo la frazione di zeri nell’array e applichiamo la correzione secondo la formula. Il logaritmo nel codice è il logaritmo naturale. La variabile nonunique_values contiene number_of_unique_values stringhe distinte; in questo esempio la lista nonunique_values contiene quindi diecimila valori distinti. Quello strano codice alla sesta riga fa sì che nella lista ci siano più valori uguali: basta aggiungere in fondo alla lista la stessa lista di valori, così ogni valore compare due volte. E poi si calcola. Idealmente la funzione dovrebbe restituire che la lista contiene diecimila valori distinti. Output:

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

Poiché a ogni esecuzione si genera una lista nonunique_values diversa, i risultati cambieranno a ogni chiamata. Abbiamo usato una funzione di hash a 16 bit. Vediamo che la prima stima della funzione count_unique_using_array era che la lista contenesse 9289 valori distinti. Con la correzione abbiamo affinato la stima a 10.017, che è già piuttosto buona: la nostra stima è maggiore del valore reale solo dello 0,17%, mentre prima era minore del 7,11%, il che è parecchio.

Se prendessimo una funzione di hash «più grande», per esempio a 24 bit, otterremmo un risultato più preciso:

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

Già la stima originale era OK, la correzione ci ha portati a diecimila tondi. Per dimostrazione possiamo provare con un milione di identificatori distinti, cioè number_of_unique_values = 1000000. Con una funzione di hash a 24 bit otteniamo questi risultati:

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

Niente male. E se lo implementiamo come array di bit, occuperebbe soltanto i due megabyte citati (+ quello che occupa il linguaggio). Per me è piuttosto buono. But we can do better! Much better. Ma alla prossima volta.

Nel frattempo puoi leggere l’articolo A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Oppure puoi passare alla puntata successiva della serie: l’algoritmo Min Value.