Sam & Max: Python, Django, Git et du cul » dict

Mesurer les performances d’un snippet Python

Sam — Sat, 08 Jun 2013 20:20:52 +0000

Ca fait longtemps que j’avais pas musique.

L’open source c’est fantastique. Github c’est merveilleux. On parle de batbelt, et paf, quelques jours plus tard on a notre première contribution.

Ce qui est sympa avec cette lib, c’est que ce sont des fonctions simples et courtes, axées sur des tâches très précises. Le code est donc généralement intéressant à lire, mais pas trop compliqué, et on tombe souvent sur des cas d’école.

C’est le cas de cette modification de la fonction dmerge(). Originalement, dmerge permet de créer un dictionnaire à partir de la fusion de de 2 autres dicos, et ça marchait comme ça:

def dmerge(d1, d2):
    d = {}
    d.update(d1)
    d.update(d2)
    return d

Facile à comprendre, rapide, simple, et le comportement par défaut est intuitif : si une clé est en double, la clé du deuxième dico écrase la première.

Comme le précisait Etienne, ce comportement est néanmoins un parmi de nombreux possibles. On pourrait aussi vouloir:

Lever une exception en cas de doublon.
Concaténer ou additionner les doublons.
Mettre les doublons dans une liste.
Garder la valeur originale en cas de doublon.
Prendre la valeur la plus grande / petite en cas de doublon.
Etc.

Pour cela, notre contributeur a proposé qu’on puisse passer en paramètre une fonction qui choisit quelle valeur garder en cas de doublon. Le code devient donc :

def dmerge(d1, d2, merge_func=lambda v1, v2: v2):
    d = {}
    d.update([(k, v) for k, v in d1.iteritems() if k not in d2])
    d.update([(k, v) for k, v in d2.iteritems() if k not in d1])
    d.update([(k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2])
    return d

Avoir une valeur par défaut nous permet de garder le comportement initial. Pour cela on utilise une lambda. C’est ce qu’on appelle l’injection de dépendance.

Comme j’ai bien faire mumuse avec Python, je me suis demandé : “quelle est la stratégie de merge la plus rapide ?”. J’ai donc fait plusieurs tests de merge, avec plusieurs algos. Voici ce que ça donne:

 from itertools import chain
 
 
 def dmerge1(d1, d2, merge_func=None):
     """
         Mon premier essai, en virant la lambda et en utilisant itertools.
     """
     d = {}
 
     if merge_func is None:
 
         d.update(d1)
         d.update(d2)
         return d
 
     for k, v in chain(d1.iteritems(), d2.iteritems()):
         if k in d1 and k in d2:
             d[k] = merge_func(d1[k], d2[k])
         else:
             d[k] = v
 
     return d
 
 
 
 def dmerge2(d1, d2, merge_func=lambda v1, v2: v2):
     """
         Le code du PR original
     """
     d = {}
     d.update([(k, v) for k, v in d1.iteritems() if k not in d2])
     d.update([(k, v) for k, v in d2.iteritems() if k not in d1])
     d.update([(k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2])
     return d
 
 
 def dmerge3(d1, d2, merge_func=None):
     """
        Un mélange du code original et de mon premier essai.
     """
     d = {}
 
     d.update(d1)
 
     if merge_func is None:
         d.update(d2)
         return d
 
     for k, v in d2.iteritems():
         if k in d:
             d[k] = merge_func(d[k], v)
         else:
             d[k] = v
 
     return d
 
 
 
 def dmerge4(d1, d2, merge_func=None):
     """
         Le code original, en virant la lambda
     """
     d = {}
 
     if merge_func is None:
         d.update(d1)
         d.update(d2)
         return d
 
     d.update([(k, v) for k, v in d1.iteritems() if k not in d2])
     d.update([(k, v) for k, v in d2.iteritems() if k not in d1])
     d.update([(k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2])
     return d
 
 
 if __name__ == "__main__":
 
     import random
     import timeit
 
     print('Generate test dicts')
 
     # pour que le test soit juste, il faut créer plusieurs types de dicos:
     # des longs, et des courts avec plein de collisions ou moins
     d1 = {random.randint(0, 100): 'd1' for x in xrange(10000)}
     d2 = {random.randint(0, 100): 'd2' for x in xrange(10000)}
     d3 = {random.randint(0, 10000000): 'd1' for x in xrange(1000000)}
     d4 = {random.randint(0, 10000000): 'd2' for x in xrange(1000000)}
 
     merge_to_list = lambda a, b: [a, b]
 
     # ensuite il faut s'assurer que toutes ces fonctions retournent bien
     # la même chose
 
     print("Testing returns value all match")
 
     assert (dmerge1(d1, d2) == dmerge2(d1, d2)
             == dmerge3(d1, d2) == dmerge4(d1, d2))
     assert (dmerge1(d1, d2, merge_to_list) == dmerge2(d1, d2, merge_to_list)
            == dmerge3(d1, d2, merge_to_list) == dmerge4(d1, d2, merge_to_list))
 
     assert (dmerge1(d3, d4) == dmerge2(d3, d4)
             == dmerge3(d3, d4) == dmerge4(d3, d4))
     assert (dmerge1(d3, d4, merge_to_list) == dmerge2(d3, d4, merge_to_list)
             == dmerge3(d3, d4, merge_to_list) == dmerge4(d3, d4, merge_to_list))
 
     assert (dmerge1(d1, d4) == dmerge2(d1, d4)
             == dmerge3(d1, d4) == dmerge4(d1, d4))
     assert (dmerge1(d1, d4, merge_to_list) == dmerge2(d1, d4, merge_to_list)
             == dmerge3(d1, d4, merge_to_list) == dmerge4(d1, d4, merge_to_list))
 
 
     # enfin on lance l'évaluation du temps d'éxécution avec timeit()
 
     print("Start timing")
 
 
     # ce code est exécuté une fois par appel de timeit
     # notez l'astuce 'from __main__ import x' qui importe du code
     # du fichier en cours, ce qui sert rarement
     setup = '''from __main__ import (dmerge1, dmerge2, dmerge3, dmerge4,
                                      d1, d2, d3, d4, merge_to_list)'''
 
 
 
     # ensuite on fait des appels à timeit : 
     # - le premier paramètre est le code à mesurer: il faut qu'il 
     #   soit le plus simple et court possible
     # - le second et le code d'initialisation avant le test (hors mesure)
     # - le 3e est le nombre de fois que le code va être appelé. 
 
 
     # on va tester chaque fonction pour chaque type de dico, une fois
     # avec l'approche par défaut, et une fois avec une fonction de merge
     # personnalisée
     print "Lots of collisions"
 
     print "Default merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d2)", setup=setup, number=1000000)
     print "2", timeit.timeit("dmerge2(d1, d2)", setup=setup, number=1000000)
     print "3", timeit.timeit("dmerge3(d1, d2)", setup=setup, number=1000000)
     print "4", timeit.timeit("dmerge4(d1, d2)", setup=setup, number=1000000)
 
     print "Custom merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
     print "2", timeit.timeit("dmerge2(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
     print "3", timeit.timeit("dmerge3(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
     print "4", timeit.timeit("dmerge4(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
 
 
    # le nombre de répétitions est bien plus faible ici car sinon le test
    # est très très long
 
     print "Long dictionaries"
 
     print "Default merge strategy"
     print "1", timeit.timeit("dmerge1(d3, d4)", setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d3, d4)", setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d3, d4)", setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d3, d4)", setup=setup, number=100)
 
     print "Custom merge strategy"
     print "1", timeit.timeit("dmerge1(d3, d4, merge_to_list)",
                               setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d3, d4, merge_to_list)",
                               setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d3, d4, merge_to_list)",
                               setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d3, d4, merge_to_list)",
                               setup=setup, number=100)
 
     print "Mixed dictionaries"
 
     print "Default merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d4)", setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d1, d4)", setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d1, d4)", setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d1, d4)", setup=setup, number=100)
 
     print "Custom merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d4, merge_to_list)",
                              setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d1, d4, merge_to_list)",
                              setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d1, d4, merge_to_list)",
                              setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d1, d4, merge_to_list)",
                              setup=setup, number=100)
 
 
# Et voici le résultat que ça nous ressort. On voit clairement 
# que la 3eme fonction donne les meilleurs perfs, du coup
# c'est celle qu'on a choisit
 
 ## Generate test dicts
 ## Testing returns value all match
 ## Start timing
 ## Lots of collisions
 ## Default merge strategy
 ## 1 19.9299340248
 ## 2 148.185166121
 ## 3 21.2276539803
 ## 4 21.2074358463
 ## Custom merge strategy
 ## 1 30.646312952
 ## 2 18.522135973
 ## 3 14.0125968456
 ## 4 18.5139119625
 ## Long dictionaries
 ## Default merge strategy
 ## 1 84.4819910526
 ## 2 383.444111109
 ## 3 80.7273669243
 ## 4 86.0287930965
 ## Custom merge strategy
 ## 1 294.41114521
 ## 2 377.38009119
 ## 3 154.505481005
 ## 4 256.771039963
 ## Mixed dictionaries
 ## Default merge strategy
 ## 1 19.9574320316
 ## 2 87.1410660744
 ## 3 19.3570361137
 ## 4 19.524998188
 ## Custom merge strategy
 ## 1 60.6157000065
 ## 2 86.3876900673
 ## 3 59.0331327915
 ## 4 87.0504939556
 ## [Finished in 2494.7s]

Le test complet a pris en tout 2494.7s, soit 41 minutes, pour tourner sur ma machine, et je l’ai lancé plusieurs fois avec différentes modifs au fil de la journée. Il faut vraiment est un geek pour aimer faire ce genre de connerie. Parce que soyons honnête, tout le monde s’en branle des perfs de cette fonction :-)

Il faut savoir aussi qu’après coup j’ai réalisé que son code utilisait des listes en intention, et non des expressions génératrices, ce qui fait qu’il faut attendre que toute la liste soit générée avec que update() fasse son travail.

Il y avait donc des cas supplémentaires à tester et j’avais mergé son code dans batbelt. Arf, l’optimisation n’a jamais de fin ^^

Bref, j’ai relancé un test avec avec des listes en intentions (et même avec des expressions ternaires ce qui donne des trucs capilotractés):

def dmerge1(d1, d2, merge_func=None):
    """
        Une version de l'ancien dmerge3 qui utilise une expression génératrice.
    """
    d = {}
 
    d.update(d1)
 
    if merge_func is None:
        d.update(d2)
        return d
 
    d.update((k, (v if k not in d else merge_func(d[k], v))) for k, v in d2.iteritems())
 
    return d
 
 
 
def dmerge2(d1, d2, merge_func=lambda v1, v2: v2):
    """
        La version du proposée par notre gentil contributeur, mais
        avec des expressions génératrices à la place des listes en 
        intention.
    """
    d = {}
    d.update((k, v) for k, v in d1.iteritems() if k not in d2)
    d.update((k, v) for k, v in d2.iteritems() if k not in d1)
    d.update((k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2)
    return d
 
 
 
def dmerge3(d1, d2, merge_func=None):
    """
      La version la plus rapide du test précédent.
    """
    d = {}
 
    d.update(d1)
 
    if merge_func is None:
        d.update(d2)
        return d
 
    for k, v in d2.iteritems():
        if k in d:
            d[k] = merge_func(d[k], v)
        else:
            d[k] = v
 
    return d
 
 
def dmerge4(d1, d2, merge_func=None):
    """
        La version proposée par notre contributeur, optimisée comme un connard.
    """
    d = {}
 
    if merge_func is None:
        d.update(d1)
        d.update(d2)
        return d
 
    d.update((k, v) for k, v in d1.iteritems() if k not in d2)
    d.update((k, v) for k, v in d2.iteritems() if k not in d1)
    d.update((k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2)
    return d
 
 
## Generate test dicts
## Testing returns value all match
## Start timing
## Lots of collisions
## Default merge strategy
## 1 12.2690660954
## 2 97.121183157
## 3 12.1084120274
## 4 12.6807589531
## Custom merge strategy
## 1 8.73903894424
## 2 12.0493769646
## 3 8.00074601173
## 4 11.4764301777
## Long dictionaries
## Default merge strategy
## 1 54.5233860016
## 2 218.695598841
## 3 70.213809967
## 4 61.8348701
## Custom merge strategy
## 1 103.258821964
## 2 217.720175982
## 3 96.5204670429
## 4 214.480421066
## Mixed dictionaries
## Default merge strategy
## 1 19.169850111
## 2 66.9599928856
## 3 19.4371211529
## 4 19.5183057785
## Custom merge strategy
## 1 64.7940750122
## 2 66.9712991714
## 3 58.5918440819
## 4 67.5281140804
## [Finished in 1619.3s]

La bonne nouvelle pour moi, c’est que l’algo 3 est toujours le plus rapide, j’ai pas à re pusher.

Mais il est intéressant de constater que globalement les 4 tests mettent 1619.3s à s’exécuter. Globalement utiliser des expressions génératrices boost bien les perfs.

Télécharger le code de l’article.

Les vues sur des collections en Python

Sam — Sat, 03 Nov 2012 18:57:02 +0000

Python 3 introduit de nombreux changements qui ont été backportés dans Python 2.7. Parmi eux, les vues, qui sont un concept assez mal expliqué dans la documentation standard.

Dictionary views

Quand on voulait travailler sur les valeurs d’un dictionnaire en Python, on avait deux choix:

faire dict.values() et récupérer une liste entière. Créant une liste entière en mémoire.
faire dict.itervalues(), et récupérer un générateur. Mais qui ne peut être lu qu’une fois.

Les vues sont une solution intermédiaire: ce sont des objets qui prennent peu de mémoire, mais qui peuvent être lus plusieurs fois.

Exemple:

>>> scores = {'foo': 1, 'bar': 0}
>>> val = scores.viewvalues()
>>> print val
dict_values([1, 0])
>>> 1 in val
True
>>> [x * 2 for x in val]
[2, 0]

Contrairement à une liste, les vues issues d’un dictionnaire ne supportent pas le slicing ou l’assignation et il n’y a aucune garantie d’ordre des éléments. De plus, elles ne peuvent être modifiées.

Bref, une vue ne contient rien, c’est juste un objet qui, quand on accède à son contenu, va le chercher dans le dictionnaire et vous le retourne. C’est ce qu’on appelle un objet proxy: il vous donne l’illusion d’accéder directement aux données pour vous faciliter la vie, généralement en vous les présentant sous une forme différente: ici un itérable.

On peut récupérer des vues pour les valeurs, mais également pour les clés et les couples clés / valeurs. Ces deux types de vues se comportent en plus comme des sets:

>>> scores.viewitems()
dict_items([('foo', 1), ('bar', 0)])
>>> scores.viewkeys() | [3,]
set([3, 'foo', 'bar'])

Puisqu’il est rare d’avoir besoin d’une vraie liste, et comme les vues sont une très bonne alternative aux générateurs, dict.values et consorts retournent des vues en Python 3.

Maintenant vous allez me dire “Mais si les vues sont une si bonne alternative aux générateurs, pourquoi on ne remplace pas tous les générateurs par des vues ?”.

Tout simplement parce que ce n’est pas possible. Un générateur est un mécanisme standard qui permet de produire des valeurs une par une. N’importe qui peut créer un générateur, car c’est un concept portable d’un problème à un autre. On peut l’appliquer à de nombreuses choses: algorithme, flux de données, fichier, etc.

Une vue n’est qu’un proxy qui permet de voir une structure de données sous une autre forme. Il faut coder une vue par type de structure de données, car la vue va chercher les données dans cette structure quand on lui demande. Le code est donc différent à chaque fois.

Python ne permet pas de créer soi-même des vues, mais créer un proxy, c’est à dire un objet qui retourne les valeurs d’un autre objet quand on l’interroge, peut se faire à la main dans tout langage de programmation. Ainsi vous pourriez créer un proxy qui ressemble a une vue des clés d’un dico très simplement:

class keyview(object):
 
    def __init__(self, d):
        self.d = d
 
    def __iter__(self):
        return self.d.iterkeys()
 
>>> view = keyview(scores)
>>> for x in view:
...     print x
...     
foo
bar
>>> list(view)
['foo', 'bar']
>>>

L’implémentation réelle de Python (en C…) ne fait pas vraiment grand chose de plus, juste un travail d’optimisation pour être plus rapide.

memoryview

Les memory views suivent le même principe, mais appliqué à toute structure de données qui supporte le buffer protocole (un certain nombre de méthodes avec un nom et un comportement défini par ce protocole) comme celles trouvées dans le module struct ou array. La structure de données la plus connue qui suit le buffer protocole est la chaîne de caractères.

>>> s = 'Sam & Max eat the road with a Github fork'
>>> ms = memoryview(s)
>>> ms[-1]
'k'
>>> ms[:9]
<memory at 0x25ded60>
>>> ''.join(ms[:9])
'Sam & Max'

Le principal intérêt de la memory view appliquée aux strings, c’est que tout slicing retourne une nouvelle memory view. On peut donc travailler sur des parties de la chaînes sans créer une nouvelle chaîne en mémoire.

En revanche, les chaînes unicodes ne sont pas supportées. Il vous faudra jouer avec encode() et decode().