Le compteur mal connu : l’HyperLogLog 13

Sam — Tue, 07 Oct 2014 14:02:58 +0000

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

Vous pouvez également profiter de l’HyperLogLog via une extension PostGres ou en utilisant une version récente de Redis.
La plupart des compteurs sur les sites sont complètement bidons, alors vous, honnête que vous êtes, embrassez l’approximatif ! C’est presque la vérité. Presque.

Quelques innovation de Python 3 backportées en Python 2.7 4

Sam — Mon, 05 Nov 2012 11:36:42 +0000

Comme nous l’avons vu avec les vues ou les collections, Python 2.7 vient avec pas mal de bonus issus directement de la branche 3. En voici quelques autres. Tout ceci n’est bien sûr ni nouveau ni exhaustif, mais je m’aperçois que peu de personnes le savent.

Une notation littérale pour les sets:

>>> {1, 2} == set((1, 2))
True

Une syntaxe pour les dictionnaires en intention:

>>> d = {chr(x): x for x in range(65, 91)}
>>> d
{'A': 65, 'C': 67, 'B': 66, 'E': 69, 'D': 68, 'G': 71, 'F': 70, 'I': 73, 'H': 72, 'K': 75, 'J': 74, 'M': 77, 'L': 76, 'O': 79, 'N': 78, 'Q': 81, 'P': 80, 'S': 83, 'R': 82, 'U': 85, 'T': 84, 'W': 87, 'V': 86, 'Y': 89, 'X': 88, 'Z': 90}

Imbriquer with:

Avant il fallait utiliser nested() ou imbriquer à la main

with open('fichiera') as a:
    with open('fichiera') as b:
        # faire un truc

Maintenant on peut faire:

with open('fichiera') as a, open('fichiera') as b:
    # faire un truc

Rien à voir, mais toujours sympa. timedelta a maintenant une méthode total_seconds() qui retourne la valeur de la durée en seconde. En effet, l’attribut seconds ne retourne que ce qui reste en seconde une fois qu’on a retiré les jours:

>>> from datetime import timedelta
>>> delta = timedelta(days=1, seconds=1)
>>> delta.seconds
1
>>> delta.total_seconds()
86401.0

Notez qu’il n’y a toujours ni attribut minutes, ni heures.

Le module unittest gagne une pléthore d’améliorations, et notamment:

L’utilisation de assertRaises comme context manager:

with self.assertRaises(KeyError):
    {}['foo']

Et un bon gros nombres de méthodes:

assertIsNone() / assertIsNotNone(), assertIs() / assertIsNot(), assertIsInstance() / assertNotIsInstance(), assertGreater() / assertGreaterEqual() / assertLess() / assertLessEqual(), assertRegexpMatches() / assertNotRegexpMatches(), assertRaisesRegexp(),
assertIn() / assertNotIn(), assertDictContainsSubset(), assertAlmostEqual() / assertNotAlmostEqual().

Enfin format() commence à devenir une alternative valable à % car il propose maintenant des marqueurs sans noter d’index:

>>> "{}, puis {} et finalement {}".format(*range(3))
'0, puis 1 et finalement 2'

Et il ajoute le séparateur des milliers au mini-langage de formatage, mais pour la virgule uniquement. Par exemple, si avoir un nombre de 15 caractères minimum formater en tant que float, avec deux chiffres après la virgules, et donc les milliers sont groupés à l’américaine:

>>> '{:15,.2f}'.format(54321)
'      54,321.00'

Sam & Max » sets

Le compteur mal connu : l’HyperLogLog 13

Quelques innovation de Python 3 backportées en Python 2.7 4