Sam & Max » dico http://sametmax.com Du code, du cul Sat, 07 Nov 2015 10:56:13 +0000 en-US hourly 1 http://wordpress.org/?v=4.1 Chercher dans plusieurs dicts à la fois avec ChainMap 14 http://sametmax.com/chercher-dans-plusieurs-dicts-a-la-fois-avec-chainmap/ http://sametmax.com/chercher-dans-plusieurs-dicts-a-la-fois-avec-chainmap/#comments Fri, 11 Jul 2014 08:09:25 +0000 http://sametmax.com/?p=11382 ChainMap.]]> 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.

]]>
http://sametmax.com/chercher-dans-plusieurs-dicts-a-la-fois-avec-chainmap/feed/ 14
Aller plus loin avec les hash maps en Python 21 http://sametmax.com/aller-plus-loin-avec-les-hash-maps-en-python/ http://sametmax.com/aller-plus-loin-avec-les-hash-maps-en-python/#comments Mon, 30 Jun 2014 03:28:26 +0000 http://sametmax.com/?p=11217 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 "<ipython-input-12-eed7cf6f5344>", 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,
 '# <file system> <mount point>   <type>  <options>       <dump>  <pass>\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 :

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.

]]>
http://sametmax.com/aller-plus-loin-avec-les-hash-maps-en-python/feed/ 21