Skip to main content Informatique en prépa - Lycée Malherbe 

5- Dictionnaires

Une liste associe des valeurs à des indices Un dictionnaire associe des valeurs à des clés de (presque) n'importe quel type : des chaînes de caractères, des nombres, des tuples...

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.

cluster_liste  liste : indice → valeur   cluster_dico  dictionnaire : clé → valeur   L 0 "Paris" 1 "Rome" 2 "Tokyo" D "France" "Paris" "Italie" "Rome" "Japon" "Tokyo"

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 :

Python

Loading editor...

capitales = {"France": "Paris", "Italie": "Rome", "Japon": "Tokyo"}

print(capitales["Italie"])
print(len(capitales))   # le nombre de couples clé / valeur

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

Python

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 :

Python

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 :

Python

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

Python

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 :

d1 d1 A "a" "b" 1 2 d1->A d2 d2 d2->A d3 d3 B "a" 1 d3->B

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.

Python

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 :

Python

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 :

Python

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 :

Voici l'évolution du dictionnaire occurrences sur la liste ["pomme", "poire", "pomme", "kiwi"] :

élément ludé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}
Python

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 :

Python

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 , quelle que soit la taille du dictionnaire.

Au contraire, le test x in L sur une liste parcourt la liste : il est en temps linéaire, . Python ne sait pas où se trouve 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 :

Python
code masqué : pas besoin de le lire pour suivre, exécutez-le simplement
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 x est 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.

Python

Loading editor...

def inverse(d):
    resultat = {}
    for (cle, valeur) in d.items():
        resultat[valeur] = cle
    return resultat
Exercice 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.

Python

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.

Python

Loading editor...

Vérification : notes_par_eleve
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
def notes_par_eleve(L):
    resultat = {}
    for (eleve, note) in L:
        if eleve not in resultat:
            resultat[eleve] = []
        resultat[eleve].append(note)
    return resultat