ITC en CPGE · Maths spé PCLes dictionnaires en Python

ITC en CPGE · Maths spé PC

Les dictionnaires en Python

Retrouver une information à partir d’une clé : le nom d’un capteur, une valeur observée ou le degré d’un monôme. Les dictionnaires permettent de représenter ces associations et de construire des traitements efficaces.

Prérequis : listes, tuples, boucles, conditions, fonctions, références à des objets mutables et ordres de grandeur O(1), O(n), O(n²). Aucune bibliothèque Python n’est nécessaire.

Commencer le cours →Ouvrir le bac à sable Python →

Cours · Les bases

Associer une clé à une valeur

Un dictionnaire est une collection mutable de paires clé–valeur. Chaque clé est unique et donne accès à une valeur. Plusieurs clés peuvent avoir la même valeur. Une nouvelle affectation à une clé existante remplace la valeur précédente.

temperatures = {"A": 19.5, "B": 20.0}
print(temperatures["A"])       # 19.5
temperatures["A"] = 21.0       # modification
temperatures["C"] = 18.5       # insertion
print(len(temperatures))       # 3

La clé "A" identifie un capteur ; la valeur 21.0 représente sa température en degrés Celsius.

Liste et dictionnaire

Une liste L représente une suite accessible par des indices : L[i]. Un dictionnaire d associe des informations à des clés : d[cle].

Dans d = {10: "A", 30: "B"}, d[10] vaut "A" et d[0] provoque une erreur. La clé entière 10 ne désigne pas la onzième case. Un dictionnaire ne se découpe pas en tranches comme une liste.

Cours · Syntaxe

Manipuler un dictionnaire

Opérations à connaître

Écriture	Effet ou résultat
d = {}	Créer un dictionnaire vide.
d[cle]	Lire la valeur ; `KeyError` si la clé est absente.
d[cle] = valeur	Insérer une paire ou remplacer sa valeur.
cle in d	Tester la présence de la clé, et non de la valeur.
cle not in d	Tester l’absence de la clé.
len(d)	Obtenir le nombre de paires.
d.copy()	Créer une copie superficielle du dictionnaire.
del d[cle]	Supprimer la paire ; `KeyError` si la clé est absente.

Prévoir une clé absente

if "D" in temperatures:
    valeur = temperatures["D"]
else:
    valeur = 0.0

Complément documenté : d.get(cle, defaut) renvoie la valeur si la clé existe, sinon defaut, sans insérer de clé. get et del sont des compléments de syntaxe dont le sens est fourni dans ce support.

Cours · Parcours

Parcourir les clés et les paires

d = {"A": 19.0, "B": 21.0, "C": 20.0}
for cle in d:                  # équivaut ici à d.keys()
    print(cle, d[cle])

for cle, valeur in d.items():
    print(cle, valeur)

d.keys() fournit une vue sur les clés ; d.items() fournit une vue sur les paires. Le second parcours décompose chaque paire dans deux variables. Les deux boucles affichent les mêmes trois lignes. Une vue reflète le contenu courant du dictionnaire.

total = 0.0
for cle in d:
    total = total + d[cle]
print(total)                    # 60.0

Les dictionnaires conservent l’ordre d’insertion des clés en Python 3.7 et versions suivantes. Cet ordre n’est pas un tri. Deux dictionnaires sont égaux s’ils contiennent les mêmes associations, même si leur ordre d’insertion diffère.

Pour chercher une valeur, on peut parcourir toutes les paires. Le complément d.values() donne une vue sur les valeurs : 19.0 in d.values() vaut True, mais peut nécessiter un parcours complet.

Cours · Objets mutables

Copier et modifier

Comprendre la copie superficielle

a = {"A": [18.0, 19.0]}
b = a
c = a.copy()
b["B"] = [20.0]
c["A"].append(21.0)

# a et b valent :
# {"A": [18.0, 19.0, 21.0], "B": [20.0]}
# c vaut : {"A": [18.0, 19.0, 21.0]}

b = a associe les deux noms au même dictionnaire. c = a.copy() crée un autre dictionnaire, mais les listes déjà présentes restent partagées. Ajouter la clé "B" ne modifie donc pas c ; modifier la liste associée à "A" se voit dans les trois noms.

Modifier pendant un parcours

On peut remplacer les valeurs associées à des clés existantes. En revanche, on évite d’ajouter ou de supprimer des clés dans le dictionnaire que l’on parcourt : l’itération peut échouer ou devenir incorrecte. Pour filtrer, on construit un nouveau dictionnaire.

positifs = {}
for cle in d:
    if d[cle] > 0:
        positifs[cle] = d[cle]

Cours · Hachage et collisions

Comprendre le hachage

Une table de hachage permet de retrouver rapidement l’emplacement associé à une clé. Une fonction de hachage transforme la clé en un entier, utilisé pour déterminer où commencer la recherche. On vérifie ensuite l’égalité des clés pour retrouver la bonne paire.

Des clés différentes peuvent conduire au même emplacement : il y a collision. La structure doit alors départager ces clés. Une collision ne signifie pas que les clés sont égales et ne doit pas entraîner la perte d’une association.

Un modèle simple avec sept cases

On prend des clés entières et la fonction h(k) = k % 7. On range dans chaque case une liste des paires qui y arrivent. Ce modèle par chaînage sert à expliquer les collisions ; il ne reproduit pas l’organisation interne exacte de dict dans CPython.

Case	Paires rangées dans cette case
3	(3, "A"), (10, "B"), (17, "C")
5	(5, "D")
Autres cases	Les cases 0, 1, 2, 4 et 6 sont vides.

Recherche de 17 : on calcule 17 % 7, soit 3, puis on compare les clés de cette case jusqu’à 17. Recherche de 24 : on arrive également en case 3, mais aucune clé n’est égale à 24 ; la clé est absente.

Si les clés sont bien réparties et la table suffisamment dimensionnée, peu de comparaisons suffisent. De nombreuses collisions ralentissent les opérations. Le redimensionnement permet notamment de conserver assez de place.

Cours · Clés

Choisir des clés hachables

Une clé doit être hachable : son hachage reste stable pendant sa présence dans le dictionnaire et des clés égales ont le même hachage. Les valeurs, elles, peuvent être des objets mutables. Pour les types usuels de ce cours :

Candidat	Clé possible	Explication
"capteur_A" ou 12	Oui	Chaîne ou entier.
(2, 5)	Oui	Tuple dont tous les éléments sont hachables.
[2, 5]	Non	Une liste est mutable et non hachable.
("A", [2, 5])	Non	Le tuple contient une liste non hachable.
{"A": 2}	Non	Un dictionnaire est non hachable.

Les flottants sont utilisables comme clés, mais leurs approximations peuvent rendre une recherche fragile. De plus, 1, 1.0 et True sont égaux et désignent la même entrée.

Cours · Complexité

Raisonner sur les coûts

On note n le nombre de paires. Dans le modèle usuel du cours, hachage et comparaison des clés coûtent O(1). Les coûts moyens supposent une bonne répartition des clés ; l’insertion peut aussi provoquer un redimensionnement.

Opération	Coût usuel	Observation
d[cle] et cle in d	O(1) en moyenne	O(n) dans le pire cas.
d[cle] = valeur	O(1) amorti en moyenne	Une opération isolée peut coûter O(n).
del d[cle]	O(1) en moyenne	O(n) dans le pire cas.
len(d)	O(1)	La taille est mémorisée.
Parcours ou copie	O(n)	Le traitement concerne toutes les paires.
Recherche d’une valeur	O(n) au pire	Le hachage porte sur les clés.

Amorti signifie qu’un coût ponctuellement élevé est réparti sur une suite d’opérations. Cela ne garantit pas un coût constant pour chaque insertion. Si les clés sont longues, leur hachage ou leur comparaison doit aussi être pris en compte.

Cours · Méthode

Compter et justifier un algorithme

Passer de recherches répétées à une table

Supposons que donnees soit une liste de n entiers. Pour chaque entier, recompter ses apparitions en parcourant toute la liste peut conduire à n parcours de longueur n, donc à un coût quadratique. Un dictionnaire permet de mémoriser le compteur de chaque entier rencontré.

compteurs = {}
for x in donnees:
    if x not in compteurs:
        compteurs[x] = 0
    compteurs[x] = compteurs[x] + 1

À chaque itération, on réalise un nombre borné d’opérations sur le dictionnaire. Le temps total est donc O(n) en moyenne. Si u valeurs distinctes sont rencontrées, on stocke u compteurs : l’espace occupé par ce résultat est O(u).

Justifier un algorithme avec un invariant

Un invariant est une propriété vraie avant chaque itération et conservée par le traitement. Pour le comptage, avant de traiter un nouvel élément, chaque compteur donne le nombre exact d’apparitions dans la partie déjà parcourue.

Au départ, cette partie est vide et le dictionnaire est vide. Traiter x augmente exactement son compteur d’une unité. À la fin, toute la liste a été parcourue : les compteurs correspondent donc aux effectifs cherchés.

TD · Exercice 1

Lire du code

Compétences : distinguer clés et valeurs, prévoir une exécution, expliquer une collision.

Lecture de code

d = {"A": 2, "B": 5}
d["A"] = d["A"] + 1
d["C"] = d["B"] - 2
d["B"] = d["A"]
print(len(d))
print("A" in d, 3 in d)
print(d["C"])

Donner le contenu de d après les trois affectations, puis les trois lignes affichées. Justifier le résultat de 3 in d.
Que provoque l’instruction d[0] ? Écrire une instruction qui ajoute la clé "D" avec la valeur 0, puis une instruction qui supprime la clé "B". Ces deux instructions sont exécutées après le programme ci-dessus.
Parmi "A", 4, (1, 2), [1, 2] et (1, [2]), quelles expressions peuvent servir de clés ? Justifier les deux refus.

TD · Exercice 1, suite

Expliquer les collisions

On considère maintenant une table indépendante du dictionnaire précédent. La fonction de hachage est h(k) = k % 5. Les paires sont rangées par chaînage dans leur case, dans l’ordre d’arrivée. On insère successivement les clés 2, 7, 12 et 4.

Compléter la table et identifier la collision.

Case	Clés présentes dans cette case
0	…
1	…
2	…
3	…
4	…

Décrire la recherche de 12, puis de 17. Pourquoi le même résultat de hachage ne suffit-il pas à conclure que la clé est présente ?

TD · Exercice 2

Compter et déterminer un mode

Une acquisition fournit une liste d’entiers. On souhaite connaître l’effectif de chaque valeur, puis la valeur la plus fréquente, appelée un mode.

L = [2, 1, 2, 3, 1, 2, 4, 3]

Contrat : occurrences(L) renvoie un dictionnaire associant chaque entier présent à son nombre d’apparitions. La liste L ne doit pas être modifiée. occurrences([]) renvoie {}.

Donner le dictionnaire attendu pour la liste ci-dessus. Écrire occurrences(L) avec une seule boucle sur L, en utilisant le schéma de comptage du cours.
Écrire mode(L), qui utilise occurrences. Si plusieurs valeurs ont l’effectif maximal, renvoyer la plus petite. Si L est vide, renvoyer None, qui indique ici l’absence de résultat. Ne pas utiliser max, la méthode count ou une bibliothèque de comptage.

TD · Exercice 2, suite

Tester le comptage et le mode

Compléter les résultats attendus dans les tests suivants avant de les exécuter. L’instruction assert vérifie qu’une expression est vraie et signale une erreur dans le cas contraire.

assert occurrences(L) == ...
assert occurrences([]) == ...
assert mode(L) == ...
assert mode([5, 1, 5, 1]) == ...
assert mode([-2, -2, 4]) == ...
assert mode([]) == ...

On note n la longueur de L et u le nombre de valeurs distinctes. Donner les coûts en temps moyen et en mémoire. Pourquoi appliquer un comptage complet de la liste à chacun de ses éléments serait-il moins efficace ?

Vérification manuelle

Valeur	Effectif attendu	Candidate au mode
1	…	…
2	…	…
3	…	…
4	…	…

Attention : la valeur la plus grande de L et la valeur la plus fréquente répondent à deux questions différentes. Le dictionnaire sert ici à comparer les effectifs associés aux valeurs.

TD · Exercice 3

Regrouper des mesures de capteurs

Trois capteurs envoient des températures en degrés Celsius. Chaque mesure est un tuple (nom_du_capteur, temperature). La liste conserve l’ordre d’arrivée des mesures.

mesures = [
    ("A", 19.0), ("B", 21.0), ("A", 20.0),
    ("C", 18.0), ("B", 23.0), ("A", 21.0)
]

Écrire regrouper(mesures), qui associe à chaque capteur la liste de ses températures, dans leur ordre d’arrivée. Un capteur absent des données ne doit pas apparaître. Pour une entrée vide, renvoyer {}. Chaque capteur doit disposer de sa propre liste. Donner également le dictionnaire attendu pour les mesures ci-dessus.
Écrire moyennes(groupes), où groupes est un résultat de regrouper. Renvoyer un dictionnaire associant chaque capteur à sa température moyenne. Utiliser une boucle pour calculer chaque somme, sans sum. Pour groupes = {}, renvoyer {}.

Les listes associées aux capteurs sont non vides par construction. Donner le dictionnaire des moyennes attendu pour les mesures ci-dessus.

TD · Exercice 3, suite

Contrôler les listes et les coûts

Expliquer l’erreur du programme ci-dessous et donner le contenu final de groupes. Indiquer comment éviter ce partage involontaire dans regrouper.

partage = []
groupes = {"A": partage, "B": partage}
groupes["A"].append(20.0)

Avec N mesures et u capteurs distincts, justifier que regrouper puis moyennes prennent ensemble O(N) en moyenne. Distinguer la mémoire occupée par les listes de mesures de celle occupée par le dictionnaire des moyennes.

Tests à compléter puis à exécuter

assert regrouper([]) == ...
assert moyennes({}) == ...
assert moyennes(regrouper(mesures)) == ...

Question de méthode : les boucles de moyennes sont imbriquées. Cela impose-t-il un coût quadratique ? Compter le nombre total de mesures visitées avant de répondre.

TD · Exercice 4

Manipuler des polynômes creux

Un polynôme creux possède peu de coefficients non nuls par rapport à son degré. On le représente par un dictionnaire qui associe un degré entier positif ou nul à son coefficient entier non nul. Les coefficients nuls ne sont pas stockés.

Ainsi, le polynôme P(x) = 3 − x² + 2x⁵ est représenté par P = {0: 3, 2: -1, 5: 2}. Le polynôme nul est représenté par {}.

P = {0: 3, 2: -1, 5: 2}
Q = {0: -3, 1: 4, 2: 1}

Écrire coefficient(P, k), pour un entier k positif ou nul, qui renvoie le coefficient du degré k. Si k est absent, renvoyer 0, sans modifier P.
Écrire evaluer(P, x) en parcourant les termes présents. Vérifier à la main la valeur de P en x = 2. Que renvoie la fonction pour le polynôme nul ?
Écrire addition(P, Q), qui renvoie un nouveau dictionnaire représentant la somme. Les arguments ne doivent pas être modifiés. Les coefficients qui s’annulent doivent être absents du résultat. Donner le résultat attendu pour les deux dictionnaires ci-dessus.

TD · Exercice 4, suite

Tester les opérations sur les polynômes

On note p = len(P) et q = len(Q). Justifier un coût O(p + q) en moyenne pour l’addition et une occupation mémoire O(p + q) au plus. Pourquoi une liste de tous les coefficients est-elle peu adaptée à 1 + x¹⁰⁰⁰⁰⁰⁰ ?

Tests à compléter puis à exécuter

assert coefficient(P, 1) == ...
assert evaluer(P, 2) == ...
assert evaluer({}, 7) == ...
assert addition(P, Q) == ...
assert addition({2: 3}, {2: -3}) == ...
assert addition({}, {}) == ...

Les calculs de coefficients sont réalisés ici sur des entiers : le test coefficient == 0 est exact. L’étude d’une tolérance d’annulation pour des coefficients flottants n’est pas demandée.

TD · Exercice 5

Rechercher une paire de somme donnée

On dispose d’une liste L d’entiers et d’un entier cible. On cherche deux indices distincts i et j, avec i < j, tels que L[i] + L[j] soit égal à cible.

Contrat : deux_somme(L, cible) renvoie un tuple (i, j) convenable, ou None s’il n’existe aucune paire. Une seule paire suffit. La liste ne doit pas être modifiée.

L = [8, 3, 5, 2, 7]
cible = 10

Une méthode essaie toutes les paires d’indices i < j. Combien de paires teste-t-elle si aucune solution n’est trouvée ? En déduire son coût en fonction de n = len(L).
Pour traiter la valeur L[j], quelle valeur complémentaire faut-il rechercher ? Expliquer le contenu utile d’un dictionnaire vus associant les valeurs déjà rencontrées à un de leurs indices.
Écrire deux_somme en une seule boucle. Tester la présence du complément avant d’insérer L[j] dans vus. Justifier cet ordre à l’aide des listes [5] et [5, 5], avec cible = 10.

TD · Exercice 5, suite

Tracer et tester la recherche

Compléter la trace ci-dessous jusqu’à la première paire trouvée. Donner le coût en temps moyen, le pire cas lié aux collisions et le coût en mémoire.

j	L[j]	Complément	vus avant le test	Action
0	8	…	{}	…
1	3	…	…	…
2	5	…	…	…
3	2	…	…	…

Tests à compléter puis à exécuter

Compléter les résultats attendus pour l’algorithme qui parcourt les indices de gauche à droite et renvoie dès le premier complément trouvé.

assert deux_somme([8, 3, 5, 2, 7], 10) == ...
assert deux_somme([5, 5], 10) == ...
assert deux_somme([5], 10) == ...
assert deux_somme([], 10) == ...
assert deux_somme([1, 2, 3], 8) == ...
assert deux_somme([-3, 7, 2], 4) == ...

Pour approfondir

Références

Les références ci-dessous permettent de retrouver le vocabulaire du programme et la documentation des opérations utilisées dans ce chapitre.

Clavier : ← → pour naviguer · F pour le plein écran