Non, ce n’est pas une faute de frappe. l’HyperLogLog est un algo qui permet de compter approximativement des éléments uniques en prenant très peu de mémoire.
Prenez par exemple un compteur d’IP uniques. En Python, on l’implémenterait en mettant les adresses IP dans un set() (puisqu’ils éliminent les doublons) et pour obtenir le nombre d’IP uniques, on ferait len() sur le set.
Une bonne stratégie, performante (les sets sont très rapides pour ce genre d’usage), simple, mais avec un défaut : la taille du set ne va cesser d’augmenter au fur et à mesure qu’on le remplit d’IP puisqu’il nous faut l’historique de toutes celles rencontrées pour éviter les doublons.
L’HyperLogLog répond à cette problématique : il tient un journal probabiliste qui va se remplir au fur et à mesure qu’on rencontre des nouveaus éléments. On peut ensuite demander au journal combien d’éléments uniques il a rencontré, et il répond avec une marge d’erreur.
Avantage : la taille en mémoire est fixe.
Désavantage : le compteur n’est pas parfaitement précis.
La précision obtenue est dépendante de la place en mémoire, par exemple si on on tolère 1% d’erreur, le journal prendra au maximum 12kb, permettant de compter jusqu’à 2^64 items.
Bref, si vous faites juste un compteur à afficher en pied de page de votre site, c’est un très bon compromis. On peut accepter d’avoir un peu plus ou un peu moins de visiteurs que la réalité qui s’affiche, sachant que la stat elle-même n’est pas vraiment réprésentative de la réalité (IP != de visiteurs uniques).
En Python, il existe une lib (uniquement 2.7 il me semble) pour ça :
>>> import hyperloglog, random >>> hll = hyperloglog.HyperLogLog(0.01) # on accepte une erreur de 1% >>> hll.add("119.250.66.95") >>> print len(hll) 1 >>> hll.add("119.250.66.95") >>> print len(hll) 1 >>> hll.add("219.81.118.147") >>> print len(hll) 2 >>> for x in xrange(1000): ... ip = ".".join(str(random.randint(1, 255)) for x in range(4)) ... print ip ... hll.add(ip) 114.208.49.91 11.72.239.16 67.56.229.66 191.62.59.163 61.104.232.43 110.58.69.141 246.123.30.234 244.246.65.219 98.93.193.114 185.143.143.69 191.177.161.213 ... >>> print len(hll) # 1000 items unique. Environ :) 1004 |
>>> print len(hll) # 1000 items unique. Environ :)
10004
–> Du coup ça devrait être 1004 non ?
Excusez moi mais, qu’es que putain de quoi ? oO
C’est quoi un “journal probabiliste” et comment ça le journal “répond avec une marge d’erreur” ?
L’informatique c’est le domaine du déterminisme et de l’exactitude par excellence.
Alors il marche comment ce module pifométrique ?
Question subsidiaire, ou est passé le trombone ='(
Cordialement
@PocketTiger
Lis le principe de l’algorithme (mal documenté sur wiki certes), il utilise une fonction de hachage appliquée aux entrées pour simuler l’aléatoire, c’est franchement pas compliqué. Pour en savoir plus : http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/
L’idée c’est d’estimer une approximation. Par exemple, on te donne plein de nombres, tu regarde leur max, et tu regardes où se trouve le premier 1 (en binaire hein). Forcément, si ton entier le plus grand est du genre 11111111 (255 en décimal) bah tu ne peux pas avoir plus de 255 nombres. Et si le min est du genre 00001011 (11 en décimal) bah tu ne peux avoir que les nombres entre 11 et 255, soit 244 nombres. Ces valeurs (min, max, etc.) sont des observables qui sont faciles à calculer (à peu de choses près, vu qu’on n’a pas forcément besoin du plus petit ou plus grand entier pour avoir une borne sup ou inf) et on en déduit un comptage approximatif du nombre d’éléments.
Bon en fait c’est beaucoup plus compliqué que ça. Ils séparent les flux d’entrées et prennent la moyenne harmonique de chaque résultat obtenu, je saurais pas dire pourquoi sans avoir lu tout le papier (http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf), je risquerais de dire des conneries. Et pour générer de l’aléatoire, ils utilisent une fonction de hachage qu’ils appliquent aux nombres en entrée.
le trombone est mort avec l’ancien serveur, paix à son âme, peut être qu’on essayera de le ressusciter. Un jour…
@Rob: tout à fait. Fixed.
@PocketTiger: J’ai même plus besoin de répondre, le blog tourne tout seul :) Le trombonne est sur l’ancien thême du blog.
Euh, si print len(hll) répond 10004 au lieu d’environ 1000, là y’a plus qu’1% d’erreur… ou alors il y a un zéro de trop ;-)
Je pense que MySQL s’en sert aussi pour compter le nombre de lignes dans ses tables, du moins avec sqlyog
Après j’irais pas jusqu’à dire que l’implémentation “c’est franchement pas compliqué”. Parce que moi je connais plein de matheux qui trouvent que faire un gratin dauphinois c’est compliqué alors que je trouve ça très simple. Donc je suppose que c’est aussi compliqué que le gratin dauphinois pour quelqu’un qui sait faire des pates.
@Sam
Je parlais de la simulation de l’aléatoire, pas de l’implémentation elle-même (qui elle prend 20 pages à expliquer et justifier). Cela dit je ne suis pas un matheux pur et je ne vois rien de franchement insurmontable dans le papier, même si c’est sûr que ça prend du temps à digérer (comme le gratin dauphinois).
@joshuafr: par “fixed”, je veux dire que la coquille est corrigée.
>En Python, il existe une lib pour ça
Combien de fois n’ai-je pas entendu cette remarque bandante dont la simplicité même fait la force de Python… Manquerait plus qu’une lib qui suce ou qui fait le café.
Ce ne serait pas une variant du “Bloom filter” ? (Qui est aussi probabiliste et de taille fixe)
C’est un principe cousin mais le bloom filter permet de savoir si un élément fait partie du set, tandis que l’hyperloglog permet de savoir combien d’éléments uniques ont été ajoutés au set. Donc pas exactement le même usage.