Comments on: Le compteur mal connu : l’HyperLogLog

By: Sam

Sam — Wed, 08 Oct 2014 09:40:36 +0000

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.

By: Alex

Alex — Tue, 07 Oct 2014 21:36:54 +0000

Ce ne serait pas une variant du “Bloom filter” ? (Qui est aussi probabiliste et de taille fixe)

By: ONU Inc.

ONU Inc. — Tue, 07 Oct 2014 19:52:45 +0000

>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é.

By: Sam

Sam — Tue, 07 Oct 2014 17:03:03 +0000

@joshuafr: par “fixed”, je veux dire que la coquille est corrigée.

By: Anne O'Nyme

Anne O'Nyme — Tue, 07 Oct 2014 16:13:53 +0000

@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).

By: Sam

Sam — Tue, 07 Oct 2014 16:03:15 +0000

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.

By: joshuafr

joshuafr — Tue, 07 Oct 2014 16:02:12 +0000

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

By: Sam

Sam — Tue, 07 Oct 2014 16:00:45 +0000

@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.

By: Max

Max — Tue, 07 Oct 2014 15:58:56 +0000

le trombone est mort avec l’ancien serveur, paix à son âme, peut être qu’on essayera de le ressusciter. Un jour…

By: Anne O. Nyme

Anne O. Nyme — Tue, 07 Oct 2014 15:46:29 +0000

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.