Tableaux associatifs : dictionnaires

Un tableau associatif est un type de variable qui permet de regrouper des données, un peu comme un tableau, sauf que les éléments ne sont pas repérés par leur indice dans cet ensemble mais par leur clé, qui peut être un entier, une chaîne de caractères, etc...

En Python les tableaux associatifs correspondent au type construit dictionnaire ( dict ).

Utilisation des dictionnaires en Python

Généralités

Les dictionnaires se révèlent très pratiques lorsque l'on doit manipuler des structures complexes à décrire et que les tableaux présentent leurs limites.

Un dictionnaire est défini par des accolades { }.

Chaque élément d'un dictionnaire est composé d'une clé et d'une valeur, séparées par deux points :.

La structure d'un dictionnaire est alors :


dico = {clé1: valeur1, clé2: valeur2, ...}

Les clés d'un dictionnaire doivent être uniques. Elles doivent être non mutables ( donc de type int, float, str, tuple ), ce qui signfie que l'on ne peut pas par exemple utiliser des clés de type list.

Les valeurs d'un dictionnaires peuvent elles être multiples et mutables ou non mutables ( tous les types sont acceptés ).

À la différence des tableaux et des tuples, les éléments d'un dictionnaire n'ont pas d'ordre particulier, d'où l'appellation d'ensemble non-ordonné : il n'y a pas de "premier élément", "deuxième élément", etc...

Exemples :


animaux = {"nom": "singe", "poids": 70, "taille": 1.75} # clés de type str et valeurs de type variés
placard = {"chemise" : 3, "pantalon" : 6, "tee-shirt" : 7} # clés de type str et valeurs de type int
simpson = {"père" : "Homer" , "mère" : "Marge", "fils" : "Bart", "fille" : "Lisa"} # clés et valeurs de type str
dressing = {"chemise" : ["M", "Bleu", "tiroir du bas"], "pantalon" : ["M", "Vert", "tiroir du milieu"]} # clés de type str et valeurs de type list

Création d'un dictionnaire

Création par instanciation

C'est la méthode la plus simple. Elle consiste à créer le dictionnaire en utilisant le symbole d'affectation = , et en saisissant les éléments les uns après les autres.


simpson = {"père" : "Homer" , "mère" : "Marge", "fils" : "Bart", "fille" : "Lisa"}

Création par compréhension

Cette méthode ressemble à celle utilisée pour remplir les tableaux. Au lieu d'indiquer les crochets du tableau [ ], on utilise les accolades du dictionnaire { }.

Exemples :


carre = {a: a**2 for a in range(0, 11)}

>>> carre = {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100}


vide = {i: None for i in range(5)}

>>> vide = {0: None, 1: None, 2: None, 3: None, 4: None}

Accès aux éléments d'un dictionnaire

Accès aux valeurs

Pour accéder à la valeur correspondant à une clé, on utilise, comme pour les valeurs dans un tableau, la notation crochets [ ] en indiquant la clé au lieu de l'indice : dico[clé] .


print(simpson["père"])
>>> Homer

print(simpson["mère"])
>>> Marge

Bien entendu, une erreur est générée si la clé n'existe pas dans le dictionnaire.


print(simpson["tante"])

>>> KeyError: 'tante'

Parcours d'un dictionnaire

Comme un tableau ou un tuple, un dictionnaire peut se parcourir élément par élément.

Parcours par clé

C'est l'équivalent du parcours par indice d'un tableau :


for cle in simpson :
	print(cle)

père
mère
fils
fille


for cle in simpson :
	print(simpson[cle])

Homer
Marge
Bart
Lisa

Parcours par valeur

On utilise la méthode values() :


for valeur in simpson.values() :
	print(valeur)

Homer
Marge
Bart
Lisa

Parcours par clé ET valeur

On utilise la méthode items() qui renvoie un tuple constitué de chaque élément clé/valeur :


for cle, valeur in vide.items():
	print(cle, valeur)
     
 
0 None
1 None
2 None
3 None
4 None

Modification d'un dictionnaire

Un dictionnaire est mutable comme un tableau ( mais à la différence d'un tuple ), c'est à dire que l'on peut en modifier les éléments.

Du fait qu'il soit mutable, la copie d'un dictionnaire présentera donc les mêmes problèmes que la copie d'un tableau.

Ajouter des éléments à un dictionnaire

Pour ajouter un élément clé/valeur à un dictionnaire, on utilise l'instruction : dico[clé] = valeur.

Exemple :


user = {'Marcel': 1234, 'Maurice': 0123, 'Gustave': 0000}
user['Bond'] = 007

>>> user = {'Marcel': 1234, 'Maurice': 0123, 'Gustave': 0000, 'Bond': 007}

Modification de la valeur d'un élément


user['Bond'] = 008

>>> user = {'Marcel': 1234, 'Maurice': 0123, 'Gustave': 0000, 'Bond': 008}

Supprimer des éléments à un dictionnaire

Pour supprimer un ensemble clé/valeur à un dictionnaire, on utilise l'instruction del dico[clé].

Exemple :


del user["Maurice"]

>>> user = {'Marcel': 1234, 'Gustave': 0000, 'Bond': 008}

Test d'appartenance

L'opérateur in permet de tester si une clé, une valeur ou un ensemble clé/valeur se trouve dans le dictionnaire :


>>> "Marcel" in user.keys()
True

>>> "Maurice" in user.keys()
False

>>> "Bond" in user.values()
False

>>> 1234 in user.values()
True

>>> ('Bond', '008') in user.items()
True

Par défaut la recherche se fait dans les clefs :


>>> user = {'Marcel': 1234, 'Maurice': 0123, 'Gustave': 0000, 'Bond': 007}
>>> '007' in user
False

>>> 'Bond' in user
True

Efficacité de la recherche

Un des avantages des dictionnaire par rapport au tableau c'est bien sur l'indexation par clef, on n'est plus limité par les index entiers commençant à 0 comme dans les tableaux.

Mais l'avantage essentiel d'un dictionnaire c'est la rapidité de la recherche. En effet, quand on fait un test d'appartenance dans un dictionnaire avec le mot in, le langage n'est pas obligé de parcourir le dictionnaire en entier, la valeur recherchée est atteinte directement, on dit que la recherche est en O(1).

La recherche dans un dictionnaire est en O(1). Cela signifie que quelque soit la taille du dictionnaire, le temps de recherche d'une clef dans le dictionnaire ne change pas. (Dans un tableau classique, le temps de recherche est en O(n) !)

Nous allons tester cette propriété des dictionnaire et les comparer aux tableaux. Le code ci-dessous utilise le module timeit que vous avez déjà utilisé ici. il permet d'afficher le temps de recherche d'un élément dans un tableau de longueur croissante. vous devez :

Tester ce code et noter l'évolution des résultats avec l'augmentation de la taille du tableau. (En particulier que se passe-t-il à chaque fois que la taille du tableau est multipliée par 10 ?)
Modifier ce code pour réaliser les mêmes tests sur un dictionnaire de la même taille que le tableau.
Tester ce code et noter l'évolution des résultats avec l'augmentation de la taille du dictionnaire. (En particulier que se passe-t-il à chaque fois que la taille du dictionnaire est multipliée par 10 ?)

from timeit import timeit for n in range (4,9): tab=[0 for i in range(10**n)] t = timeit(stmt = "2 in tab", globals=globals(), number = 1) print(t)

Exercices

Manipulations de base

définir le dictionnaire personne contenant les informations suivantes relatives à une personne :
- Nom : Dupuis
- Prénom : Jacque
- Age : 30
corriger l'erreur dans le prénom et afficher le dictionnaire. La bonne valeur est "Jacques".
afficher la liste des clés du dictionnaire.
afficher la liste des valeurs du dictionnaire.
afficher la liste des paires clé/valeur du dictionnaire.
afficher la phrase : "Jacques Dupuis a 30 ans" en utilisant le dictionnaire.

Constructions par compréhension

Compléter l'instruction ci-dessous afin d'obtenir un dictionnaire contenant les 11 premières puissances de deux (de 2**0 jusqu'à 2**10) :
```
dico = {0:1, 1:2, 2:4, 3:8, 4:16, 5:32, 6:64 ...}
					
```
dico = {...:... for ... in range(....)} print(dico)
On dispose de deux tableaux donnant les numéros des départements et les noms des départements ( dans le même ordre ) :
```
numeros = ["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","2A","2B","21","22","23","24","25","26","27","28","29","30","31","32","33","34","35","36","37","38","39","40","41","42","43","44","45","46","47","48","49","50","51","52","53","54","55","56","57","58","59","60","61","62","63","64","65","66","67","68","69","70","71","72","73","74","75","76","77","78","79","80","81","82","83","84","85","86","87","88","89","90","91","92","93","94","95","971","972","973","974","976"]

noms = ["Ain","Aisne","Allier","Alpes-de-Haute-Provence","Hautes-Alpes","Alpes-Maritimes","Ardèche","Ardennes","Ariège","Aube","Aude","Aveyron","Bouches-du-Rhône","Calvados","Cantal","Charente","Charente-Maritime","Cher","Corrèze","Corse-du-Sud","Haute-Corse","Côte-d'Or","Côtes d'Armor","Creuse","Dordogne","Doubs","Drôme","Eure","Eure-et-Loir","Finistère","Gard","Haute-Garonne","Gers","Gironde","Hérault","Ille-et-Vilaine","Indre","Indre-et-Loire","Isère","Jura","Landes","Loir-et-Cher","Loire","Haute-Loire","Loire-Atlantique","Loiret","Lot","Lot-et-Garonne","Lozère","Maine-et-Loire","Manche","Marne","Haute-Marne","Mayenne","Meurthe-et-Moselle","Meuse","Morbihan","Moselle","Nièvre","Nord","Oise","Orne","Pas-de-Calais","Puy-de-Dôme","Pyrénées-Atlantiques","Hautes-Pyrénées","Pyrénées-Orientales","Bas-Rhin","Haut-Rhin","Rhône","Haute-Saône","Saône-et-Loire","Sarthe","Savoie","Haute-Savoie","Paris","Seine-Maritime","Seine-et-Marne","Yvelines","Deux-Sèvres","Somme","Tarn","Tarn-et-Garonne","Var","Vaucluse","Vendée","Vienne","Haute-Vienne","Vosges","Yonne","Territoire de Belfort","Essonne","Hauts-de-Seine","Seine-St-Denis","Val-de-Marne","Val-D'Oise","Guadeloupe","Martinique","Guyane","La Réunion", "Mayotte"]

					
```
Compléter l'instruction ci-dessous afin d'obtenir un dictionnaire dont les clefs correspondent aux numéros des départements et dont les valeurs correspondent aux noms des départements :
```
departements = { "1" : "Ain", "2" : "Aisne", "3" : "Allier",	 ...}
					
```
numeros = ["1","2","3","4","5","6","7","8","9","10", "11","12","13","14","15","16","17","18","19","2A", "2B","21","22","23","24","25","26","27","28","29","30", "31","32","33","34","35","36","37","38","39","40", "41","42","43","44","45","46","47","48","49","50", "51","52","53","54","55","56","57","58","59","60", "61","62","63","64","65","66","67","68","69","70", "71","72","73","74","75","76","77","78","79","80", "81","82", "83","84","85","86","87","88","89","90", "91","92","93","94","95","971","972","973","974","976"] noms = ["Ain","Aisne","Allier","Alpes-de-Haute-Provence", "Hautes-Alpes","Alpes-Maritimes","Ardèche","Ardennes", "Ariège","Aube","Aude","Aveyron","Bouches-du-Rhône", "Calvados","Cantal","Charente","Charente-Maritime","Cher", "Corrèze","Corse-du-Sud","Haute-Corse","Côte-d'Or", "Côtes d'Armor","Creuse","Dordogne","Doubs","Drôme","Eure", "Eure-et-Loir","Finistère","Gard","Haute-Garonne", "Gers","Gironde","Hérault","Ille-et-Vilaine","Indre", "Indre-et-Loire","Isère","Jura","Landes","Loir-et-Cher", "Loire","Haute-Loire","Loire-Atlantique","Loiret", "Lot","Lot-et-Garonne","Lozère","Maine-et-Loire", "Manche","Marne","Haute-Marne","Mayenne","Meurthe-et-Moselle", "Meuse","Morbihan","Moselle","Nièvre","Nord","Oise", "Orne","Pas-de-Calais","Puy-de-Dôme","Pyrénées-Atlantiques", "Hautes-Pyrénées","Pyrénées-Orientales","Bas-Rhin", "Haut-Rhin","Rhône","Haute-Saône","Saône-et-Loire","Sarthe", "Savoie","Haute-Savoie","Paris","Seine-Maritime", "Seine-et-Marne","Yvelines","Deux-Sèvres","Somme","Tarn", "Tarn-et-Garonne","Var","Vaucluse","Vendée","Vienne", "Haute-Vienne","Vosges","Yonne","Territoire de Belfort", "Essonne","Hauts-de-Seine","Seine-St-Denis","Val-de-Marne", "Val-D'Oise","Guadeloupe","Martinique","Guyane","La Réunion", "Mayotte"] departements = {...:... for ... in range(...)} print(departements)
On dispose d'un dictionnaire donnant les âges de chats hospitalisés chez un vétérinaire :
```
ages = {'Mirza' : 7, 'Tom' : 4, 'Moustache' : 6, 'Patoune' : 5, 'Frisco' : 6, 'Tacos' : 5, 'Sleepy' : 3, 'Belle' : 4, 'Zaza' : 11, 'Oxmo' : 13}
					
```
Compléter l'instruction suivante afin d'obtenir la liste de tous les noms de chats ayant plus de 7 ans :

ages = {'Mirza' : 7, 'Tom' : 4, 'Moustache' : 6, 'Patoune' : 5, 'Frisco' : 6, 'Tacos' : 5, 'Sleepy' : 3, 'Belle' : 4, 'Zaza' : 11, 'Oxmo' : 13} chats_ages = [ ... for ... in ... if ... >= ...] print(chats_ages)

Lien vers les RÉPONSES

Utilisation de dictionnaires

Fusion de dictionnaires

Dans différents contextes, notamment lorsque l'on collecte des données open source à partir de différents sites il est nécessaire de fusionner les données obtenues structirées dans des dictionnaires.

Écrire une fonction fusion_dico qui renvoie le dictionnaire obtenu en fusionnant deux dictionnaires passés en paramètre.
Les valeurs des clefs communes aux deux dictionnaires seront additionnées (on suppose que les valeurs sont donc de type "additionnable")
Les dictionnaires donnés en paramètre ne seront pas modifiés par la fonction

def fusion_dico(dico1, dico2): """Fonction qui renvoie un dictionnaire issu de la fusion des paramètres ENTREE : Deux dictionnaires dont les valeurs sont additionnables SORTIE : le dictionnaire correspondant à la fusion des deux paramètres """ pass def tests_fusion(): dico2={'a':1,'b':3} dico1={'a':1,'b':1,'c':3} test1 = (fusion_dico(dico1,dico2) == {'a': 2, 'b': 4, 'c': 3}) dico3={'a':'a','b':'b'} dico4={'a':'a','b':'b','c':'c'} test2 = (fusion_dico(dico3,dico4) == {'a': 'aa', 'b': 'bb', 'c': 'c'}) return test1 and test2 print(tests_fusion())

Lien vers les RÉPONSES

Score au Scrabble

Le dictionnaire scrabble ci-dessous contient la valeur de chacune des lettres de l'alphabet au Scrabble :


scrabble = {"A":1,"B":3,"C":3,"D":2,"E":1,"F":4,"G":2,"H":4,"I":1,"J":8,"K":10,"L":1,"M":2,"N":1,"O":1,"P":3,"Q":8,"R":1,"S":1,"T":1,"U":1,"V":4,"W":10,"X":10,"Y":10,"Z":10}

Écrire une fonction score qui calcule, en utilisant le dictionnaire scrabble, le score obtenu en plaçant un mot passé en argument à la fonction ( sans tenir compte des cases bonus : lettre compte-double, mot compte-triple, etc...)

tester la fonction avec quelques mots ( en utilisant éventuellement le module doctest ) :


score('NSI') == 3				
score('BONJOUR') == 16
score('KIWI') == 22
score('ANTICONSTITUTIONNELLEMENT') == 28

def score(mot): """Fonction qui calcule le score d'un mot placé au Scrabble ENTREE : mot = chaîne de caractères représentant le mot à évaluer (str) SORTIE : le score associé à ce mot (int) """ scrabble = {"A":1,"B":3,"C":3,"D":2,"E":1,"F":4,"G":2,"H":4,"I":1,"J":8,"K":10,"L":1,"M":2,"N":1,"O":1,"P":3,"Q":8,"R":1,"S":1,"T":1,"U":1,"V":4,"W":10,"X":10,"Y":10,"Z":10} pass

Lien vers les RÉPONSES

Conversion chiffres romains → base 10

Les Romains n'utilisaient pas la numération de position comme nous le faisons, mais un système où chaque symbole représente une certaine valeur décimale :

'M' = 1000
'D' = 500
'C' = 100
'L' = 50
'X'= 10
'V' = 5
'I' = 1

Pour obtenir le nombre exprimé par une suite de ces "chiffres romains", il faut faire la somme de toutes leurs valeurs décimales, en suivant les règles suivantes :

si un chiffre n'est pas suivi d'un chiffre de plus grande valeur, alors on additionne simplement sa valeur à la somme.
si un chiffre est suivi d'un autre de plus grande valeur, alors on soustrait sa valeur de la somme.

Exemple :

"MCMXIX" = "M - C + M + X - I + X" = 1000 - 100 + 1000 + 10 - 1 + 10 = 1919

créer un dictionnaire romains, dont les clés sont les chiffres romains ( chaîne de caractère ) et les valeurs leur équivalent décimal ( entier ).
écrire une fonction rom_to_dec qui utilise le dictionnaire romains pour convertir en base 10 un nombre en chiffres romains passé en argument.

def rom_to_dec(r): """Fonction de conversion d'un nombre en chiffres romains vers la base 10 ENTREE : r = chaîne de caractères représentant le nombre en chiffres romains SORTIE : le nombre ( entier ) converti en base 10 (int) """ romains = {} # dictionnaire des équivalences chiffres romains <-> valeur décimale ( à compléter ) pass

Lien vers les RÉPONSES

Construction et affichage de dictionnaire : analyse d'un texte

Écrire une fonction analyse qui prend en argument une chaîne de caractères et renvoie un dictionnaire associant à chaque caractère apparaissant dans la chaîne le nombre de ses occurrences, c'est à dire le nombre de fois où ce caractère apparaît dans la chaîne.
Écrire ensuite une fonction qui affiche le dictionnaire ( passé en argument ) dans l’ordre alphabétique des lettres.
On utilisera la méthode tableau.sort() qui appliquée à un tableau, trie celui-ci en place.

tester le code avec le texte suivant :


p = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Curabitur condimentum nulla eu tempus luctus. Quisque scelerisque eu ipsum feugiat egestas. Curabitur viverra velit vitae viverra accumsan. Etiam sodales turpis quis arcu imperdiet, eu faucibus erat sodales. Sed consequat risus non eleifend mollis. Donec vel est nec ligula mattis tincidunt in id neque. Sed quis aliquet augue, a imperdiet neque. Ut tristique eros iaculis est accumsan ullamcorper. Sed vitae tellus at diam efficitur fermentum ut et odio. Maecenas ac diam at urna ornare varius ac at felis. Vestibulum magna enim, gravida ut malesuada eu, iaculis ac ipsum."

def analyse(phrase): """Fonction comptant le nombre d'occurrences de chaque caractère dans une chaîne ENTREE : phrase = chaîne de caractères (str) SORTIE : le dictionnaire associant à chaque caractère dans la chaîne son nombre d'occurrences (dict) """ pass def affiche(dico): """Fonction d'affichage d'un dictionnaire dans l'ordre alphabétique des lettres ENTREE : dico = le dictionnaire (dict) SORTIE : aucune """ pass

Lien vers les RÉPONSES

Décodage du morse

On s'intérèsse au codage et au décodage d'un message à l'aide du code morse.

On représente le code morse à l'aide d'un dictionnaire; on ne s'intéresse qu'aux lettres en majuscules non accentuées. Pour l'espace on utilise le slash (par exemple) :


morse = {' ': '/', 'E': '°', 'I': '°°', 'S': '°°°', 'H': '°°°°', 'V': '°°°-', 'U': '°°-', 'F': '°°-°', 'A': '°-', 'R': '°-°', 'L': '°-°°', 'W': '°--', 'P': '°--°', 'J': '°---', 'T': '-', 'N': '-°', 'D': '-°°', 'B': '-°°°', 'X': '-°°-', 'K': '-°-', 'C': '-°-°', 'Y': '-°--', 'M': '--', 'G': '--°', 'Z': '--°°', 'Q': '--°-', 'O': '---'}

Écrire une fonction encode_lettre, qui prend en paramètre une lettre et le dictionnaire morse, et qui renvoie le code morse de la lettre.
Par exemple : encode_lettre('S', morse) renvoie '°°°'.
Écrire une fonction encode_mots qui prend en paramètre un message et le dictionnaire morse, et qui renvoie le message codé en morse.
Chaque code devra être séparé du suivant par un espace.
Par exemple : encode_mot('SOS',morse) renvoie : '°°° --- °°°'.
Écrire une fonction decode_mots qui prend en paramètre un message codé et le dictionnaire morse, et qui renvoie le message décodé. On pourra utiliser la méthode chaine.split(), qui renvoie le tableau des mots de la chaîne chaine.

Décoder le message suivant :


message = "-°°° °-° °- °°°- --- / °--- ° °°- -° ° / °--° °- -°° °- °-- °- -° / °-°° °- / -° °°° °° / ° °°° - / °- °°°- ° -°-° / - --- °°"

def encode_lettre(lettre, morse): pass def encode_mots(msg, morse): pass def decode_mots(msg, morse): pass morse = {' ': '/', 'E': '°', 'I': '°°', 'S': '°°°', 'H': '°°°°', 'V': '°°°-', 'U': '°°-', 'F': '°°-°', 'A': '°-', 'R': '°-°', 'L': '°-°°', 'W': '°--', 'P': '°--°', 'J': '°---', 'T': '-', 'N': '-°', 'D': '-°°', 'B': '-°°°', 'X': '-°°-', 'K': '-°-', 'C': '-°-°', 'Y': '-°--', 'M': '--', 'G': '--°', 'Z': '--°°', 'Q': '--°-', 'O': '---'} message = "-°°° °-° °- °°°- --- / °--- ° °°- -° ° / °--° °- -°° °- °-- °- -° / °-°° °- / -° °°° °° / ° °°° - / °- °°°- ° -°-° / - --- °°"

Lien vers les RÉPONSES