Aller plus loin avec les hash maps en Python 21


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.

21 thoughts on “Aller plus loin avec les hash maps en Python

  • Lomig Lavnek

    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.

  • Rodolphe B.

    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'

  • nogat

    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

  • Sam Post author

    @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 :

    array_diff(array("marc" => 12, "alice" => 23),
               array("marc" => 23, "alice" => 12));

    Retourne True.

    array("foo", "bar") != array("bar", "foo")

    Returne True.

    Et:

    array("foo" => 1, "bar" => 2) == array("bar" => 2, "foo" => 1)

    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.

  • Shagshag

    @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.

  • Shagshag

    @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’est array(0 => "foo", 1 => "bar") != array(0 => "bar", 1 => "foo") C’est pas un list

    je suis pas un Phplover non plus mais faut pas critiquer en bloc. C’est pas le même langage, pas la même logique.

  • Sam Post author

    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.

  • Samson
    array("foo","bar") == array("1"=&gt;"bar", "0"=&gt;"foo")

    retourne Vrai

    array(0=&gt;"foo",1=&gt;"bar") == array("1"=&gt;"bar", "0"=&gt;"foo")

    retourne Vrai

  • Shagshag

    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.

    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.

  • Shagshag

    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)

  • hindflo

    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.

    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é?

  • Sam Post author

    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.

  • Azerty

    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 :

    O(1) ? je suis curieux de savoir comment.

  • Sam Post author

    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/

  • cladmi

    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.

  • Batisteo

    Deux mini-coquilles :

    […] utilisent le dictionnaire pour montrer une forme ou une autre de compteur.

    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 :

    Inline comments should be separated by at least two spaces from the statement.

    Génial le Clippy ! :·D

  • Luthaf

    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.

    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]

  • Duckie

    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é.

  • Alex

    sympa le ticket
    Petit update pour ceux qui passeront plus tard:
    pip install sortedcontainers au lieu de pip install sorted_container

Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.