Comments on: Le compteur mal connu : l’HyperLogLog http://sametmax.com/le-compteur-mal-connu-lhyperloglog/ Du code, du cul Sat, 07 Nov 2015 11:08:18 +0000 hourly 1 http://wordpress.org/?v=4.1 By: Sam http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-145215 Wed, 08 Oct 2014 09:40:36 +0000 http://sametmax.com/?p=12353#comment-145215 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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144943 Tue, 07 Oct 2014 21:36:54 +0000 http://sametmax.com/?p=12353#comment-144943 Ce ne serait pas une variant du “Bloom filter” ? (Qui est aussi probabiliste et de taille fixe)

]]>
By: ONU Inc. http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144884 Tue, 07 Oct 2014 19:52:45 +0000 http://sametmax.com/?p=12353#comment-144884 >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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144791 Tue, 07 Oct 2014 17:03:03 +0000 http://sametmax.com/?p=12353#comment-144791 @joshuafr: par “fixed”, je veux dire que la coquille est corrigée.

]]>
By: Anne O'Nyme http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144766 Tue, 07 Oct 2014 16:13:53 +0000 http://sametmax.com/?p=12353#comment-144766 @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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144764 Tue, 07 Oct 2014 16:03:15 +0000 http://sametmax.com/?p=12353#comment-144764 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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144763 Tue, 07 Oct 2014 16:02:12 +0000 http://sametmax.com/?p=12353#comment-144763 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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144762 Tue, 07 Oct 2014 16:00:45 +0000 http://sametmax.com/?p=12353#comment-144762 @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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144761 Tue, 07 Oct 2014 15:58:56 +0000 http://sametmax.com/?p=12353#comment-144761 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 http://sametmax.com/le-compteur-mal-connu-lhyperloglog/#comment-144757 Tue, 07 Oct 2014 15:46:29 +0000 http://sametmax.com/?p=12353#comment-144757 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.

]]>