¿Cómo contar el número de elementos distintos de una lista?

El problema es sencillo: se cuentan y ya.

Pero hay quienes tienen cantidades ingentes de elementos que contar. Tantos que por razones de memoria, etc., es inviable hacer lo obvio, es decir, guardar una lista de claves (elementos distintos) y valores (el número de ocurrencias) sumando uno a los últimos cada vez que ocurra una de las primeras.

Por ese motivo, existen algoritmos que aproximan el número de elementos distintos de una lista. Existe, de hecho, toda una industria dedicada a crear tal tipo de algoritmos.

Veamos una versión simplificada de uno de ellos. A cada elemento se le calcula un hash. Un hash es una función no continua. Por ejemplo, como esta:

carlos@chino:~$ echo "hola" | md5sum
916f4c31aaa35d6b867dae9a7f54270d

Convierte la cadena "hola" en un número (en hexadecimal), el que aparece arriba. Si se escribe en binario, se puede contar el número de ceros con el que principia.

Si hubiese muchos elementos distintos y se calculase el número de ceros con el que comienza el hash de cada uno de ellos aumentaría la probabilidad de que hubiese más y más. Si el número máximo de ceros es pequeño, el número de elementos distintos será, probablemente, pequeño. Si es grande, es probable que el número de ceros máximo al principio de la cadena sea mayor.

Con eso y un poquito más, se tiene HyperLogLog. Aquí se lo puede ver en funcionamiento.

(Nota: el poquito más es un truco para tener varios máximos en lugar de solo uno y poder afinar la predicción).

(Otra nota: en el artículo en el que se publicó el algoritmo no dice likelihood en ninguna parte. ¡Raro!)