Dictionnaires et ensembles

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• construire un dictionnaire, y accéder par clé, y ajouter, y modifier et y supprimer des couples, et choisir entre l'accès direct d[cle] et la méthode get selon que l'absence d'une clé est une anomalie ou un cas normal;
• dire quels objets peuvent servir de clé et expliquer pourquoi une liste ne le peut pas, en lisant le message d'erreur que Python produit;
• parcourir un dictionnaire par ses clés, ses valeurs ou ses couples, et écrire sans hésiter la boucle for cle, valeur in d.items();
• écrire de mémoire les deux motifs qui justifient à eux seuls l'existence des dictionnaires — compter avec get(cle, 0) + 1 et regrouper dans des listes;
• construire des ensembles, les combiner par union, intersection, différence et différence symétrique, et savoir pourquoi {} est un dictionnaire et non un ensemble;
• justifier, mesure à l'appui, pourquoi tester l'appartenance à un ensemble ou à un dictionnaire ne coûte pas ce que coûte le même test sur une liste, et choisir entre liste, tuple, dictionnaire et ensemble en fonction de ce que vous faites de vos données.

Pourquoi un dictionnaire

Ce que la liste avait perdu

Depuis le chapitre 3, ce cours revient aux mêmes dix notes. Au chapitre 3 elles étaient tapées une à une dans une boucle; au chapitre 6 elles sont devenues une liste, et cela a été un vrai progrès: une seule variable, une longueur, un parcours, un tri. Rappelons cette liste — il s'agit d'une classe fictive de dix étudiants, notée selon le barème suisse de 1 à 6, la moyenne étant obtenue à 4.

# Les notes du cours, telles que le chapitre 6 les rangeait: une liste
notes_liste = [4.5, 5.0, 3.5, 6.0, 4.0, 5.5, 4.5, 3.0, 5.0, 4.5]
print(notes_liste[3])
print(max(notes_liste))

6.0
6.0

Le programme répond bien. Mais regardez ce qu'il ne dit pas. notes_liste[3] vaut 6.0: la note de qui? max(notes_liste) vaut 6.0 aussi: quel étudiant a obtenu la meilleure note? La liste a rangé les valeurs, elle a même conservé leur ordre, mais elle a perdu la seule chose qui rendait ces valeurs intéressantes: le nom auquel chacune se rapporte. Une liste associe des valeurs à des positions, 0, 1, 2, et le monde réel se moque des positions. Ce que vous voulez écrire, c'est «la note d'Alice», pas «la note numéro 0».

Bien sûr, on peut s'en sortir. On peut tenir deux listes parallèles, une de noms et une de notes, et se jurer de toujours les modifier ensemble. C'est une solution fragile: le jour où vous triez les notes sans trier les noms, chacun hérite de la note de son voisin, et le programme ne signale rien du tout — il donne simplement de mauvaises réponses. Ce genre de bogue est particulièrement désagréable parce qu'il ne provoque aucune erreur.

La liste de couples, et pourquoi elle ne suffit pas

Le chapitre 6 nous a donné un meilleur outil: le tuple. On peut ranger chaque étudiant avec sa note dans un couple, et mettre tous les couples dans une liste. Les deux informations voyagent alors ensemble; un tri ne peut plus les séparer.

# Une liste de couples (nom, note): il faut chercher le nom
notes_paires = [("Alice", 4.5), ("Bruno", 5.0), ("Chloe", 3.5),
                ("David", 6.0), ("Elena", 4.0), ("Farid", 5.5),
                ("Gaelle", 4.5), ("Hugo", 3.0), ("Ines", 5.0),
                ("Jonas"

5.5
None

Cela fonctionne, et c'est déjà honnête. Mais deux choses clochent.

D'abord, il faut écrire une fonction pour une opération aussi élémentaire que «donne-moi la note de Farid». Dans un programme réel, vous consultez une table des dizaines de fois; devoir appeler note_de(...) à chaque fois, avec les parenthèses, la liste à passer et le None à tester, alourdit tout.

Ensuite, et c'est plus grave, cette fonction cherche. Elle part du premier couple et compare le nom, puis le deuxième, puis le troisième, jusqu'à tomber sur le bon ou à épuiser la liste. Pour Farid, sixième de la liste, six comparaisons. Pour un nom absent, dix comparaisons — la totalité de la liste — avant de pouvoir conclure. Sur dix étudiants c'est insensible. Sur un fichier de 50 000 clients, chaque consultation devient un parcours de 50 000 couples, et si vous en faites 50 000, vous venez de demander à votre machine deux milliards et demi de comparaisons. Nous mesurerons ce coût à la fin du chapitre; retenez pour l'instant qu'il est réel.

L'idée: une table de correspondance

Le dictionnaire résout les deux problèmes d'un coup. C'est une structure qui associe directement une clé à une valeur, et qui retrouve la valeur à partir de la clé sans parcourir quoi que ce soit.

Le mot «dictionnaire» est bien choisi: dans un dictionnaire de langue, vous ne cherchez pas le mot numéro 12 480, vous cherchez le mot «ensemble», et vous ne lisez pas le volume page après page pour le trouver. D'autres langages appellent la même structure une table de hachage, un tableau associatif ou une map; en Python, c'est le type dict.

Le reste du chapitre déplie cette idée: comment construire un dictionnaire, comment y accéder sans se faire arrêter par une erreur, comment le parcourir, et surtout les deux programmes-types — compter et regrouper — que l'on réécrit toute sa vie de programmeur.

Construction et accès

Écrire un dictionnaire

Le plus simple est de l'écrire en toutes lettres, entre accolades. Voici enfin le carnet de notes du cours dans sa forme définitive.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

print(notes["Farid"

5.5
10
{'Alice': 4.5, 'Bruno': 5.0, 'Chloe': 3.5, 'David': 6.0, 'Elena': 4.0, 'Farid': 5.5, 'Gaelle': 4.5, 'Hugo': 3.0, 'Ines': 5.0, 'Jonas': 4.5}

Trois remarques sur cet affichage. notes["Farid"] donne bien 5,5 sans qu'aucune fonction ait été écrite. len(notes) donne le nombre de couples, pas le nombre de clés plus le nombre de valeurs: dix étudiants, dix couples. Et print(notes) réaffiche le dictionnaire entier dans le format que vous avez tapé, avec des apostrophes simples autour des chaînes — Python préfère 'Alice' à "Alice" quand il affiche, les deux écritures étant équivalentes en Python (chapitre 5).

Comme la liste, le dictionnaire peut être écrit sur plusieurs lignes: Python considère que l'instruction continue tant que l'accolade ouvrante n'a pas été refermée, ce qui autorise l'alignement ci-dessus et le rend lisible.

Le dictionnaire vide s'écrit {}, et on le remplit ensuite par affectation.

inventaire = {}                 # dictionnaire vide
print(inventaire, len(inventaire))

inventaire["pommes"] = 12       # la cle n'existe pas: elle est creee
inventaire["poires"] = 5
inventaire["pommes"] = 15       # la cle existe: valeur remplacee
print(inventaire)

{} 0
{'pommes': 15, 'poires': 5}

Une seule et même instruction, inventaire["pommes"] = …, fait deux choses différentes selon que la clé est déjà là ou non: elle crée le couple la première fois, elle remplace la valeur ensuite. Il n'y a jamais deux clés "pommes" dans un dictionnaire. Nous reviendrons sur ce point, qui est à la fois la grande commodité du dictionnaire et le piège où tombent les débutants qui croyaient accumuler des valeurs.

Quand la clé n'existe pas

Demandez une clé absente, et Python s'arrête. Voici le programme, dans un fichier nommé carnet.py, et l'erreur exacte qu'il produit.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

print(notes["Zoe"

Traceback (most recent call last):
  File "carnet.py", line 5, in <module>
    print(notes["Zoe"])
          ~~~~~^^^^^^^
KeyError: 'Zoe'

Lisons-la ligne à ligne, comme le chapitre 1 l'a appris. Traceback (most recent call last) annonce la pile des appels, ici réduite à un seul niveau. File "carnet.py", line 5, in <module> donne le fichier et la ligne fautive — Python affiche en réalité le chemin complet du fichier, que nous abrégeons ici. in <module> signifie: dans le corps du programme, hors de toute fonction. Vient ensuite la ligne elle-même, puis une ligne de soulignement: les ~ marquent l'expression évaluée, les ^ le morceau précis qui a échoué, c'est-à-dire l'indexation ["Zoe"]. Enfin, KeyError: 'Zoe' nomme le type de l'erreur et la clé coupable.

KeyError n'a pas d'équivalent exact chez les listes: une liste signale IndexError quand l'indice dépasse sa longueur. Les deux disent la même chose — «cet accès ne correspond à rien» — mais KeyError vous donne en prime la clé qui manquait, ce qui est souvent tout ce dont vous avez besoin pour comprendre.

La méthode get et sa valeur par défaut

Il arrive qu'une clé absente ne soit pas une anomalie mais un cas prévu: on demande la note d'un étudiant qui n'a pas encore passé l'examen, le stock d'un article jamais commandé, le nombre d'occurrences d'un mot pas encore rencontré. Arrêter le programme serait absurde. La méthode get répond alors sans protester.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

print(notes.get("Farid"

5.5
None
0.0
5.5

Trois choses à retenir. Avec un seul argument, get rend None quand la clé manque — None est la valeur spéciale «rien» du chapitre 4, celle que rend aussi une fonction sans return. Avec un deuxième argument, get rend cette valeur-là à la place de None: c'est la valeur par défaut. Et — dernière ligne — la valeur par défaut est ignorée quand la clé existe: get ne remplace jamais une valeur présente.

Notez aussi ce que get ne fait pas: il ne modifie pas le dictionnaire. Après notes.get("Zoe", 0.0), la clé "Zoe" n'a pas été créée, notes a toujours dix couples. C'est une lecture, pas une écriture.

Tester la présence d'une clé

L'opérateur in, que le chapitre 6 utilisait sur les listes, fonctionne sur les dictionnaires — mais il porte sur les clés, pas sur les valeurs.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

print("Hugo"

True
False
False
True

La troisième ligne est celle qui surprend: Hugo a bien 3,0, et pourtant 3.0 in notes est False. C'est correct: in sur un dictionnaire demande «existe-t-il une clé égale à 3.0?», et il n'y en a pas — les clés sont des noms. Pour interroger les valeurs, il faut le dire, avec notes.values().

Ce n'est pas seulement une question de sens: c'est aussi une question de coût. Chercher parmi les clés est immédiat; chercher parmi les valeurs oblige Python à les parcourir toutes, exactement comme une liste. Nous y reviendrons.

Modifier un dictionnaire

Ajouter, remplacer, supprimer

Un dictionnaire est mutable, comme une liste (chapitre 6) et contrairement à un tuple ou à une chaîne: on le modifie en place, sans en fabriquer un nouveau.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

notes["Chloe"] 

11 4.0 5.5
10 False

del d[cle] supprime le couple entier — la clé et sa valeur. Si la clé n'existe pas, del lève un KeyError, tout comme une lecture.

La méthode pop fait la même chose, mais elle rend la valeur supprimée, ce qui est commode quand on veut la réutiliser; et comme get, elle accepte une valeur par défaut qui la dispense de protester.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

partie = dict

3.0 9
None
10

La ligne partie = dict(notes) mérite un mot. Le chapitre 6 a montré, sur les listes, que liste2 = liste1 ne copie rien: les deux noms désignent le même objet, et modifier l'un modifie l'autre. Les dictionnaires ont exactement le même comportement, pour exactement la même raison. dict(notes) — ou notes.copy(), qui fait la même chose — construit un nouveau dictionnaire contenant les mêmes couples, et c'est pourquoi len(notes) vaut toujours 10 à la fin.

Affecter une clé absente la crée

Voici la différence la plus importante entre un dictionnaire et une liste, et elle n'est pas là où on l'attend. Sur une liste, écrire à un indice qui n'existe pas est une erreur:

liste = [4.5, 5.0, 3.5]
liste[7] = 6.0        # l'indice 7 n'existe pas

Traceback (most recent call last):
  File "liste_vs_dict.py", line 2, in <module>
    liste[7] = 6.0        # l'indice 7 n'existe pas
    ~~~~~^^^
IndexError: list assignment index out of range

C'est cohérent: une liste de trois éléments n'a pas de septième case, et Python refuse d'en inventer quatre au passage. Un dictionnaire, lui, n'a pas de «cases» en ce sens; ses clés n'ont aucune raison de se suivre. Écrire d["Karim"] = 5.5 sur une clé absente est donc parfaitement légitime, et crée le couple.

Ce qui peut servir de clé

Hachable, c'est-à-dire immuable en pratique

Une valeur, dans un dictionnaire, peut être n'importe quoi: un nombre, une chaîne, une liste, un autre dictionnaire. Une clé, non. Python exige qu'une clé soit hachable (hashable): qu'il puisse en calculer un petit résumé numérique, son hachage, et que ce résumé ne change jamais tant que l'objet vit. C'est ce résumé qui permet à Python de retrouver la valeur sans parcourir le dictionnaire — nous y reviendrons en parlant de vitesse.

En pratique, la règle à retenir est courte: les objets immuables sont hachables, les objets mutables ne le sont pas. Sont donc acceptés comme clés les entiers, les flottants, les booléens, les chaînes de caractères et les tuples — pour autant que le tuple ne contienne lui-même que des objets hachables. Sont refusées les listes, les dictionnaires et les ensembles.

groupes = {}
groupes[("Alice", "Bruno")] = "TP 1"      # un tuple: accepte
groupes[42] = "salle 42"                  # un entier: accepte
groupes[True] = "oui"                     # un booleen: accepte
print(groupes)

{('Alice', 'Bruno'): 'TP 1', 42: 'salle 42', True: 'oui'}

Un tuple de deux noms comme clé est un usage courant et parfaitement idiomatique: il permet d'indexer une table à deux entrées, resultats[("Alice", "Analyse")] = 5.5, là où deux dictionnaires imbriqués seraient plus lourds.

L'erreur, en vrai

Essayons avec une liste, dans un fichier groupes.py.

groupes = {}
groupes[["Alice", "Bruno"]] = "TP 1"      # une liste: refuse

Traceback (most recent call last):
  File "groupes.py", line 2, in <module>
    groupes[["Alice", "Bruno"]] = "TP 1"      # une liste: refuse
    ~~~~~~~^^^^^^^^^^^^^^^^^^^^
TypeError: unhashable type: 'list'

Le message est d'une précision rare: unhashable type: 'list', «type non hachable: liste». Ce n'est pas un KeyError — la clé n'a même pas été cherchée; c'est un TypeError, une erreur de type, parce que l'objet proposé ne peut pas être une clé.

Pourquoi ce refus? Parce qu'une liste est modifiable. Supposez que Python l'accepte: vous rangez la valeur "TP 1" à l'emplacement calculé à partir de ["Alice", "Bruno"], puis vous ajoutez "Chloe" à cette liste. L'objet a changé, son résumé aussi, et le dictionnaire cherche désormais votre valeur à un endroit où elle n'est pas. Le couple serait devenu introuvable alors même que vous tenez la clé en main. Plutôt que de laisser cette incohérence s'installer, Python refuse dès le départ. Le tuple, lui, ne peut plus changer une fois créé: son résumé est stable pour toujours, donc il fait une clé sûre.

Parcourir un dictionnaire

Les trois vues

Boucler directement sur un dictionnaire parcourt ses clés. Trois méthodes donnent accès aux trois lectures possibles: keys() pour les clés, values() pour les valeurs, items() pour les couples.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

for cle in

Alice Bruno Chloe David Elena Farid Gaelle Hugo Ines Jonas 
['Alice', 'Bruno', 'Chloe', 'David', 'Elena', 'Farid', 'Gaelle', 'Hugo', 'Ines', 'Jonas']
[4.5, 5.0, 3.5, 6.0, 4.0, 5.5, 4.5, 3.0, 5.0, 4.5]

Remarquez que for cle in notes et for cle in notes.keys() font exactement la même chose; la première forme est plus courte et c'est celle qu'on écrit. Remarquez aussi le list(...) autour de notes.keys(): sans lui, l'affichage est différent.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5}
print(notes.keys())
print(notes.values())
print(notes.items())

dict_keys(['Alice', 'Bruno', 'Chloe'])
dict_values([4.5, 5.0, 3.5])
dict_items([('Alice', 4.5), ('Bruno', 5.0), ('Chloe', 3.5)])

keys() ne rend pas une liste mais une vue (view) sur le dictionnaire: un objet qui sait se parcourir et qui reflète le dictionnaire en direct, sans en recopier le contenu. C'est ce que l'affichage dict_keys([...]) indique. Une vue se parcourt avec for, se compte avec len, se teste avec in — tout ce dont on a besoin la plupart du temps. Quand vous avez vraiment besoin d'une liste (pour l'indexer, la trier en place, ou la figer avant de modifier le dictionnaire), écrivez list(notes.keys()).

items et le déballage

La forme que vous écrirez le plus souvent est celle-ci, et elle vaut d'être comprise plutôt que copiée:

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

print(list

('Alice', 4.5)
Bruno a 5.0
David a 6.0
Farid a 5.5
Ines a 5.0

La première ligne montre ce que items() produit réellement: une suite de tuples de deux éléments. La boucle s'appuie alors sur le déballage (unpacking) du chapitre 6: écrire for nom, note in ... quand les éléments sont des couples revient à écrire nom, note = couple à chaque tour. On aurait pu s'en passer:

for couple in notes.items():
    nom = couple[0]
    note = couple[1]

mais la forme déballée dit ce qu'elle fait et évite deux lignes de bruit à chaque boucle. C'est l'écriture idiomatique; adoptez-la.

L'ordre des clés

Les clés d'un dictionnaire n'ont pas d'indice, et pourtant l'affichage ci-dessus sort Alice, Bruno, Chloé… dans l'ordre où elles ont été écrites. Ce n'est pas une coïncidence.

Les deux motifs qui justifient le chapitre

Tout le reste de ce chapitre peut s'oublier. Ces deux programmes-là, non: ils reviennent dans à peu près tout ce que l'on écrit ensuite, du traitement de texte à l'analyse de données.

Compter

Le problème: on a une suite d'objets — les caractères d'un mot, les mots d'une phrase, les codes postaux d'un fichier — et on veut savoir combien de fois chacun apparaît. Une liste ne convient pas: on ne sait pas à l'avance quelles valeurs vont se présenter, donc on ne peut pas réserver une case par valeur. Un dictionnaire, lui, crée ses clés à la demande.

La version longue, écrite avec les outils que vous avez déjà:

# La version longue: on teste si la cle est deja la
frequences = {}
for caractere in "ananas":
    if caractere in frequences:
        frequences[caractere] = frequences[caractere] + 1
    else:
        frequences[caractere] = 1
print(frequences)

{'a': 3, 'n': 2, 's': 1}

Elle est correcte et parfaitement lisible. Mais remarquez ce que fait le else: il donne à une clé nouvelle sa valeur de départ, 1, c'est-à-dire 0 plus 1. Autrement dit, les deux branches font la même chose — «ancienne valeur plus un» — et ne diffèrent que par ce qu'est l'ancienne valeur d'une clé absente. Or get sait précisément fournir cette valeur-là.

# La version idiomatique: get fournit le 0 de depart
frequences = {}
for caractere in "ananas":
    frequences[caractere] = frequences.get(caractere, 0) + 1
    print(caractere, frequences)

a {'a': 1}
n {'a': 1, 'n': 1}
a {'a': 2, 'n': 1}
n {'a': 2, 'n': 2}
a {'a': 3, 'n': 2}
s {'a': 3, 'n': 2, 's': 1}

Une ligne au lieu de cinq, et le print dans la boucle montre la construction pas à pas. Cette ligne mérite d'être décortiquée, car elle en fait beaucoup:

1. frequences.get(caractere, 0) lit le compte actuel du caractère, ou 0 s'il n'a jamais été vu;
2. + 1 ajoute la rencontre en cours;
3. frequences[caractere] = ... range le résultat, en créant la clé si elle n'existait pas.

C'est exactement la conjonction de deux propriétés vues plus haut — la valeur par défaut de get, et le fait qu'affecter une clé absente la crée — qui rend cette ligne possible. Retenez-la sous cette forme:

compteur[cle] = compteur.get(cle, 0) + 1

Le même motif s'applique mot à mot, en découpant d'abord la phrase avec split() (chapitre 5).

phrase = "le chat dort le chien dort le chat mange"
mots = phrase.split()
print(len(mots))

comptes = {}
for mot in mots:
    comptes[mot] = comptes.get(mot, 0) + 1
print(comptes)

9
{'le': 3, 'chat': 2, 'dort': 2, 'chien': 1, 'mange': 1}

Neuf mots, cinq mots distincts. Une fois ce dictionnaire construit, chercher le mot le plus fréquent est une boucle de maximum comme celles du chapitre 3, à ceci près qu'on retient deux choses: le meilleur score et la clé qui l'a obtenu.

comptes = {"le": 3, "chat": 2, "dort": 2, "chien": 1, "mange": 1}

mot_max = ""
compte_max = 0
for mot, compte in comptes.items():
    if compte > compte_max:     # strict: le premier atteint gagne
        compte_max = compte
        mot_max =

le 3

Regrouper

Le second motif répond à une question différente: non plus «combien de fois?» mais «lesquels?». On veut, pour chaque catégorie, la liste des éléments qui y tombent. La valeur associée à une clé n'est alors plus un nombre mais une liste, que l'on allonge à chaque rencontre.

La difficulté est la même qu'au comptage, et se résout de la même façon: la première fois qu'une catégorie apparaît, il n'y a pas encore de liste à allonger, il faut la créer.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

groupes = {}

{'reussi': ['Alice', 'Bruno', 'David', 'Elena', 'Farid', 'Gaelle', 'Ines', 'Jonas'], 'echoue': ['Chloe', 'Hugo']}
8 sur 10

Huit étudiants sur dix ont la moyenne, et on sait maintenant lesquels, ce qui est le progrès décisif par rapport au simple compteur. La ligne clé est groupes[categorie].append(nom): elle lit la liste associée à la catégorie, puis lui ajoute le nom. Comme les listes sont mutables (chapitre 6), append modifie la liste en place, et il n'y a rien à ré-affecter dans le dictionnaire — la liste rangée dans groupes et celle que l'on vient d'allonger sont le même objet.

Le test if categorie not in groupes suivi de la création peut se contracter avec la méthode setdefault, qui rend la valeur associée à une clé en la créant au passage si elle manque — l'exact analogue de get, mais qui écrit au lieu de seulement lire.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

par_tranche = {}

{4: ['Alice', 'Elena', 'Gaelle', 'Jonas'], 5: ['Bruno', 'Farid', 'Ines'], 3: ['Chloe', 'Hugo'], 6: ['David']}
3 2 ['Chloe', 'Hugo']
4 4 ['Alice', 'Elena', 'Gaelle', 'Jonas']
5 3 ['Bruno', 'Farid', 'Ines']
6 1 ['David']

Deux observations. La première: les clés du dictionnaire sortent dans l'ordre 4, 5, 3, 6 — l'ordre d'insertion, puisque Alice, avec 4,5, a été rencontrée en premier. La boucle finale les remet en ordre croissant grâce à sorted(par_tranche), qui trie les clés. La seconde: int(note) tronque vers zéro, il n'arrondit pas — int(4.5) vaut 4, pas 5. C'est exactement ce qu'il faut ici, où l'on veut la tranche [4; 5[, mais c'est une confusion classique à laquelle le chapitre 1 vous a déjà exposé avec la division entière //.

L'explorateur: voir le dictionnaire se construire

Le motif de comptage est plus facile à voir qu'à lire. L'explorateur ci-dessous reprend le mot du chapitre et laisse le curseur avancer, caractère par caractère, dans la boucle for. À chaque position, le dictionnaire est reconstruit depuis le début du texte et affiché sous forme de barres, une barre par clé, dans l'ordre d'insertion.

Faites-le glisser lentement et regardez deux choses. D'une part, quand une barre apparaît: c'est le moment où get a rendu 0, donc où une lettre est rencontrée pour la première fois; toutes les fois suivantes, la barre monte d'un cran sans qu'aucune clé ne s'ajoute. D'autre part, le décrochage des deux compteurs: la somme des valeurs suit exactement le nombre de caractères traités, du premier au dernier, alors que le nombre de clés distinctes progresse de plus en plus lentement. Sur ce mot-là, huit des onze clés sont créées dans les douze premiers caractères; les trois dernières n'arrivent qu'aux positions 18, 19 et 22 (le e, le l, le m), et les trois derniers caractères, e, n et t, ne font plus que monter des barres existantes. C'est toute la différence entre compter des occurrences et compter des catégories.

Dictionnaires en compréhension

Le chapitre 6 a introduit les listes en compréhension, qui construisent une liste en une expression au lieu d'une boucle. Les dictionnaires ont la même écriture, avec des accolades et un cle: valeur avant le for.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

carres = {n: n 

{1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
{'Alice': 5, 'Bruno': 5, 'Chloe': 5, 'David': 5, 'Elena': 5, 'Farid': 5, 'Gaelle': 6, 'Hugo': 4, 'Ines': 4, 'Jonas': 5}
8

La structure est toujours la même: {expression_de_cle: expression_de_valeur for variables in source}, avec un if optionnel à la fin qui filtre. La troisième ligne est le cas le plus utile en pratique — sélectionner un sous-dictionnaire — et redonne bien les huit étudiants qui ont la moyenne.

Attention cependant à une compréhension qui paraît anodine: inverser un dictionnaire, en échangeant clés et valeurs.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0,
         "Ines": 5.0, "Jonas": 4.5}

inverse = {note: nom 

7
{4.5: 'Jonas', 5.0: 'Ines', 3.5: 'Chloe', 6.0: 'David', 4.0: 'Elena', 5.5: 'Farid', 3.0: 'Hugo'}

Dix étudiants entrent, sept couples sortent. La raison est celle du début du chapitre: une clé n'apparaît qu'une fois. Alice, Gaëlle et Jonas ont tous 4,5; les trois écrivent successivement dans la clé 4.5, et la dernière écriture gagne. Jonas n'est pas «le» titulaire du 4,5, il est simplement le dernier de la liste. Trois étudiants ont disparu sans le moindre avertissement.

Les ensembles

Un dictionnaire dont on aurait retiré les valeurs

Il arrive qu'on ne veuille associer aucune valeur aux clés et se contenter de savoir ce qui est là: quels étudiants ont rendu la série, quels mots apparaissent dans un texte, quels codes ont déjà été attribués. C'est ce que fait un ensemble (set).

Les deux propriétés — unicité et absence d'ordre — vont de pair avec la troisième, qui est la raison d'être de la structure: tester l'appartenance ne coûte pas un parcours, exactement comme pour les clés d'un dictionnaire. Un ensemble est, littéralement, un dictionnaire auquel on a enlevé les valeurs.

notes_liste = [4.5, 5.0, 3.5, 6.0, 4.0, 5.5, 4.5, 3.0, 5.0, 4.5]

distinctes = set(notes_liste)
print(len(notes_liste), len(distinctes))
print(sorted(distinctes))

lettres = set("ananas")
print

10 7
[3.0, 3.5, 4.0, 4.5, 5.0, 5.5, 6.0]
3 ['a', 'n', 's']

set(quelque_chose) construit un ensemble à partir de n'importe quelle collection parcourable: une liste, une chaîne, un tuple, les clés d'un dictionnaire. Les répétitions disparaissent en chemin, et c'est de loin la manière la plus courte de dédoublonner une liste. Dix notes, sept valeurs distinctes; six lettres dans «ananas», trois distinctes.

Ajouter et retirer

inscrits = set()                 # un ensemble vide
inscrits.add("Alice")
inscrits.add("Bruno")
inscrits.add("Alice")            # deja present: aucun effet
print(len(inscrits), sorted(inscrits))

inscrits.discard("Chloe")        # absente: discard ne dit rien
print(sorted(inscrits))

2 ['Alice', 'Bruno']
['Alice', 'Bruno']

add ajoute un élément, ou ne fait rien s'il est déjà là — c'est le comportement souhaité dans la quasi-totalité des cas, et il dispense du if ... not in ... que l'on écrirait avec une liste. Pour retirer, deux méthodes: discard ne proteste jamais, remove exige que l'élément soit présent. Dans un fichier inscription.py:

inscrits = {"Alice", "Bruno"}
inscrits.remove("Chloe")         # absente: remove proteste

Traceback (most recent call last):
  File "inscription.py", line 2, in <module>
    inscrits.remove("Chloe")         # absente: remove proteste
    ~~~~~~~~~~~~~~~^^^^^^^^^
KeyError: 'Chloe'

C'est un KeyError, le même que pour un dictionnaire — la parenté des deux structures se voit jusque dans les messages d'erreur. Le choix entre les deux méthodes suit la même logique que celui entre d[cle] et get: remove quand l'absence serait un bogue, discard quand elle est normale.

Les quatre opérations

C'est ici que les ensembles paient. Les quatre opérations de la théorie des ensembles sont directement des opérateurs Python, et chacune remplace une boucle que vous auriez écrite à la main.

a = {1, 2, 3, 4}
b = {3, 4, 5}

print(sorted(a | b))       # union
print(sorted(a & b))       # intersection
print(sorted(a - b))       # difference
print(sorted(b 

[1, 2, 3, 4, 5]
[3, 4]
[1, 2]
[5]
[1, 2, 5]

• a | b, l'union: les éléments qui sont dans a, dans b, ou dans les deux. Une barre verticale, le même symbole que le «ou» de certains langages.
• a & b, l'intersection: les éléments présents dans les deux à la fois.
• a - b, la différence: les éléments de a qui ne sont pas dans b. C'est la seule des quatre qui ne soit pas symétrique, et la quatrième ligne le montre: a - b donne [1, 2], b - a donne [5].
• a ^ b, la différence symétrique: les éléments qui sont dans exactement un des deux ensembles. C'est l'union moins l'intersection, ou encore (a - b) | (b - a).

Pourquoi les accolades vides donnent un dictionnaire

Une bizarrerie de syntaxe, qu'il vaut mieux connaître que découvrir.

vide_dict = {}
vide_ens = set()

print(type(vide_dict))
print(type(vide_ens))
print(type({1, 2, 3}))
print(type({"a": 1}))
print(len(vide_dict), len(vide_ens))

<class 'dict'>
<class 'set'>
<class 'set'>
<class 'dict'>
0 0

Les accolades servent aux deux structures, et Python les distingue à ce qu'il y a dedans: des couples cle: valeur pour un dictionnaire, des éléments seuls pour un ensemble. Vides, les accolades sont ambiguës — et la question a été tranchée en faveur du dictionnaire, tout simplement parce que les dictionnaires existaient dans le langage avant les ensembles. L'ensemble vide s'écrit donc set(), et seulement ainsi. Si un for sur ce que vous croyiez être un ensemble vide se met à vous rendre des clés, ou si un add vous répond AttributeError: 'dict' object has no attribute 'add', c'est cette ligne-là qu'il faut aller relire.

Pourquoi c'est rapide

Ce que coûte un parcours

Reprenons la fonction note_de du début du chapitre. Pour trouver un nom, elle compare les clés une à une. Sur une liste de $n$ couples, elle fait au mieux une comparaison — si le nom cherché est en tête — et au pire $n$, quand le nom est en queue ou absent. En moyenne, sur un nom présent tiré au hasard, environ $n/2$. Le point important n'est pas la constante mais la proportionnalité: doubler la taille de la liste double le travail de chaque recherche.

Un dictionnaire ne procède pas ainsi. À partir de la clé, il calcule — c'est le hachage dont nous parlions — un emplacement dans une table interne, et va regarder directement à cet emplacement. Ce calcul ne dépend pas du nombre de couples rangés: il coûte à peu près la même chose dans un dictionnaire de dix clés et dans un dictionnaire d'un million. On dit que l'accès se fait en temps constant, par opposition au temps proportionnel du parcours. Les ensembles fonctionnent de la même manière — ce sont les mêmes tables, sans les valeurs.

La mesure

Une affirmation sur la vitesse doit se mesurer, pas se croire. Le module time de la bibliothèque standard fournit perf_counter(), qui rend un nombre de secondes: la différence entre deux appels donne la durée de ce qui s'est passé entre les deux.

Ce programme emprunte une notion au chapitre 8: la ligne import time charge un module, c'est-à-dire un fichier de fonctions déjà écrites, et time.perf_counter() appelle l'une d'elles. L'importation et les modules sont le sujet du chapitre 8; retenez seulement, pour l'instant, que cette ligne met perf_counter à votre disposition. Rien d'autre dans ce chapitre n'en dépend, et une mesure inventée ne vaudrait rien: c'est pour cela que nous faisons l'emprunt plutôt que de citer un chiffre de mémoire.

import time

taille = 100000
grande_liste = list(range(taille))
grand_ensemble = set(grande_liste)
cible = taille - 1               # le pire cas: le dernier element

debut = time.perf_counter()
for i in range(1000):
    trouve = cible in grande_liste
t_liste = (time.perf_counter() - debut) 

834.1 microsecondes (liste)
0.085 microsecondes (ensemble)
9833 fois plus lent

Voilà le résultat d'une exécution réelle, sur un ordinateur portable ordinaire, avec Python 3.13. Chaque recherche dans la liste de 100 000 éléments a coûté environ 834 microsecondes, chaque recherche dans l'ensemble environ 0,085 microseconde.

Deux honnêtetés s'imposent. D'abord, ces nombres sont propres à la machine: sur la vôtre ils seront différents, et sur la même machine ils varient d'une exécution à l'autre. En relançant ce programme une douzaine de fois, la liste a donné entre 610 et 1550 microsecondes par recherche, et l'ensemble entre 0,059 et 0,10: le rapport observé allait de 8 400 à 16 000. Ne retenez donc pas «9 833 fois», retenez «quatre ordres de grandeur, sur cette taille-là». Ensuite, le temps mesuré pour l'ensemble inclut le coût de la boucle for elle-même, qui est du même ordre que la recherche: le rapport mesuré sous-estime l'avantage réel. C'est la direction prudente, et cela suffit à la démonstration.

Ce qui se passe quand on change la taille

Le rapport brut est spectaculaire mais il dépend de la taille choisie. Le vrai enseignement est ailleurs: dans la façon dont chaque durée évolue quand la collection grandit.

import time

def duree_par_recherche(collection, cible, essais):
    """Duree moyenne d'un test d'appartenance, en microsecondes."""
    debut = time.perf_counter()
    for i in range(essais):
        trouve = cible in collection
    return (time.perf_counter() - debut) / essais * 1000000

for taille in [10000, 100000, 1000000]:
    liste = list

10000 60.5 0.027
100000 684.8 0.03
1000000 7609.1 0.033

Lisez les colonnes. La liste: 61 microsecondes, puis 685, puis 7609 — chaque multiplication de la taille par dix multiplie la durée par une dizaine, ce qui est exactement le comportement proportionnel annoncé. L'ensemble: 0,027, puis 0,030, puis 0,033 — aucune tendance, seulement le bruit de la mesure. Cent fois plus d'éléments n'ont rien coûté du tout.

C'est cela, et non le facteur de dix mille, qu'il faut emporter: le coût de la recherche dans une liste suit la taille, celui de la recherche dans un ensemble ou un dictionnaire ne la suit pas. Sur une collection de dix éléments, la différence est invisible et le choix de la structure n'a aucune importance. Sur une collection de cent mille, elle décide qu'un programme réponde en une seconde ou en trois heures.

Choisir la bonne structure

Vous connaissez maintenant quatre façons de ranger plusieurs valeurs dans une variable. Le tableau ci-dessous est le résumé pratique de ce cours: il se lit par la question «qu'est-ce que je fais de ces données?», qui est la bonne question, et non par «comment sont-elles faites?».

Quelques règles de décision qui en découlent, dans l'ordre où on se les pose:

1. Chaque donnée porte-t-elle un identifiant naturel — un nom, un numéro, un code, un mot? Si oui, dictionnaire, et la question est réglée. C'est le cas du carnet de notes, d'un annuaire, d'un stock, d'un compteur d'occurrences.
2. Sinon, ai-je seulement besoin de savoir ce qui est présent, sans ordre et sans répétition? Si oui, ensemble. C'est le cas des étudiants inscrits, du vocabulaire d'un texte, des identifiants déjà attribués.
3. Sinon, l'ordre compte-t-il, ou les répétitions? Si oui, liste. C'est le cas d'une suite de mesures, d'un historique, d'une file d'attente.
4. Ces données doivent-elles être protégées contre toute modification, ou servir de clé de dictionnaire? Si oui, tuple. C'est le cas d'une coordonnée (x, y), d'une date (annee, mois, jour), d'un couple (nom, matiere) servant de clé.

Rien n'interdit de combiner: une liste de dictionnaires est la forme habituelle d'un tableau de données lu dans un fichier (chapitre 8), un dictionnaire de listes est ce que produit le motif de regroupement, et un dictionnaire dont les valeurs sont des ensembles décrit très bien «pour chaque cours, l'ensemble des étudiants inscrits».

Le carnet de notes, enfin complet

Fermons la boucle ouverte au chapitre 3. Voici le programme qui, en un seul parcours du dictionnaire, calcule tout ce que l'on veut savoir du carnet — et qui, cette fois, peut nommer les étudiants concernés.

Synthèse

• Un dictionnaire associe des clés à des valeurs et retrouve une valeur à partir de sa clé sans rien parcourir, là où une liste de couples doit comparer les éléments un à un. C'est l'aboutissement du fil rouge du cours: le chapitre 3 additionnait dix nombres, le chapitre 6 les rangeait dans une liste, le chapitre 7 leur rend enfin leur nom.
• On lit avec d[cle] quand l'absence est un bogue — elle lève un KeyError qui nomme la clé manquante — et avec d.get(cle, defaut) quand elle est normale. On écrit avec d[cle] = valeur, qui crée la clé si elle manque, contrairement à une liste dont un indice inexistant lève IndexError. in porte sur les clés, del et pop suppriment.
• Une clé doit être hachable, donc en pratique immuable: nombre, chaîne, booléen ou tuple. Une liste en clé lève TypeError: unhashable type: 'list', parce qu'un objet modifiable rendrait la valeur associée introuvable après modification.
• On parcourt avec for cle in d, d.keys(), d.values() et surtout for cle, valeur in d.items(). Depuis Python 3.7 (et de fait depuis CPython 3.6), l'ordre d'insertion des clés est garanti par le langage — mais «ordonné» ne veut pas dire «trié»: pour l'ordre alphabétique, il faut sorted(d).
• Les deux motifs à savoir écrire de mémoire sont le comptage, compteur[cle] = compteur.get(cle, 0) + 1, et le regroupement, groupes.setdefault(cle, []).append(element) — dont la variante fautive groupes[cle] = element écrase au lieu d'accumuler, sans lever la moindre erreur.
• Un ensemble est un dictionnaire sans valeurs: éléments uniques, aucun ordre, appartenance immédiate, et les quatre opérations |, &, -, ^. L'ensemble vide s'écrit set(), car {} est un dictionnaire vide; et un ensemble s'affiche toujours trié, son ordre interne n'étant pas reproductible.
• Mesuré sur cette machine, un test d'appartenance dans une liste de 100 000 entiers a coûté environ 834 microsecondes contre 0,085 pour le même test dans un ensemble; et surtout, multiplier la taille par dix multiplie la durée de la liste par dix sans rien changer à celle de l'ensemble. Ces durées dépendent de la machine; la loi d'évolution, non.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

annuaire = {"Alice": "021 693 11 11", "Bruno": "022 379 71 11"}
annuaire["Chloe"] = "032 718 11 11"       # ajout
annuaire["Bruno"] =

def compter_voyelles(phrase):
    """Rend le dictionnaire des voyelles et de leur nombre."""
    voyelles = "aeiouy"
    comptes = {}
    for caractere in phrase.lower():
        if caractere in voyelles:
            comptes[caractere] = comptes.get(caractere, 

def regrouper_par_longueur(mots):
    """Regroupe les mots par leur nombre de caracteres."""
    groupes = {}
    for mot in mots:
        taille = len(mot)
        if taille not in groupes:
            groupes[taille] = []

phrase1 = "le chat dort sur le tapis du salon"
phrase2 = "le chien dort sur le tapis de la cuisine"

mots1 = set(phrase1.split())
mots2 = set(phrase2.split())

print(len(mots1), len(mots2))
print(

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0,
         "Elena": 4.0, "Farid": 

Références

• Downey, A., Think Python, 3e éd., O'Reilly, chapitres sur les dictionnaires et les tuples (édition en accès libre; une traduction française existe).
• Swinnen, G., Apprendre à programmer avec Python 3, Eyrolles, Paris, chapitre sur les dictionnaires (édition en accès libre).
• Matthes, E., Python Crash Course, 3e éd., No Starch Press, San Francisco, chapitre «Dictionaries».
• Guttag, J. V., Introduction to Computation and Programming Using Python, MIT Press, Cambridge, chapitre sur les structures de données et leur coût.
• Documentation officielle Python, The Python Standard Library, section «Mapping Types — dict» et section «Set Types — set, frozenset» (docs.python.org).
• Tutoriel officiel Python, section «Data Structures», sous-sections sur les dictionnaires, les ensembles et les compréhensions (docs.python.org).