Linear counting: como estimar o número de valores distintos

Como poderíamos contar o número de valores distintos em algum conjunto de dados, se esses dados fossem realmente muitos? Podemos ter, por exemplo, um serviço que mede o número de usuários únicos em algum site grande ou até em todo o domínio .br/.com/.whatever ou algo assim.

O método ingênuo

Ok, não tem o que discutir: simplesmente percorremos os dados e guardamos cada valor exatamente uma vez em alguma estrutura de dados adequada. Em Python, poderíamos escrever mais ou menos assim (o código é desnecessariamente prolixo, de propósito):

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

Funciona. Tudo bem, mas e se os dados forem identificadores únicos v4 de 36 caracteres e se houver, digamos, dez milhões desses IDs únicos? Bom… o programa continua calculando o valor correto, mas quanta memória ele ocupa? Podemos tentar calcular. Para simplificar, vamos supor que guardamos o uuid realmente como uma string de 36 caracteres. Um uuid ocupa, assim, 36 bytes, e dez milhões de IDs ocupam 360 MB.

Não é pouco, vamos admitir. Se os IDs únicos fossem cem milhões, já estaríamos na casa dos gigabytes de memória ocupada. E isso contando apenas o que os dados ocupam. Acrescente algum overhead que o Python/JavaScript ocupa, e você pode chegar à casa dos gigabytes mesmo com dez milhões de IDs:

Você não quer isso. Como sair dessa?

Podemos tentar guardar os próprios IDs de forma mais eficiente, podemos usar C em vez de Python, o que reduziria bastante o consumo de memória, mas mesmo assim ainda não seria o ideal, e um programa desses ainda ocuparia uma quantidade absurda de espaço. Resta fazer a pergunta: será que realmente precisamos saber com exatidão se o número de valores distintos é exatamente 9.563.618? Aconteceria alguma coisa se trabalhássemos com 9.547.666? Se a sua resposta é que sim, que aconteceria, e que você quer o valor exato, então fique à vontade. Caso contrário, vamos mostrar métodos para estimar o número de valores distintos em um conjunto de dados da forma mais precisa e rápida possível e com o mínimo de memória.

Funções hash — a nossa salvação

Vamos considerar uma função hash que recebe uma string na entrada e devolve na saída um número de n bits. Se você está mais acostumado com funções hash que “devolvem uma string”, imagine simplesmente que essa string é depois convertida em número, não há nenhum segredo nisso. O número de bits indica o tamanho do número. Uma função de 8 bits devolve um número que ocupa oito bits, e em oito bits cabem 2⁸ valores diferentes, tipicamente os números inteiros de 0 a 255. Daqui em diante vamos trabalhar com uma função hash de 24 bits. Uma função assim devolve 2²⁴ valores diferentes, ou seja, 16.777.216.

Em vez de guardar os próprios valores, vamos guardar seus hashes de 24 bits. Para guardar dez milhões de hashes de 24 bits, precisamos de 30 MB. É uma ordem de grandeza melhor do que os 360 MB anteriores. O código poderia ser assim:

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 função hash é uma função nativa do Python e devolve um número inteiro; a função nhash mostra uma implementação ingênua de uma função hash de n bits; não é importante entender como ela funciona, porque de qualquer forma ela não funciona corretamente — o resultado dessa função não ocupa 24 bits, mas isso agora não importa, o que me interessa é o princípio.

Depois vem a função count_unique_using_nhash, que conta os valores distintos. Ela percorre todos os valores, calcula o hash de cada um e o guarda na variável found, se esse valor ainda não estiver lá.

O problema desse método é que a função hash pode devolver o mesmo checksum para strings diferentes — pode ocorrer uma colisão. Quanto mais colisões ocorrem, mais impreciso é o resultado que obtemos. A função count_unique_using_nhash quase sempre devolve um número de valores distintos menor do que o que realmente existe.

E qual função hash escolher? Não importa tanto assim, mas em geral se recomenda alguma variante do MurmurHash.

Mapas de bits

Você prestou atenção nas aulas de introdução à programação em C? Se sim, conhece os mapas de bits. Como poderíamos aproveitá-los?

Vamos esboçar a ideia com um vetor. Na verdade, não precisamos guardar os checksums calculados; podemos criar um vetor de comprimento 2²⁴ e inicializar todos os elementos com zero. Então, no momento em que encontramos algum checksum — que é um número! — escrevemos 1 nesse vetor, no índice checksum, marcando assim que esse checksum já foi encontrado. O número de elementos distintos será, então, aproximadamente igual ao número de uns nesse vetor. O código poderia ser assim:

def count_unique_using_array(values):
    # lista de comprimento 2^24 inicializada com zeros
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

No entanto, usar um vetor é, nesse caso, muito custoso em memória, porque em cada célula precisamos guardar sempre um 1 ou um 0. Em vez disso, podemos usar um vetor de bits. Para você entender: um número inteiro (integer) pode ser guardado, por exemplo, em 32 bits. Se convertermos o número 354 para o sistema binário, obtemos 101100010. O número 354 ficaria, então, guardado no computador como um inteiro de 32 bits (deixemos os detalhes de lado, tá?) assim:

00000000 00000000 00000001 01100010

É um formato bem agradável, que poderíamos aproveitar, não é? Na nossa função queremos guardar apenas uns e zeros, e acabamos de descobrir que um número comum não é nada além de um monte de zeros e uns (assim como tudo no computador…). Ou seja, por meio de operações bit a bit podemos guardar um 1 de modo que ele ocupe realmente um único bit.

Voltemos à nossa função com o vetor. Se a reescrevêssemos com vetores de bits, para uma função hash de 24 bits nos bastaria um vetor de bits de tamanho 2²⁴ bits, que são 2 MiB. Isso é uma melhoria e tanto!

Com uma função hash de 32 bits, que tem 2³² valores de saída diferentes, ou seja, 4.294.967.296, precisaríamos de um vetor de bits de meio giga. Não é nada mal, já que com isso conseguimos contar valores distintos até a casa dos bilhões.

Linear Counting

Já mencionei que, ao usar uma função hash, obtemos apenas uma estimativa do número de valores distintos. Essa estimativa é tanto mais imprecisa quanto mais o número de valores distintos se aproxima do número de valores de saída diferentes da função hash. É lógico que, se temos um conjunto de dados com cinco bilhões de valores distintos, simplesmente não vamos conseguir contá-los com uma função hash de 24 bits.

No entanto, a estimativa que calculamos por meio de funções hash pode ser refinada. Usa-se para isso uma ideia simples — quanto mais valores distintos há no conjunto de dados, mais provável é que, com o tempo, surjam colisões. (Colisão = duas entradas diferentes têm a mesma saída da função hash, o mesmo checksum.) Agora vamos fazer algumas contas, então vamos introduzir algumas variáveis:

• Vamos trabalhar com uma função hash h de n bits.
• O número de todas as saídas possíveis da função h é, assim, igual a 2n. Vamos denotar esse número pela letra m, ou seja: m=2n.
• O vetor de bits em que vamos guardar quais checksums encontramos será denotado pela letra maiúscula A. O vetor A tem comprimento m.
• Depois de percorrermos todo o conjunto de dados com o nosso algoritmo, alguns valores do vetor de bits serão iguais a zero e outros, a um. O que vai nos interessar principalmente é a razão “número de zeros dividido pelo comprimento do vetor”, que nos dá a proporção relativa de zeros no vetor de bits. No começo essa razão é igual a 1, porque o vetor é inicializado só com zeros. Se fosse meio a meio, a razão seria igual a um meio etc. Vamos denotar esse valor por Z e calculá-lo como Z = número de zeros / m.

Neste ponto, vale que, quanto maior o valor de Z, maior a certeza de que a nossa estimativa do número de valores distintos é precisa. Se, por exemplo, percorrermos um conjunto de dados vazio, no vetor de bits ficarão só zeros e o valor de Z será igual a um — teremos, assim, plena certeza de que no nosso conjunto de dados há tantos elementos distintos quantos uns há no vetor de bits — zero.

Se o valor de Z é igual a 0,99, isso significa que um centésimo do vetor de bits está preenchido com uns. 99% do vetor contém zeros. Isso ainda é bom, é provável que durante o cálculo não tenham ocorrido colisões demais e talvez não seja necessária nenhuma correção, ou só uma mínima. Mas, se o valor de Z é igual a 0,05, apenas 5% do vetor permaneceram zerados e provavelmente, durante o cálculo, esbarramos em muitas e muitas colisões — será necessária uma grande correção.

Mas como calcular essa correção? Vamos recorrer ao logaritmo, que é uma função que tem esta forma:

O que nos interessa é aquela parte vermelha no intervalo ]0, 1]. Se marcarmos no eixo x o valor de Z, conseguimos que, quanto maior o Z, mais o valor de y se aproxima de zero. E, ao contrário, quanto menor o Z, menor será o valor de y. Calculamos a estimativa final multiplicando esse número por -m. Observe que, para um valor de Z suficientemente baixo, obtemos um número que é até menor do que -1, e, se multiplicarmos esse valor por -m, obtemos uma estimativa maior do que m: estimamos que o número de valores distintos é maior do que o número de todos os checksums possíveis que podem sair da função hash h.

A fórmula completa para calcular o número p de valores distintos seria esta:

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

A implementação (sem vetores de bits, apenas com vetores comuns) poderia ser assim:

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 aqui e o logaritmo natural, de 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)

Na função linear_counting, primeiro calculamos a primeira estimativa com o algoritmo anterior, que usa uma função hash de n bits. Depois calculamos a proporção de zeros no vetor e fazemos a correção segundo a fórmula. O logaritmo no código é o logaritmo natural. A variável nonunique_values contém number_of_unique_values strings distintas; neste exemplo, portanto, na lista nonunique_values há dez mil valores distintos. Aquele código estranho na sexta linha faz com que no vetor haja mais valores iguais: simplesmente anexamos ao final da lista a mesma lista de valores, e cada valor fica, assim, duas vezes no vetor. E depois é só calcular. O ideal é que a função devolva que a lista contém dez mil valores distintos. Saída:

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

Como sempre é gerada uma lista nonunique_values diferente, os resultados vão variar a cada chamada. Usamos uma função hash de 16 bits. Vemos que a primeira estimativa da função count_unique_using_array foi de que a lista contém 9.289 valores distintos. Refinamos essa estimativa com a correção para 10.017, o que já é bem razoável: a nossa estimativa é maior apenas em 0,17%, enquanto antes era menor em 7,11% — o que é bastante.

Se pegássemos uma função hash “maior”, por exemplo de 24 bits, obteríamos um resultado mais preciso:

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

A própria estimativa original já estava OK, e o refinamento chegou a exatos dez mil. Para demonstrar, podemos tentar um milhão de IDs distintos, isto é, number_of_unique_values = 1000000. Com uma função hash de 24 bits, chegamos a estes resultados:

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

Dá pro gasto. E, se implementarmos isso como vetor de bits, o vetor deveria devorar apenas os dois megabytes mencionados (+ o que a linguagem devorar). Para mim, bem razoável. But we can do better! Much better. Mas só da próxima vez.

Enquanto isso, você pode ler o artigo A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Ou pode seguir para a próxima parte da série: algoritmo min-value.