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 :
- 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.
Merci pour cet article. C’est très clair du début à la fin.
Je souhaite etudier les générateurs de sites statique et en faire un petit pour étude et ceci va vraiment me servir.
Qu’as-tu contre les array en PHP?
Très bien comme article, j’ai pu apprendre quelques petits trucs :)
Juste une petite précision : un set et un namedtuple ne peuvent être utilisés comme clé que s’ils ne contiennent que des objet hashables :
>>> {(1, 2): 42}
{(1, 2): 42}
>>> {(1, [2]): 42}
Traceback (most recent call last):
File "", line 1, in
TypeError: unhashable type: 'list'
Salut,
Les dictionnaires mes grands amis bordéliques.
Merci pour ces articles, les rares qui parlent de python sans utiliser la langue de Margaret Thatcher… a mon grand regret.
Biz
@anonyme: je n’ai rien contre. Ils sont juste mal foutus. C’est un mélange de set, de lists et de hashmap, qui ne fait correctement aucun des 3, et propose le comportement d’un des 3 sans qu’on sache lequel selon l’opération.
Exemples :
– le sorting est ubuesque: array_multisort, arsort, asort, ksort, krsort, natsort, natcasesort, sort, rsort, uasort, uksort, usort…
– les comparaisons sont une blaques :
Retourne True.
Returne True.
Et:
Retourne True.
– La notation litérale pour les arrays existent depuis seulement la version 5.4. LOL.
– Il y a 40 milles fonctions pour tout du coup: gérer des ensenbles, des slices, des queues… Tout ça sur la même structures de données. Aucun overloading d’opérateur pour rendre tout ça plus facile.
– Les perfs des arrays en tant que listes sont évidement toutes pourries puisque les clés sont toujours des hash aux lieu d’être des entiers.
C’est encore un truc que les mecs de PHP ont voulu faire “simple” en mélangeant, et ce faisant, il l’ont rendu imbitable pour autre chose que le cas le plus basique.
@Sam c’est plutôt pas la même chose. Un array en PHP c’est un OrderedDict en Python et les clés ne peuvent être que des int ou string.
C’est pas mal foutu, les array font bien ce qu’on leur demande, plus qu’un list, moins qu’un dict. Un pythoniste s’attend surement à ce qu’ils fassent plus mais dans ce cas c’est pas un array qu’il faut utiliser.
@Sam :
la multitude de fonction et leurs syntaxes ne sont pas liées aux array, c’est un reproche à PHP en général
array_diff != ‘==’
array("foo", "bar") != array("bar", "foo")c’est normal en vrai c’estarray(0 => "foo", 1 => "bar") != array(0 => "bar", 1 => "foo")C’est pas un listje suis pas un Phplover non plus mais faut pas critiquer en bloc. C’est pas le même langage, pas la même logique.
La multitudes des fonctions est partiellement liées au fait que les arrays font tout et n’importe quoi.
L’array, par ailleurs, n’est pas juste un ordered dict dans le sens ou l’indice numérique est en fait une clé, alors que le ordered dict à une clé ET un indice. Par ailleurs, les opérations ensemblistes se font aussi si l’array, donc on l’utilise aussi comme un set. Ce qu’on ne ferait pas avec un ordered dict, parce que ça n’a pas de sens.
Et “les arrays font bien ce qu’on leur demande”, ça dépend qui demande. Dans aucun autre langage on a une structure de base à qui on demande de faire tout ce bordel. C’est l’API là plus mal foutu de toutes les structures de données que je connaisse.
Les arrays en PHP, c’est la barre de faire, le truc à tout faire. Du coup il fait rien de bien. Par exemple, tu soulignes que le comportement que je reproche est “normal”, mais ça ne veut rien dire “normal”. Qu’il soi documenté pour être ainsi, ça ne le rend pas pour autant bon. La vérité c’est que tu ne connais pas précisément tous les cas de figures possibles de l’utilisation de l’array, un diff, un comparaison, un contains, etc, auront un comportement qui est parmis celui d’une list, d’un hash map ou d’un set, sans aucun moyen de le prévoir. C’est complètement incohérent, l’incohérence d’une API est le signe d’un mauvais design.
On peut manger sa purée avec un couteau. Ça va marcher. Mais qu’on ne vienne pas me dire que c’était le meilleur moyen. Pour une séquence, tu prends une forme de liste, pour un mapping, tu prend une forme de hash map, pour ensemble, tu prends une forme de set. Filer un truc qui fait vaguement les 3, avec abritrairement des traits des uns et des autres, c’est pas de l’informatique, c’est de la cuisine. J’aime la cuisine, mais pas pour faire des programmes.
retourne Vrai
retourne Vrai
Tu demandes à PHP des comportements d’objet qu’il n’a pas. Il a le comportement d’array PHP, pas de list, dict Python ou collection Java ou Perl. Ce comportement ne te convient pas ok c’est pas pour ça qu’il est mal foutu. Il n’est pas celui que tu attend. Tu voudrais peut être utiliser ArrayObject plutôt
Quand tu n’as qu’un couteau, tu ne manges pas de purée, tu n’y penses même pas, tu fais des frites.
Enfin bon je suis d’accord que PHP c’est pas de la programmation rigoureuse ou poussée.
(dommage qu’on ne puisse pas éditer ses commentaires)
Question stupide: en quoi c’est un avantage qu’elle soit en pure python? Alors que toute la moitié python se vantent “ouais nous on compilé directement en c tous ce qu’on pouvait pour être le plus performant possible”.
Question de compatibilité?
Pas besoin de compiler l’extension quand tu pip install.
Ca veut dire :
– si ton hosting te le permet pas la compilation, tu peux l’utiliser
– tu peux l’essayer en copiant juste le dossier du module, sans avoir à l’installer
– tu peux fournir un programme stand alone multi plateforme avec cette lib très facilement
– si tu veux l’utiliser sur ta machine, pas besoin d’installer gcc et les headers python
– tu peux l’utiliser sur des plateformes alternatives sans effort (exemple, android dans kivy)
– marche sur d’autres implémentations de python (pypy, jython, ironpython, brython, etc)
Si le but principal de ta lib est la perf (comme numpy ou pypy) et qu’utiliser le C est le seul moyen d’y arriver, alors utiliser une extension C est une bonne chose, à condition de fournir un bon support de binaires compilés pour pas mal de plateformes. Mais si tu peux répondre à ton cahier des charges en pur Python, alors c’est idéal.
O(1) ? je suis curieux de savoir comment.
Pour la complexité des opérations sur les types de base en Python, la référence est ce document : https://wiki.python.org/moin/TimeComplexity
On note que le cas moyen est O(1), mais on peut avoir un extrema maximum à O(n). A noter que N est le nombre max d’élément qu’il y a eu dans le dict, pas la taille de la valeur hashée.
Pour ce qui est de l’implémentation, les valeurs sont dans un array, et l’indice de cet array est calculé via un hash de la valeur. Une bonne explication ici :
http://www.laurentluce.com/posts/python-dictionary-implementation/
En effet je connaissais le
get(val, default)mais le ‘setdefault‘ j’étais passé à côté. Les premières fois où je l’ai vu, je m’étais dis que c’était en rapport avec les defaultdict…C’est un pattern tellement récurent en plus.
Merci pour ce rappel, on commence à tout connaître, mais on se fait toujours surprendre par un truc basique de l’espace qui nous change la vie.
Deux mini-coquilles :
Rajouter le retour de c[‘z’] :
»» c['z'] += 1 # pas de KeyError
»» c['z']
1 # <--- Oh, un un !
»» c.most_common(2) # et en bonus
[('b', 3), ('a', 2)]
Et pour faire mon fourreur de drosophiles :
Génial le Clippy ! :·D
Et le Lua alors ? Les tables font à la fois liste, dico, structure de données et permettent même de créer des classes !
Mais contrairement à PHP, l’API est certes minimaliste et bien faite.
[HS] C’est quoi ce trombone qui me juge pendant que j’écris mon message ? Si je fait du LaTeX, c’est bien pour ne pas voir sa figure ![/HS]
Moi qui allait me mettre au Lua…
Hello
Je suis d’accord avec Sam sur les array en PHP, c’est vraiment bâtard comme outil.
En Lua, c’est encore pire ! Les tables peuvent contenir à la fois une partie indicée sur des entiers et une autres indicée sur des clés. Pour pouvoir compter les éléments, il y a plusieurs techniques aussi, dont celle de stocker une clé qui s’appelle “n”, sous certaines conditions, parfois il faut écrire une boucle à la main. Et pour ne rien arranger, les indices commencent à 1 au lieu de zéro (sous prétexte, selon la doc que c’est plus intuitif !!!). Il faut mettre ça en regard de la légèreté du moteur d’exécution, mais pour la propreté LUA peut repasser.
Pour ce qui est de la complexité d’accès dans une hashmap, cela est commun à toutes les hashmaps quel que soit le langage : le terme “hashmap” désigne bien la technique d’implémentation et pas le fait d’associer une valeur à une clé.
sympa le ticket
Petit update pour ceux qui passeront plus tard:
pip install sortedcontainersau lieu de pip install sorted_containerBon le billet à déjà une paire d’années, mais pour le newbie que je suis moins maintenant grâce à ce site, je me suis dit que j’allais essayer de faire un commentaire intelligent qui aurait pu m’aider au moment où j’ai découvert les merveilles du module collections.
Je me demandais récemment pourquoi j’avais utiliser setdefault() au lieu d’un defaulftdict, j’ai compris que j’avais commis une erreur de jeunesse (ah quelques mois en arrière j’étais pur et innocent … ah on me dit que non) pour deux raisons, la première étant la vitesse et la deuxième, plus fondamentale je trouve, je l’ai trouvé en cherchant sur le net :
C’était dès lors clair pour moi, j’ai dû tirer un trait sur setdefault().
PS : J’ai trouvé ça sur stupidpythonideas.blogspot.fr.
PS 2: Une traduction pourrait-être : “Vous devez regarder comment la valeur retournée (par dictionnaire[clé]) va être utilisée plus tard dans le code. Quand vous rencontrerez une clé manquante, voulez-vous une liste vide (la valeur par défaut dans l’exemple), ou une KeyError ?”