Rappels sur les dictionnaires en Python

Objectifs et prérequis

Prérequis : fonctions en Python , listes et tuples vus en première

À l’issue de ce chapitre, vous saurez :

créer un dictionnaire (littéral, à partir d’une liste de couples, par compréhension) ;
accéder, ajouter, modifier et supprimer des entrées ;
itérer sur les clés, les valeurs ou les couples (clé, valeur) ;
gérer l’absence d’une clé avec try/except ou la méthode get ;
comparer la complexité de la recherche dans une liste (O(n)) et dans un dictionnaire (O(1)).

Introduction

Plutôt qu’accéder à une valeur à partir de son indice (comme dans un tableau), on peut souhaiter y accéder à partir d’une clé.

Par exemple dans un annuaire téléphonique, on accède à un numéro de téléphone à partir d’un nom. Les noms sont donc les clés, les numéros de téléphone les valeurs. Dans un dictionnaire (au sens traditionnel), on recherche une définition à partir d’un mot. Les mots sont les clés et les définitions les valeurs.

L’accès à la valeur ainsi que la modification ou l’ajout d’une valeur doivent être possibles sans parcourir toute la structure. On parle aussi de tableaux associatifs.

Introduction (suite)

Un dictionnaire est un ensemble de couples (clé, valeur) : on accède à une valeur par sa clé et non par sa position (l’ordre d’insertion est conservé, mais il ne joue aucun rôle). On peut ajouter des couples ; si la clé figure déjà dans le dictionnaire alors le couple est remplacé par le nouveau. Un dictionnaire Python est un objet mutable (comme les listes mais contrairement aux chaînes de caractères ou aux tuples).

Création de dictionnaires

Plusieurs méthodes permettent de créer un dictionnaire.

Dictionnaire vide

d = dict()

# ou

d = {}


print(d)

{}

Dictionnaire littéral

On écrit directement les couples clé: valeur entre accolades.

boxoffice = {'Aladdin' : 569439,
             'Godzilla 2' : 342574,
             'Rocketman' : 277017}


print(boxoffice)

{'Aladdin': 569439, 'Godzilla 2': 342574, 'Rocketman': 277017}

À partir d’une liste de couples

La fonction dict transforme une liste de couples (clé, valeur) en dictionnaire.

couples = [('Aladdin', 569439), ('Godzilla 2', 342574), ('Rocketman', 277017)]
boxoffice = dict(couples)

print(boxoffice)

{'Aladdin': 569439, 'Godzilla 2': 342574, 'Rocketman': 277017}

Par compréhension

dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

double_dict1 = {k: v * 2 for (k, v) in dict1.items()}

print(double_dict1)

{'a': 2, 'b': 4, 'c': 6, 'd': 8, 'e': 10}

Accès aux valeurs, informations

Accès à une valeur par sa clé

print(boxoffice['Aladdin'])

Nombre d’enregistrements (longueur)

print(len(boxoffice) == 3)

True

Test d’appartenance d’une clé

print('Rocketman' in boxoffice)

True

Ajout, modification, suppression de valeurs

Ajout d’une valeur

boxoffice['Avengers'] = 0

print(len(boxoffice) == 4)
print(boxoffice['Avengers'])

True
0

Unicité des clés

boxoffice['Avengers'] = 132260

print(len(boxoffice) == 4)
print(boxoffice['Avengers'])

True
132260

Les valeurs peuvent ne pas être uniques

boxoffice['Mon Film'] = 132260

print(len(boxoffice) == 5)
print(boxoffice['Avengers'])
print(boxoffice['Mon Film'])

True
132260
132260

Supprimer une valeur

del boxoffice['Mon Film']

print(len(boxoffice) == 4)
print('Mon Film' in boxoffice )

True
False

Itérations

Itération sur les clés

for film in boxoffice:
    print(f"{film} => {boxoffice[film]} spectateurs")

Aladdin => 569439 spectateurs
Godzilla 2 => 342574 spectateurs
Rocketman => 277017 spectateurs
Avengers => 132260 spectateurs

On obtient le même résultat avec le code ci-dessous :

for film in boxoffice.keys():
    print(f"{film} => {boxoffice[film]} spectateurs")

Itération sur les clés (suite)

Aladdin => 569439 spectateurs
Godzilla 2 => 342574 spectateurs
Rocketman => 277017 spectateurs
Avengers => 132260 spectateurs

Itération sur les valeurs

for nbre_spectateurs in boxoffice.values():
    print(nbre_spectateurs)

Itération sur les paires (clé, valeur)

for film, nbre_spectateurs in boxoffice.items():
    print(f"{film} => {nbre_spectateurs} spectateurs")

Aladdin => 569439 spectateurs
Godzilla 2 => 342574 spectateurs
Rocketman => 277017 spectateurs
Avengers => 132260 spectateurs

Exceptions

Accès à une valeur inexistante

print(boxoffice['Mon Film'])

Traceback (most recent call last):
  File "main.py", line 1, in <module>
    print(boxoffice['Mon Film'])
KeyError: 'Mon Film'

Capture d’exceptions

On peut intercepter l’erreur avec les instructions try et except. Python exécute d’abord le bloc try ; si une erreur KeyError s’y produit, il abandonne ce bloc et exécute le bloc except KeyError au lieu d’arrêter le programme. Si aucune erreur ne se produit, le bloc except est ignoré.

Capture d’exceptions (suite)

def nombre_entrees(titre_film):
    '''
    renvoie le nombre d'entrées du film selon boxoffice, 0 si nombre non connnu
    (boxoffice considéré ici comme global)
    '''
    try:
        return boxoffice[titre_film]
    except KeyError:
        return 0

print(nombre_entrees('Avengers'))
print(nombre_entrees('Mon film'))

Capture d’exceptions (suite)

132260
0

La méthode get() permet d’accéder à la valeur d’une clef

print(boxoffice.get('Avengers'))

boxoffice.get(key) est équivalent boxoffice[key] si key est une clef qui existe
boxoffice.get(key) renvoie None par défaut en cas de clef absente

listend

La méthode get() permet d’accéder à la valeur d’une clef (suite)

print(boxoffice.get('Mon Film') == None)

# On peut préciser, en second paramètre, la valeur que l'on veut avoir pour une clef absente
print(boxoffice.get('Mon Film', 0))
print(boxoffice.get('Avengers', 0))

True
0
132260

Recherche dans une liste et dans un dictionnaire

Lorsqu’on cherche une valeur dans une liste, il faut, dans le pire cas, parcourir tous les éléments un par un. La complexité est donc en \(O(n)\) où \(n\) est la taille de la liste.

Recherche dans une liste et dans un dictionnaire (suite)

def recherche_liste(element, liste):
    for e in liste:
        if e == element:
            return True
    return False

animaux = ['chat', 'chien', 'poule', 'vache', 'cochon']
print(recherche_liste('vache', animaux))
print(recherche_liste('tigre', animaux))

True
False

Recherche dans une liste et dans un dictionnaire (suite)

Lorsqu’on cherche une clé dans un dictionnaire, Python utilise une table de hachage. Le principe est le suivant : une fonction de hachage transforme la clé en un indice de tableau, ce qui permet d’accéder directement à la valeur associée, sans parcourir toute la structure. La complexité est donc en \(O(1)\) en moyenne.

ages = {'Alice': 17, 'Bob': 16, 'Charlie': 18}
print('Bob' in ages)
print('Diana' in ages)

True
False

Recherche dans une liste et dans un dictionnaire (suite)

Le test d’appartenance in effectue une recherche en \(O(n)\) sur une liste et en \(O(1)\) sur un dictionnaire. Cela se vérifie expérimentalement :

Recherche dans une liste et dans un dictionnaire (suite)

import time

n = 10_000_000
grande_liste = list(range(n))
grand_dict = {i: None for i in range(n)}

t0 = time.time()
print(n - 1 in grande_liste)
t1 = time.time()
print(f"Liste : {t1 - t0:.4f} s")

t0 = time.time()
print(n - 1 in grand_dict)
t1 = time.time()
print(f"Dictionnaire : {t1 - t0:.6f} s")

Recherche dans une liste et dans un dictionnaire (suite)

La différence est spectaculaire : la recherche dans la liste prend quelques centièmes de seconde tandis que celle dans le dictionnaire prend environ une microseconde, soit un facteur de l’ordre de 10 000 pour n = 10 000 000. Ce facteur augmente avec la taille de la structure : la durée de la recherche dans le dictionnaire ne dépend pas de n, alors que celle de la recherche dans la liste est proportionnelle à n.

À retenir. Le choix entre une liste et un dictionnaire a un impact majeur sur les performances d’un programme. Si l’on a besoin de tester fréquemment l’appartenance d’un élément, un dictionnaire est bien plus adapté qu’une liste.

Type des clés et valeurs

Les clés peuvent être de différents types (mais non mutables)

chiffres_arabes_vers_romains = {1: 'I', 10: 'X', 100: 'C'}
print(chiffres_arabes_vers_romains[10])

grille = {(0,0): 'T', (0,1): 'S', (1,0): ' ', (1,1): 'T'}
print(grille[(0,0)] == 'T')

Les clés peuvent être de différents types (mais non mutables) (suite)

True

Ce code provoque une erreur :

d1 = {'s': 3, 8: 'chat', [1, 'chien']: (2, 7)}
print(d1)

Traceback (most recent call last):
  File "main.py", line 1, in <module>
    d1 = {'s': 3, 8: 'chat', [1, 'chien']: (2, 7)}
TypeError: unhashable type: 'list'

Les clés peuvent être de différents types (mais non mutables) (suite)

Pas celui-ci :

d2 = {'s': 3, 8: 'chat', (1, 'chien'): (2, 7)}
print(d2)

{'s': 3, 8: 'chat', (1, 'chien'): (2, 7)}

Les valeurs aussi peuvent être de différents types

thon = {'espece': 'T', 'gestation': 3}
requin = {'espece': 'S', 'gestation': 2, 'energie': 2}
mer = {(0, 0): thon, (0, 1): None, (1, 0): None, (1, 1): requin}

print(mer[(0, 0)]['espece'])
print(mer[(1, 1)]['energie'])

T
2

Vérifiez votre compréhension

Pourquoi une liste ne peut-elle pas servir de clé dans un dictionnaire, alors qu’un tuple le peut ?
Réponse
Les clés d'un dictionnaire doivent être hachables, c'est-à-dire non mutables. Une liste est mutable (on peut modifier ses éléments), donc non hachable. Un tuple est immuable ; s'il ne contient que des éléments non mutables, il est hachable et utilisable comme clé. En revanche, le tuple (1, [2]), qui contient une liste, ne peut pas servir de clé.
Quelle est la différence entre boxoffice['Mon Film'] et boxoffice.get('Mon Film', 0) quand la clé n’existe pas ?
Réponse
boxoffice['Mon Film'] lève une exception KeyError qui interrompt le programme. boxoffice.get('Mon Film', 0) renvoie la valeur par défaut 0 sans erreur. La méthode get est plus sûre quand on n'est pas certain que la clé existe.
Pourquoi la recherche d’une clé dans un dictionnaire est-elle en O(1) alors qu’elle est en O(n) dans une liste ?
Réponse
Un dictionnaire utilise une table de hachage : une fonction transforme la clé en un indice de tableau, permettant un accès direct sans parcourir la structure. Dans une liste, il faut potentiellement examiner tous les éléments un par un.

L'essentiel à retenir

Un dictionnaire est un ensemble de couples (clé, valeur), accessibles par clé et non par position ; l’accès à une valeur par sa clé est en O(1) grâce au hachage.
Les clés doivent être non mutables (chaînes, entiers, tuples) ; les valeurs peuvent être de n’importe quel type.
On itère avec .keys(), .values() ou .items() ; l’absence d’une clé se gère avec try/except KeyError ou la méthode .get().
Le choix entre liste et dictionnaire a un impact majeur sur les performances : O(n) vs O(1) pour la recherche.
Les dictionnaires servent de base aux représentations de graphes et à de nombreuses structures en Python.