Sam & Max » dict

Compter et grouper : encore plus fainéant 6

Sam — Wed, 01 Jul 2015 19:37:12 +0000

Après avoir bien galéré à créer un compteur à la main avec un dico, vous avez découvert les joies des méthodes dict.get et dict.setdefault. Puis évidemment quelqu’un vous a pointé vers collections.defaultdict, et enfin, vous avez fini par découvrir collections.Counter. Joie.

Le parcours est à peu près toujours le même quand on veut grouper ou compter des valeurs en Python.

Malgré cela, je vois encore des gens qui sous utilisent ces collections. Par exemple, Counter peut compter automatiquement :

>>> from collections import Counter
>>> Counter('jfsqmfjdklmqfjsdqklmfjdsqhfdqsjkhfdshjkl')
    Counter({'j': 6, 'f': 6, 'q': 5, 's': 5, 'd': 5, 'k': 4, 'l': 3, 'm': 3, 'h': 3})

Mais ce que ne réalisent pas beaucoup de développeurs, c’est que cet objet accepte n’importe quel itérable en paramètre. Nous sommes en Python, et rededjiou, je me tue à répéter que l’itération est la philosophie centrale du langage.

Donc le compteur peut prendre une expression génératrice en paramètre.

Par exemple, si vous voulez compter un truc un peu plus complexe que des éléments, comme mettons, le ratio de lignes commentées dans un fichier, vous n’avez pas besoin de faire ça :

count = Counter()
for line in open('/etc/fstab', encoding='ascii'):
        count[line.startswith('#')] += 1
 # out : Counter({True: 10, False: 3})

Ceci marchera parfaitement :

count = Counter(line.startswith('#') for line in open('/etc/fstab', encoding='ascii'))
# out : Counter({True: 10, False: 3})

Vous pouvez également utiliser des générateurs plus complexes. Combien de fichiers par types d’extensions ?

import os
import pathlib
 
def get_extensions(path):
    for dirpath, dirnames, files in os.walk(path):
        for name in files:
            ext = pathlib.Path(name).suffix
            if ext: # on ignore les fichiers sans extension
                yield ext
 
 
Counter(get_extensions('/etc')).most_common(9)
 # Out : 
 # ('.conf', 632),
 # ('.0', 348),
 # ('.gz', 323),
 # ('.jhansonxi', 207),
 # ('.pem', 177),
 # ('.load', 127),
 # ('.ttb', 86),
 # ('.ktb', 80),
 # ('.kti', 55)]

Notez que le Counter peut faire plus que compter. Ici il nous donne les 9 plus grandes valeurs du classement, mais en prime, il peut aussi nous faire des opérations ensemblistes :

>>> c = Counter("aabbbbbbbbbbbbcccc")
>>> c & Counter('aaaaaaaaaaaaaaabbcddddddd') # valeurs min
    Counter({'b': 2, 'a': 2, 'c': 1})
>>> c | Counter('aaaaaaaaaaaaaaabbcddddddd') # valeurs max
    Counter({'a': 15, 'b': 12, 'd': 7, 'c': 4})

Le compteur fournit par Python est donc naturellement très, très puissant.

Une autre chose qui est rarement faite : sous-classer ces types.

Par exemple, si vous avez souvent des opérations où il faut grouper des valeurs :

from collections import defaultdict
 
class Grouper(defaultdict):
 
    def __init__(self, iterable):
        super(Grouper, self).__init__(list)
        self.update(iterable)
 
    def update(self, iterable):
        try:
            iterable = iterable.items()
        except AttributeError:
            iterable = iterable
        for k, v in iterable:
            self[k].append(v)

On prend un default dict, on lui dit qu’un update ajoute les éléments à la liste en valeur plutôt que de la remplacer, et zou, vous avez un dictionnaire qui va grouper toutes les valeurs automatiquement.

Liste des fichiers par extensions ? Fastoche !

def get_extensions(path):
    for dirpath, dirnames, files in os.walk(path):
        for name in files:
            ext = pathlib.Path(name).suffix
            if ext: 
                yield ext, name # on rajoute le name ici
 
>>>files = Grouper(get_extensions('/etc'))
>>> files['.tti']
['en-na-ascii.tti',
 'numbers-french.tti',
 'devanagari.tti',
 'letters-cyrillic.tti',
 'punctuation-basic.tti',
 'malayalam.tti',
 'ascii-basic.tti',
 'spaces.tti',
 'letters-latin.tti',
 'letters-latin-dot8.tti',
 'en-chess.tti',
 'numbers-dot8.tti',
 'punctuation-tibetan.tti',
 'boxes.tti',
 'gujarati.tti',
 'numbers-nemeth.tti',
 'punctuation-alternate.tti',
 'common.tti',
 'blocks.tti',
 'gurmukhi.tti',
 'kannada.tti',
 'telugu.tti',
 'tamil.tti',
 'numbers-dot6.tti',
 'de-chess.tti',
 'control-latin.tti',
 'letters-tibetan.tti',
 'oriya.tti',
 'bengali.tti']

Bref, compter et grouper sont des opérations si communes : ne vous faites par chier à refaire tout ça à la main.

Views VS generators 6

Sam — Wed, 25 Mar 2015 18:57:20 +0000

Avec Python 2.7, un outil appelé les “views” (les “vues”) est apparu. Une vue est juste un enrobage qui permet de voir un objet d’une certaine façon, et de le manipuler d’une certaine façon (avec une autre API), sans changer cet objet.

Les vues ont surtout été notables pour leur apparition dans les dictionnaires avec Python 2.7:

    >>> scores = {"sam": 1, "max": 0}
    >>> scores.items() # retourne une lsite
    [('max', 0), ('sam', 1)]
    >>> scores.iteritems() # retourne un générateur
    <dictionary-itemiterator object at 0x7f8782a26628>
    >>> list(scores.iteritems()) # sans views
    [('max', 0), ('sam', 1)]
    >>> scores.viewsitems() # avec views
    Traceback (most recent call last):
      File "", line 1, in <module>
        scores.viewsitems() # avec views
    AttributeError: 'dict' object has no attribute 'viewsitems'
 
    >>> scores.viewitems() # retourne une vue
    dict_items([('max', 0), ('sam', 1)])

Néanmoins personne ne les a vraiment utilisé, et c’est un tort. Elles sont en effet très performantes, et pour cette raison sont retournées par défaut avec items() en Python 3.

En effet, les vues ne sont qu’un enrobage : elles ne contiennent rien, et donc ne prennent pas beaucoup mémoire, tout comme les générateurs.

Mais contrairement aux générateurs, les vues ne se vident pas et peuvent exposer une API plus complète que les générateurs, comme par exemple déclarer une taille :

>>> items = scores.iteritems()
>>> list(items)
[('max', 0), ('sam', 1)]
>>> list(items) # woops
[]
>>> items = scores.viewitems()
>>> list(items)
[('max', 0), ('sam', 1)]
>>> list(items)
[('max', 0), ('sam', 1)]
>>> len(scores.iteritems()) # nope
Traceback (most recent call last):
  File "", line 1, in <module>
    len(scores.iteritems())
TypeError: object of type 'dictionary-itemiterator' has no len()
 
>>> len(scores.viewitems())
2

Alors certes, on ne peut pas mettre des vues partout, et les générateurs restent utiles. Mais quand il est possible de les utiliser, et à moins d’avoir besoin d’une liste afin de modifier les valeurs in place, il n’y pas de raison de ne pas le faire : c’est le meilleur des deux mondes.

Chercher dans plusieurs dicts à la fois avec ChainMap 14

Sam — Fri, 11 Jul 2014 08:09:25 +0000

Depuis Python 3.3 existe un nouvel outil pour travailler avec les dicos et j’étais complètement passé à côté : ChainMap.

Il permet de créer un objet qui se comporte comme un dict, mais qui va chercher dans plusieurs dictionnaires.

Un exemple sera plus clair.

Imaginez que vous ayez un système de configuration avec des valeurs par défaut :

default_config = {'DEBUG': False, 'HOST': 'localhost', 'PORT': 8080}

Puis votre utilisateur peut fournir un fichier de configuration settings.py qui contient :

DEBUG = True
PORT = 8000

Et avec un peu de parsing, vous le récupérez sous forme de dico :

import settings
user_config = {k: v for k, v in vars(settings).items() if k.isupper()}
## {'DEBUG': True, 'PORT': 8000}

Puis l’utilisateur peut passer la config via la ligne de commande, et une fois il fait :

--host 0.0.0.0

Et vous récupérez la config :

cmd_config = {"HOST": "0.0.0.0"}

Maintenant il faut prendre tout ça en compte. La ligne de commande écrase le fichier de config qui écrase les valeurs par défaut :

conf = {}
conf.update(default_config)
conf.update(user_config)
conf.update(cmd_config)
print(conf) # configuration finale
## {'DEBUG': True, 'HOST': '0.0.0.0', 'PORT': 8000}

Ça va marcher, mais ça a plusieurs défauts :

Si vos dicos sont très grands, vous prenez encore plus de place en mémoire.
Si vous modifiez conf, impossible de savoir quelle était sa valeur initiale.
Si vous modifiez user_config, il faut tout refusionner. Mais si vous avez modifié conf entre temps, comment vous assurer que vous n’allez pas écraser ces modifications ?
Si vous voulez temporairement faire une modification à conf, il faut de nouveau créer un dico en plus avec tout dedans.

ChainMap résout ce problème en cherchant une clé dans une liste de dicos sous-jacent, mais en appliquant les modifications uniquement sur le premier dico.

>>> from collections import ChainMap
 
>>> conf = ChainMap({}, # <- ce mapping sera le seul modifié
                    # les clés seront cherchées dans cet ordre :
                    cmd_config, 
                    user_config, 
                    default_config)
 
>>> conf['HOST']
>>> '0.0.0.0'
>>> conf['DEBUG']
>>> True
>>> conf['PORT']
>>> 8000

Les dicos sont ici stockés par référence, ça ne prend pas de mémoire en plus, et si on modifie un dico :

user_config['DEBUG'] = False

Alors c’est reflété par ChainMap:

>>> conf['DEBUG']
False

Si on fait une modification, seul le dico le plus haut dans la chaine (ici notre dico vide), est modifié :

>>> conf["PORT"] = 7777
>>> conf
ChainMap({'PORT': 7777}, {'HOST': '0.0.0.0'}, {'DEBUG': False, 'PORT': 8000}, {'DEBUG': False, 'HOST': 'localhost', 'PORT': 8080})

Et si on a besoin d’un contexte temporaire, on peut créer un enfant :

>>> sub_conf = conf.new_child()
>>> sub_conf
ChainMap({}, {'PORT': 7777}, {'HOST': '0.0.0.0'}, {'DEBUG': False, 'PORT': 8000}, {'DEBUG': False, 'HOST': 'localhost', 'PORT': 8080})

Cela crée un nouveau ChainMap, avec un dico vide en haut de la chaîne, qui permet donc de travailler temporairement avec de nouvelles valeurs, sans toucher au ChainMap d’origine.

Aller plus loin avec les hash maps en Python 21

Sam — Mon, 30 Jun 2014 03:28:26 +0000

Les hash map sont souvent sous-utilisés, surtout par les personnes venant d’un autre langage avec implémentation vraiment batarde du concept. Les arrays en PHP et les objets en Javascript étant parmi les pires exemples.

Le point d’entrée pour les hash maps en Python, c’est le dictionnaire. Et la plupart des gens ont pigé le principe de l’association clé / valeur :

>>> d = {}
>>> d['cle'] = 'valeur'
>>> d['cle']
'valeur'
>>> d['pas cle']
Traceback (most recent call last):
  File "", line 1, in <module>
    d['pas cle']
KeyError: 'pas cle'

L’intérêt du dictionnaire étant qu’accéder à une clé est très rapide (c’est une opération O(1)), tout comme vérifier qu’une clé est présente dans le dico :

>>> 'cle' in d
True

Mais généralement les gens s’arrêtent là.

Itération

Parfois, ils vont plus loin, et tentent l’itération dessus :

>>> scores = {"Joe": 1, "Jonh": 5, "Jack": 3, "Jenny": 7, "Jeanne": 0, "July": 3}
>>> for score in scores:
    print(score)
...
Jenny
Jack
Joe
July
Jonh
Jeanne

Ils s’aperçoivent qu’on peut uniquement récupérer les clés, et essayent de faire ça :

>>> for nom in scores:
    print(nom, scores[nom])
...
Jenny 7
Jack 3
Joe 1
July 3
Jonh 5
Jeanne 0

Rapidement ils sont corrigés par quelques collègues qui leur expliquent qu’on peut faire ceci :

>>> for nom, score in scores.items():
    print(nom, score)
...
Jenny 7
Jack 3
Joe 1
July 3
Jonh 5
Jeanne 0

Sans vraiment expliquer pourquoi. Si vous êtes curieux, cela marche grâce à l’unpacking.

Ensuite ils vont chercher à afficher des choses dans l’ordre, mais un dictionnaire n’est pas ordonné. Là commencent les embrouilles : dans l’ordre des clés, des valeurs ou dans l’ordre d’insertion ?

Dans l’ordre des clés ou des valeurs, il faut se taper le tri à chaque fois :

>>> for nom, score in sorted(scores.items()):
    print(nom, score)
...
Jack 3
Jeanne 0
Jenny 7
Joe 1
Jonh 5
July 3
>>> for nom, score in sorted(scores.items(), key=lambda x: x[1]):
    print(nom, score)
...
Jeanne 0
Joe 1
Jack 3
July 3
Jonh 5
Jenny 7

Dans l’ordre d’insertion par contre, ce n’est pas possible avec le dictionnaire. Mais voilà l’astuce : le hash map en Python, ce n’est pas QUE le type dict.

Pour ce problème, on peut utiliser collections.OrderedDict :

>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> d['Jeanne'] = 3
>>> d['Jack'] = 2
>>> d['July'] = 6
>>> for nom, score in d.items():
        print(nom, score)
...
Jeanne 3
Jack 2
July 6

Après il y a le rare problème, mais tout de même existant, de la très très grosse structure de données que l’on veut itérer dans l’ordre de clés :

>>> import random
>>> l = range(10000000)
>>> random.shuffle(l)

Si on fait un sort dessus, ça prend plusieurs secondes :

>>> l.sort()

Imaginez avec un dico qui contient un million de clés sous forme de texte. La lecture dans l’ordre sera très, très lente. Parfois ce n’est pas grave, et parfois c’est très emmerdant.

La stdlib de Python ne permet pas de répondre à ce problème facilement. On pourrait bricoler quelque chose avec heapq, mais franchement, c’est se casser la tête pour rien.

Le plus simple est d’utiliser une lib externe, par exemple l’excellente sorted_container, qui en plus d’être très rapide, est en pur Python. Du coup, un peu de pip :

pip install sortedcontainer

Et on est bon.

>>> from sortedcontainers import SortedDict
>>> d = SortedDict()
>>> d['Joe'] = 1
>>> d['Jeanne'] = 6
>>> d['July'] = 3
>>> d['John'] = 3
>>> for nom, score in d.items():
    print(nom, score)
...
Jeanne 6
Joe 1
John 3
July 3

SortedDict s’assure que le dictionnaire reste ordonné à chaque insertion d’un élément, et ainsi, vous évite de devoir faire un tri tout à la fin.

Initialisation

La plupart du temps, on utilise la notation littérale. Mais le constructeur dict trouve son utilité dans le fait qu’il accepte un itérable de tuples en paramètre :

>>> dict([("a", 1), ("b", 2)])
{'a': 1, 'b': 2}

La plupart du temps, les gens n’en voient pas l’utilité. Mais il faut se rappeler que tout le langage Python est organisé autour de l’itération. Je ne cesse de le répéter, en Python, l’itération est tout.

De fait, cette particularité du constructeur du dico vous permet de créer des dictionnaires à partir de structures existantes inattendues…

Prendre deux séquences et les pairer :

>>> personnes = ('Joe', 'John', 'Jean-Michel')
>>> scores = (4, 10, 34)
>>> zip(personnes, scores)
[('Joe', 4), ('John', 10), ('Jean-michel', 34)]
>>> dict(zip(personnes, scores))
{'Jean-michel': 34, 'John': 10, 'Joe': 4}

Pairer les deux derniers champs du résultat d’une commande :

>>> import subprocess
>>> df = subprocess.check_output('df')
>>> print(df)
Sys. de fichiers       blocks de 1K  Utilisé Disponible Uti% Monté sur
/dev/sda7                   7972000  6614840     929156  88% /
none                              4        0          4   0% /sys/fs/cgroup
udev                        1968688        4    1968684   1% /dev
tmpfs                        395896     1112     394784   1% /run
none                           5120        0       5120   0% /run/lock
none                        1979472      160    1979312   1% /run/shm
none                         102400       44     102356   1% /run/user
/dev/sda5                  65438480 57693436    4397852  93% /media/sam/
>>> dict(l.split()[-2:] for l in  list(df.split('\n'))[1:] if l)
{'31%': '/media/truecrypt1', '1%': '/run/user', '93%': '/media/sam', '88%': '/', '0%': '/run/lock'}

Depuis Python 2.7, cette fonctionnalité est partiellement phagocytée par la syntaxe pour les intentions sur les dicos :

>>> from pprint import pprint
>>> pprint( {line: num for num, line in enumerate(open('/etc/fstab'), 1)})
{'#\n': 6,
 '# / was on /dev/sda7 during installation\n': 8,
 '# /etc/fstab: static file system information.\n': 1,
 '#                \n': 7,
 "# Use 'blkid' to print the universally unique identifier for a\n": 3,
 '# device; this may be used with UUID= as a more robust way to name devices\n': 4,
 '# swap was on /dev/sda6 during installation\n': 10,
 '# that works even if disks are added and removed. See fstab(5).\n': 5,
 'UUID=4c0455fb-ff57-466a-8d1f-22b575129f4f none            swap    sw              0       0\n': 11,
 'UUID=4f560031-1058-4eb6-a51e-b7991dfc6db7 /               ext4    errors=remount-ro 0       1\n': 9,
 'UUID=b27f7e93-60c0-4efa-bfae-5ac21a8f4e3c /media/sam ext4 auto,user,rw,exec 0 0\n': 12}

Cela dit, on n’a pas toujours besoin de clés ET de valeurs pour créer un dictionnaire. Ainsi, si on a une liste de n’clés qu’on veut toutes initialiser à la même valeur, la très peu connue méthode fromkeys nous rendra bien service :

>>> personnes = ('Joe', 'John', 'Jean-michel')
>>> dict.fromkeys(personnes, 0)
{'Jean-michel': 0, 'John': 0, 'Joe': 0}

De même, on peut ne pas vouloir initialiser un dico, mais vouloir une valeur par défaut pour toutes les clés. collections.defaultdict est fait pour ça. En plus, les valeurs peuvent être dynamiques :

>>> from collections import defaultdict
>>> scores = defaultdict(lambda: 0)
>>> scores['Joe']
0
>>> scores['Joe'] = 1
>>> scores['Joe']
1
>>> scores['July']
0
>>> import datetime
>>> naissances = defaultdict(datetime.datetime.utcnow)
>>> naissances['Joe']
datetime.datetime(2014, 6, 29, 6, 58, 11, 412202)

Enfin, je sais que tous les tutos du monde en Python utilisent le dictionnaire pour montrer une forme ou une aute de compteur. Mais si vous avez VRAIMENT besoin d’un compteur, utilisez collections.Counter qui est un objet avec l’interface d’un dictionnaire mais avec tout ce qu’il faut pour compter :

>>> from collections import Counter
>>> c = Counter('abbbac') # comptage automatique
>>> c
Counter({'b': 3, 'a': 2, 'c': 1})
>>> c['c']
1
>>> c['d'] # pas de KeyError
0
>>> c['z'] += 1 # pas de KeyError
>>> c['z']
>>> c.most_common(2) # et en bonus
[('b', 3), ('a', 2)]

Clé en main

Récupérer une clé si on ne sait pas si elle est présente est une opération courante, et la documentation montre généralement ça :

try:
   val = dico['cle']
except KeyError:
   val = 'valeur par defaut'

Bien que ce soit parfaitement valide, c’est généralement se faire chier pour rien puisqu’on peut faire ça en une ligne :

   val = dico.get('cle', 'valeur par defaut')

Néanmoins la méthode get() est très connue. Moins connue est la méthode setdefault. En effet, parfois on veut faire plutôt ceci :

try:
   val = dico['cle']
except KeyError:
   dico['cle'] = 'valeur par defaut'
   val = 'valeur par defaut'

Et ça peut également se faire en une ligne :

   val = dico.setdefault('cle', valeur par defaut)

J’aimerais aussi en profiter pour rappeler que les clés des dicos peuvent être n’importe quel objet hashable, pas juste une string ou un int. Notamment, les tuples sont des clés valides, et comme l’opérateur tuple est la virgule et non la parenthèse, cette syntaxe est parfaitement valide :

>>> d = {}
>>> d[1, 2] = 'tresor'
>>> d[3, 3] = 'mine'
>>> d
{(1, 2): 'tresor', (3, 3): 'mine'}
>>> d[3, 3]
'mine'

Parmi les objets utilisables comme clés :

Les frozenset.
Les namedtuples
Les instances de vos classes

Si vous avez un doute, il est facile de savoir si un objet est hashable ou pas :

>>> import collections
>>> isinstance({}, collections.Hashable)
False
>> isinstance(0, collections.Hashable)
True

Mon dico à moi, c’est le meilleur

On peut tout à fait hériter du type dictionnaire pour obtenir un type qui a des fonctionnalités que le type original n’a pas :

>>> class MonDico(dict):
...     def __add__(self, other):
...         new = {}
...         new.update(self)
...         new.update(other)
...         return new
...
>>> d1 = MonDico(a=1, b=2)
>>> d2 = MonDico(b=3, c=3)
>>> d1 + d2
{'a': 1, 'c': 3, 'b': 3}

Mais c’est assez rare. La plupart du temps on veut plutôt rajouter des fonctionnalités de conteneur à un type existant. Dans ce cas, les méthodes magiques viennent à la rescousse. Par exemple :

class Phrase(object):
 
   def __init__(self, string):
      self.words = string.split()
 
   def __getitem__(self, word):
      return [i for i, w in enumerate(self.words) if w == word]
 
>>> p = Phrase("Une petite puce pique plus qu'une grosse puce ne pique")
>>> p['petite']
[1]
>>> p['puce']
[2, 7]

Hey oui, les hash maps en Python, c’est un sujet qui peut aller très, très loin. C’est ce qui est merveilleux avec ce langage, on peut rapidement programmer en effleurant juste la surface, sans se noyer. Et si on a besoin d’aller plus loin, des profondeurs abyssales de features nous attendent.

Mesurer les performances d’un snippet Python 6

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 15

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