5- Dictionnaires
Une liste associe des valeurs à des indices
On peut imaginer une liste comme une rangée de casiers numérotés : pour retrouver un objet, il faut connaître le numéro de son casier. Un dictionnaire, c'est une rangée de casiers étiquetés : on retrouve un objet grâce à son étiquette, qu'on choisit librement.
Avec la liste, il faut savoir que Rome est dans la case 1. Avec le dictionnaire, on demande directement « la capitale de l'Italie ». C'est le principe d'un vrai dictionnaire (on cherche un mot pour trouver sa définition), d'un répertoire de téléphone (on cherche un nom pour trouver un numéro), etc.
Vocabulaire
- Une clé est ce qui sert à retrouver une information (ici, le pays).
- Une valeur est l'information associée à la clé (ici, la capitale).
- Un dictionnaire est un ensemble de couples clé : valeur. Chaque clé n'apparaît qu'une seule fois ; plusieurs clés différentes peuvent en revanche avoir la même valeur.
I. Utilisation
a) Création et accès
Un dictionnaire s'écrit entre accolades, avec des couples clé: valeur :
Loading editor...
capitales = {"France": "Paris", "Italie": "Rome", "Japon": "Tokyo"}
print(capitales["Italie"])
print(len(capitales)) # le nombre de couples clé / valeurOn accède à la valeur associée à une clé avec des crochets, comme pour une liste. Si la clé n'existe pas, on obtient une erreur :
Loading editor...
print(capitales["Espagne"])
b) Insertion et modification
On ajoute un couple, ou on modifie la valeur associée à une clé, avec une affectation :
Loading editor...
capitales["Espagne"] = "Madrid" # ajout d'une nouvelle clé capitales["Japon"] = "Tokyo (東京)" # modification print(capitales)
Un dictionnaire vide s'écrit {}. On le remplit souvent au fur et à mesure :
Loading editor...
carres = {}
for n in range(1, 6):
carres[n] = n ** 2
print(carres)c) Présence d'une clé
Pour tester si une clé est présente, on utilise in (comme pour les listes) :
Loading editor...
print("France" in capitales)
print("Allemagne" in capitales)
print("Paris" in capitales) # "Paris" est une valeur, pas une clé !d) Copie
Comme les listes, les dictionnaires sont mutables : si deux variables désignent le même dictionnaire, une modification par l'une se voit par l'autre. Pour obtenir un dictionnaire indépendant, on utilise la méthode copy :
Après le code ci-dessous, d1 et d2 sont deux noms pour le même dictionnaire (l'ajout de "b" par d1 se voit donc dans d2), alors que d3 est un autre dictionnaire, créé avant l'ajout.
Loading editor...
d1 = {"a": 1}
d2 = d1 # d2 désigne le même dictionnaire que d1
d3 = d1.copy() # d3 est une copie
d1["b"] = 2
print(d2)
print(d3)II. Parcours
On peut parcourir les clés d'un dictionnaire avec keys, ou les couples (clé, valeur) avec items :
Loading editor...
notes = {"Alice": 15, "Bob": 12, "Chloé": 17}
for nom in notes.keys():
print(nom)
for (nom, note) in notes.items():
print(nom, "a eu", note)for nom in notes: parcourt aussi les clés, comme for nom in notes.keys():.
Par exemple, la moyenne des notes :
Loading editor...
def moyenne(notes):
total = 0
for note in notes.values():
total += note
return total / len(notes)
moyenne(notes)III. Exemple : compter les éléments d'une liste
On veut savoir combien de fois apparaît chaque élément d'une liste. Un dictionnaire associe à chaque élément déjà rencontré son nombre d'apparitions. On parcourt la liste, et pour chaque élément :
- s'il est déjà une clé du dictionnaire, on augmente son compteur de 1 ;
- sinon, on l'ajoute avec un compteur à 1.
Voici l'évolution du dictionnaire occurrences sur la liste ["pomme", "poire", "pomme", "kiwi"] :
| élément lu | déjà présent ? | occurrences après |
|---|---|---|
{} | ||
"pomme" | non | {"pomme": 1} |
"poire" | non | {"pomme": 1, "poire": 1} |
"pomme" | oui | {"pomme": 2, "poire": 1} |
"kiwi" | non | {"pomme": 2, "poire": 1, "kiwi": 1} |
Loading editor...
def compter(L):
occurrences = {}
for x in L:
if x in occurrences:
occurrences[x] += 1
else:
occurrences[x] = 1
return occurrences
compter(["pomme", "poire", "pomme", "kiwi", "pomme", "poire"])On peut ensuite trouver l'élément le plus fréquent :
Loading editor...
def plus_frequent(L):
occurrences = compter(L)
meilleur = None
for (x, n) in occurrences.items():
if meilleur is None or n > occurrences[meilleur]:
meilleur = x
return meilleur
plus_frequent(list("abracadabra"))IV. Coût des opérations
L'intérêt principal des dictionnaires est leur rapidité : l'accès à une valeur, l'insertion, et le test in se font en temps constant (en moyenne), c'est-à-dire en
Au contraire, le test x in L sur une liste parcourt la liste : il est en temps linéaire, x dans la liste : il doit comparer x à chaque élément, un par un, jusqu'à le trouver (ou arriver au bout). Un dictionnaire, lui, « sait » directement dans quel casier regarder à partir de la clé.
Sur le graphique ci-dessous, le temps de recherche dans une liste augmente avec sa taille, alors que celui dans un dictionnaire reste (presque) nul :
Liste ou dictionnaire ?
- Les données sont numérotées dans l'ordre
(une suite de mesures, les cases d'un tableau) : une liste. - On veut retrouver une information à partir d'un nom, d'un mot, d'un identifiant... (des notes par élève, un stock par produit, un nombre d'apparitions par mot) : un dictionnaire.
- On fait beaucoup de tests « est-ce que
xest présent ? » sur beaucoup de données : un dictionnaire, pour la rapidité.
On verra en deuxième année comment les dictionnaires fonctionnent (le hachage), et pourquoi toutes les valeurs ne peuvent pas être des clés : par exemple, une liste ne peut pas être une clé.
Exercices
Exercice 1
Écrire une fonction inverse(d) qui renvoie le dictionnaire "inversé" : à chaque valeur de d, il associe la clé correspondante. On suppose que toutes les valeurs sont différentes.
Loading editor...
def inverse(d):
resultat = {}
for (cle, valeur) in d.items():
resultat[valeur] = cle
return resultatExercice 2
Écrire une fonction anagrammes(m1, m2) qui teste si deux mots sont des anagrammes (ils ont les mêmes lettres, le même nombre de fois), en utilisant la fonction compter.
Loading editor...
def anagrammes(m1, m2):
return compter(m1) == compter(m2) Deux dictionnaires sont égaux (==) s'ils ont les mêmes couples clé / valeur.
Exercice 3
On dispose d'une liste de couples (eleve, note), un même élève pouvant apparaître plusieurs fois. Écrire une fonction notes_par_eleve(L) qui renvoie un dictionnaire associant à chaque élève la liste de ses notes.
Loading editor...
def notes_par_eleve(L):
resultat = {}
for (eleve, note) in L:
if eleve not in resultat:
resultat[eleve] = []
resultat[eleve].append(note)
return resultat