Un dictionnaire est un type abstrait de données ayant les propriétés suivantes :
il est composé d'une séquence finie mais non ordonnée d'éléments composés :
de clés
des valeurs associées à chacun des clés précédentes
on peut accéder à n'importe quelle valeur pourvu qu'on connaisse sa clé
on peut rajouter ou supprimer n'importe quelle clé et ainsi supprimer la valeur associée
Les clés
Les valeurs associées
"Ananas"
178
"Banane"
1200
"Cerise"
(90.0, 'kg')
L'autre nom du type dictionnaire est le tableau associatif. Il s'agit en effet d'une sorte de généralisation du tableau classique, pour lequel les clés sont le numéro d'index.
01° Quelle est la valeur associée à la clé "Courgette" ? Quelle est la valeur associée à la clé "Pomme de Terre" ?
Les clés
Les valeurs associées
"Chips"
(38, 'paquet', '2.00')
"Courgette"
(12, 'kilo', '4.80')
"Pomme de Terre"
'En cours de réapprovisionnement'
...CORRECTION...
02° Quel est le type de la valeur associée à la clé "Courgette" ? Quel est le type de la valeur associée à la clé "Pomme de Terre" ?
...CORRECTION...
2e partie de la définition du type abstrait de données DICTIONNAIRE : son interface
Description des primitives du Dictionnaire
On décrit un type mutable, mais on peut avoir de l'immuable.
nouveauDictionnaire() -> Dictionnaire
dictA = nouveauDictionnaire() Le contenu de dictA est alors {}.
Notez l'aspect mutable puisque la primitive de modification ne renvoie pas un nouveau dictionnaire.
modifier("Alice", 15, ds) va transformer le 12 en 15 dans le dictionnaire.
ds contient {'Alice': 15}
lire(cle:Cle, d:Dictionnaire) -> Valeur
Renvoie la valeur associée à une clé, si la clé existe.
lire("Alice", ds) va renvoyer 15.
supprimer(cle:Cle, d:Dictionnaire) -> None
Supprime la clé et la valeur associée du dictionnaire.
supprimer("Alice", ds) va supprimer la clé "Alice" du dictionnaire.
ds contient alors {} puisque c'était la seule.
03° Créer un dictionnaire plats qui contient 3 clés : vos trois plats préférés. La valeur associée aux clés sera à choisir parmi "Apéro", "Entrée", "Plat", "Dessert".
La ligne 5 demande la suppression de la clé "Bob" dans ce dictionnaire qui devient alors :
>>> ds
{'Alice': 15, 'Charlie': 19}
On peut également utiliser une méthode du type natif dict nommée pop(). Attention, contrairement au pop() du type list, il faut nécessairement fournir une clé. C'est normal puisqu'un dictionnaire n'ordonne pas ses clés.
>>> ds.pop('Alice')
15>>> ds
{'Charlie': 19}
Une dernière remarque pour la fin :
Nature des clés et des valeurs
Le type abstrait DICTIONNAIRE et le type natif dict de Python permettent d'avoir des clés et des valeurs de nature totalement différentes.
On pourrait ainsi également associer un string pour signaler une "Absence" ou le fait que l'élève soit "Non Noté" sur ce DS.
Dans un tableau non trié, la recherche d'un élément est à coût linéaire.
Par contre, dans un tableau trié, on peut utiliser une recherche dichotomique qui est à coût logarithmique.
Regardons le coût de la recherche dans un dictionnaire lorsqu'on ne connait pas la clé associée.
Il existe 3 méthodes permettant d'énumérer le contenu d'un dictionnaire.
Parcours par clés avec keys()
Pour trouver les clés, on a la méthode implicite et la méthode explicite.
Méthode implicite
Nous éviterons de l'utiliser par la suite car elle peut induire en erreur quelqu'un qui lirait rapidement le code.
1
2
3
4
5
6
7
8
9
dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}# Méthode implicite : truc va contenir une clé différente à chaque tourfortrucindico:print(truc)# Méthode implicite : avec un nom adapté à la variable de boucleforcleindico:print(cle)
Dans les deux cas, on obtient ceci :
Ananas
Bananes
Cerises
Kiwi
Poires
Manière explicite
On peut indiquer clairement qu'on récupère les clés en utilisant la méthode keys() sur le dictionnaire. A privilégier sur vos copies.
1
2
3
4
5
dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}# Méthode explicite avec la méthode keysforcleindico.keys():print(cle)
04° Créer le prédicat valeur_existe() pour qu'il renvoie True si la valeur transmise existe bien dans le dictionnaire. Attention, on cherche bien une valeur associée à une clé, pas une clé.
CONTRAINTE : on vous impose l'utilisation de la méthode keys().
defvaleur_existe(d,v):"""Renvoie True si v est l'une des valeurs dans le dictionnaire d :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (bool) :: True si on trouve, False sinon :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> valeur_existe(exemple, 5) True >>> valeur_existe(exemple, 12) False """passif__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
defvaleur_existe(d,v):"""Renvoie True si v est l'une des valeurs dans le dictionnaire d :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (bool) :: True si on trouve, False sinon :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> valeur_existe(exemple, 5) True >>> valeur_existe(exemple, 12) False """forcleind.keys():ifd[cle]==v:returnTruereturnFalse
On réalise la boucle déclarée en L17 autant de fois qu'il y a de clés, notons n ce nombre.
Or, la ligne 18 et 19 sont des opérations à coût constant.
La boucle L17-18-19 est donc à coût linéaire ( puisque linéaire * constant donne du linéaire).
La ligne L20 est à coût constant.
La fonction est donc à coût linéaire.
Parcours par valeurs avec values()
Si on cherche juste les valeurs (c'est à dire qu'on ne veut pas modifier le contenu), on peut utiliser la méthode values.
1
2
3
4
5
dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}# Méthode explicite : valeur va contenir les valeurs obtenues via values()forvaleurindico.values():print(valeur)
On obtient alors directement les valeurs une par une :
2
5
7
10
4
06° Créer le prédicat valeur_existe() pour qu'il renvoie True si la valeur transmise existe bien dans le dictionnaire. On vous impose l'utilisation de la méthode values().
defvaleur_existe(d,v):"""Renvoie True si v est l'une des valeurs dans le dictionnaire d :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (bool) :: True si on trouve, False sinon :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> valeur_existe(exemple, 5) True >>> valeur_existe(exemple, 12) False """passif__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
defvaleur_existe(d,v):"""Renvoie True si v est l'une des valeurs dans le dictionnaire d :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (bool) :: True si on trouve, False sinon :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> valeur_existe(exemple, 5) True >>> valeur_existe(exemple, 12) False """forvaleurind.values():ifvaleur==v:returnTruereturnFalse
07° Quel est le coût de la recherche ?
...CORRECTION...
Linéaire : on regarde toutes les valeurs une par une et à l'interne, il faut donc bien trouver les clés une par une.
Alors, quelle méthode utilisée ?
BILAN A CONNAITRE : choisir le parcours
Si on veut juste lire les valeurs (sans vouloir les modifier), on peut utiliser :
soit un parcours par valeurs : forvind.values() et la valeur est obtenue avec v
soit un parcours par clés : forcind.keys() et la valeur est obtenue avec d[c]
Si on veut modifier les valeurs, il faut connaître la clé et nous n'avons donc pas le choix :
parcours par clés : forcind.keys() et on peut modifier les éléments avec d[c] = nouveau
C'est donc proche des parcours sur les tableaux :
Si on veut juste lire les valeurs d'un tableau, nous avons deux choix :
soit le parcours par valeurs : forvint et on récupère les valeurs avec v
soit le parcours par indices : foriinrange(len(t)) et on récupère les valeurs avec t[i]
Si on veut modifier les valeurs stockées dans les cases, il faut connaître l'indice de la case donc :
parcours par indices : foriinrange(len(t)) et on récupère les valeurs avec t[i] = nouveau
Attention néanmoins à la grande différence :
forxind ramène les clés une à une si d est un dictionnaire.
forxint ramène les valeurs une à une si t est un tableau.
En réalité, il existe une troisième façon de faire cela avec les dictionnaires : on peut obtenir directement un tuple contenant la clé et la valeur associée.
Parcours par couple (clé, valeur) avec items()
On peut obtenir à la fois la clé et la valeur (sans repasser par la clé) avec items() via un tuple (cle, valeur). On peut donc le stocker directement dans une variable ou stocker directement la clé (indice 0 du tuple) et la valeur (indice 1 du tuple).
08° Créer le prédicat valeur_existe() pour qu'il renvoie True si la valeur transmise existe bien dans le dictionnaire. On vous impose l'utilisation de la méthode items().
defvaleur_existe(d,v):"""Renvoie True si v est l'une des valeurs dans le dictionnaire d :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (bool) :: True si on trouve, False sinon :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> valeur_existe(exemple, 5) True >>> valeur_existe(exemple, 12) False """passif__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
defvaleur_existe(d,v):"""Renvoie True si v est l'une des valeurs dans le dictionnaire d :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (bool) :: True si on trouve, False sinon :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> valeur_existe(exemple, 5) True >>> valeur_existe(exemple, 12) False """forcle,valeurind.items():ifvaleur==v:returnTruereturnFalse
09° Quel est le coût de la recherche ?
...CORRECTION...
Linéaire : on regarde toutes les valeurs une par une et à l'interne, il faut donc bien trouver les clés une par une.
10° On veut créer une fonction qui cherche une valeur transmise et lui rajoute 2 si elle la trouve. La valeur doit donc être un int ou un float. Quelles méthodes peut-on utiliser ?
...CORRECTION...
On va devoir agir sur la valeur : il faudra donc connaître la clé. On peut donc utiliser keys() ou items().
11° On propose ceci. Qu'est-ce qui fait que cela ne fonctionne pas ? Modifier la fonction pour qu'elle fonctionne.
defrajoute_2_si_existe(d,v):"""Rajoute 2 à la valeur si elle existe :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (None) :: :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> rajoute_2_si_existe(exemple, 5) >>> exemple {'Ananas': 2, 'Bananes': 7, 'Cerises': 7, 'Kiwi': 10, 'Poires': 4} """forcle,valeurind.items():ifvaleur==v:valeur=valeur+2if__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
...CORRECTION...
Ligne 19 : on modifie la variable LOCALE valeur, pas le contenu réel du dictionnaire. Pour ça, il faut agir via la clé !
defrajoute_2_si_existe(d,v):"""Rajoute 2 à la valeur si elle existe :: param d(dict) :: le dictionnaire à analyser :: param v(Elt) :: la valeur qu'on cherche à trouver ou pas :: return (None) :: :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> rajoute_2_si_existe(exemple, 5) >>> exemple {'Ananas': 2, 'Bananes': 7, 'Cerises': 7, 'Kiwi': 10, 'Poires': 4} """forcle,valeurind.items():ifvaleur==v:d[cle]=valeur+2if__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
Avantages / désavantages du dictionnaire
Avantages
Lecture / modification : coût constant si on connaît la clé.
Insertion / suppression : coût constant si on connaît la clé.
Aucune nécessité d'avoir les mêmes types de données pour chaque valeur
Aucune nécessité d'avoir les mêmes types de données pour les clés
Opérateur d'appartenance in : à coût constant.
Désavantages
Impossibilité classer les valeurs.
Recherche de valeur à coût linéaire
Les clés sont stockés sans qu'on impose un ordre. Lorsqu'on lit les clés, l'ordre de lecture n'est absolument pas imposé par quoi que ce soit.
Ordre des clés dans les versions récentes de Python
Ceci n'est absolument pas à connaître, c'est une pythonnerie qui va même (presque) à l'encontre du principe des clés non ordonnées.
Tout comme le type list de Python est une extension du tableau dynamique de base, le type dict de Python est une extension du dictionnaire de base.
En Python, les clés sont toujours fournies par ordre d'apparition dans le dictionnaire.
Ce n'est pas une raison pour utiliser cela dans vos algorithmes : ce n'est pas valable dans tous les langages.
Conclusion : l'ordre d'apparition des clés ne doit pas être utilisé dans un algorithme pour coder une information : rien ne garantit l'ordre de leur apparition.
12° On considère un dictionnaire dont les clés sont les noms de fruits ou légumes et les valeurs associées aux clés de notre dictionnaire caractérisent le nombre de jours de présence dans l'entrepot de ces fruits ou légumes. Créer une fonction plus_ancien() qui renvoie le tuple (clé, valeur) du produit en stock depuis le plus longtemps. On vous impose la méthode items().
Cela revient à chercher le maximum.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
defplus_ancien(d:dict)->tuple:"""Renvoie un tuple (clé, valeur) de l'élément dont la valeur est la plus ancienne / grande :: param d(dict) :: le dictionnaire à analyser sous forme cle(str) et valeur(int) :: return (tuple) :: renvoie un tuple (str, int) du plus ancien élément :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> plus_ancien(exemple) ('Kiwi', 10) """passif__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
defplus_ancien(d:dict)->tuple:"""Renvoie un tuple (clé, valeur) de l'élément dont la valeur est la plus ancienne / grande :: param d(dict) :: le dictionnaire à analyser sous forme cle(str) et valeur(int) :: return (tuple) :: renvoie un tuple (str, int) du plus ancien élément :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> plus_ancien(exemple) ('Kiwi', 10) """maximum=0cle_maximum=''forcle,valeurind.items():ifvaleur>maximum:maximum=valeurcle_maximum=clereturn(cle_maximum,maximum)
13° Créer une fonction produits_perimes() qui renvoie un tableau contenant les clés des produits dépassant le nombre de jours fournis lors de l'appel. On vous impose la méthode keys().
defproduits_perimes(d:dict,nbr_jours:int)->list:"""Renvoie un tableau contenant les clés des produits périmés :: param d(dict) :: le dictionnaire à analyser sous forme cle(str) et valeur(int) :: paral nbr_jours(int) :: le nombre de jours à ne pas atteindre :: return (list) :: un tableau de clés des produits périmés :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> produits_perimes(exemple, 5) ['Bananes', 'Cerises', 'Kiwi'] """passif__name__=='__main__':importdoctestdoctest.testmod()dico={'Ananas':2,'Bananes':5,'Cerises':7,'Kiwi':10,'Poires':4}
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
defproduits_perimes(d:dict,nbr_jours:int)->list:"""Renvoie un tableau contenant les clés des produits périmés :: param d(dict) :: le dictionnaire à analyser sous forme cle(str) et valeur(int) :: paral nbr_jours(int) :: le nombre de jours à ne pas atteindre :: return (list) :: un tableau de clés des produits périmés :: exemples >>> exemple = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} >>> produits_perimes(exemple, 5) ['Bananes', 'Cerises', 'Kiwi'] """reponse=[]forcleind.keys():ifd[cle]>=nbr_jours:reponse=reponse+[cle]returnreponse
Vous auriez pu faire la même chose en utilisant append() plutôt que des concaténations.
Et d'ailleurs, savez-vous quelle est la meilleure façon de procéder s'il y a vraiment beaucoup de stock ?
Il y a énormément de choses à dire sur les fonctions de hachage. Cette description très rapide utilise plusieures simplifications : ne faites pas de généralités à partir des informations trouvées ici.
En informatique, une fonction de hachage est une fonction qui transforme une entrée (qui est toujours une suite d'octets en réalité) en un nombre (qui est toujours une suite d'octets en réalité).
On peut les utiliser pour diminuer l'empreinte mémoire d'un objet et ainsi faire des recherches d'égalité entre deux objets sans les placer réellement en mémoire s'ils sont volumineux.
Exemple avec une fonction qui divise une image en plusieurs zones et la remplace chaque zone par la couleur moyenne de la zone.
CC BY-SA 4.0, par Unique Nitrogen sur Wikipedia
Finalement, chaque empreinte n'est qu'une suite de 15 pixels.
Bien entendu, deux tableaux très similaires en termes de couleurs pourraient (mais à l'octet près, c'est douteux) avoir la même empreinte. Cela se nomme une collision.
On hache n'importe quelle donnée immuable avec Python avec la fonction native hash.
14-A° Réaliser un programme qui affiche trois fois de suite le hachage d'une même entrée.
Vous devriez visualiser que Python vous donne 3 fois la même sortie.
14-B° Relancer le programme.
Vous devriez visualiser que Python vous donne encore 3 fois la même sortie mais que les valeurs sont différentes de la fois précédentes.
Contrairement aux fonctions de hachage cryptographiques, la fonction native hash() intègre à chaque démarrage d'un programme Python une part d'aléatoire. Tant que le programme tourne, les réponses seront les mêmes mais si vous lancez plusieurs fois le même programme, vous n'aurez pas les mêmes valeurs de hachage.
14-C° Sur les systèmes assurant correctement la sécurité, les mots de passe ne sont jamais enregistrés "en dur" : la base de données ne contient pas un string qui correspond à votre mot de passe. Sinon, n'importe qui pouvant accéder à la base de données, pourrait lire votre mot de passe. Non : les bases de données ne contiennent que le hashage de votre mot de passe.
Question : demander à Python de hacher plusieurs entrées très similaires. Lorsque les entrées sont assez semblables, les sorties sont-elles proches ou éloignées ? Quel est l'intérêt ?
Les réponses sont éloignées les unes des autres. De cette façon, si quelqu'un récupère le hash du mot de passe, il ne peut tenter de retrouver l'entrée par déduction : si deux entrées proches donnaient un résultat proche, on pourrait retrouver l'entrée par déduction.
Même si un hacker récupère le hash -6321758195780172941, il aura bien du mal à retrouver votre vrai mot de passe !
14-D° La fonction hash() de Python permet-elle de sauvegarder les mots de passe de façon sécurisés ?.
...CORRECTION...
Non, puisqu'à chaque fois qu'on démarre un nouveau programme, la valeur obtenue sera différente.
Ce hash() de Python sert à autre chose.
Les fonctions de hachage utilisées pour stocker les mots de passe doivent avoir beaucoup de propriétés pour assurer la sécurité des données, notamment (mais pas que) :
Une entrée fournit toujours la même sortie;
des entrées proches fournissent des sorties très différentes.
Il doit être difficile de retrouver une entrée connaissant la valeur de hachage.
La lutte incessantes entre les hackers et les systèmes de sécurisation fait qu'il y a beaucoup d'autres propriétés moins évidentes à respecter.
En réalité, cette fonction est fondamentalement à la source du fait que trouver une clé est à coût constant dans un dictionnaire.
Lorsque que demandez à Python de créer un dictionnaire, il vous crée fondamentalement... un tableau.
Ce tableau aura beaucoup plus de cases que le nombre de clés que vous utilisez, et les cases ne contiendront que None au début.
Partons sur un exemple avec un tableau de 1000 cases.
Lorsque vous tapez ds["Alice"] = 18, vous voulez associer la valeur 18 à la clé "Alice".
Python va calculer où placer ce 18 dans le tableau dont vous ne connaissez même pas l'existence en tant qu'utilisateur. Voilà ce qui se passe sous le capot :
>>> t = [None for _ in range(1000)]
667>>> hash('Alice') % 1000
667>>> t[667] = 18
15-A° Déterminer la case attribuée à 5 élèves de la classe. Ont-ils tous une case différente ?
...CORRECTION...
Normalement oui, à moins de ne pas avoir eu de chance, chaque élève a certainement obtenu son numéro à lui.
Sur cet exemple, Dana et Elodie sont toutes les deux dans la case 3...
C'est ce qu'on appelle une collision.
Comme les collisions sont inévitables, Python utilise un mécanisme pour les gérer : il calcule bien la case mais chaque case une liste de tuples (clé, valeur) :
De façon très grossière, voici comment on pourrait comprendre ce qui se passe lorsque vous voulez ranger dans un dictionnaire les notes d'Alice (18), de Bob (8) et de Charlie (0) :
16° Si on travaille sur un tableau où le nombre de cases est bien plus grand que le nombre de clés, quel est le coût espéré de l'accès à une case connaissant la clé ?
...CORRECTION...
Sans collision (et donc de parcours de listes ou de tableaux), toutes les opérations sont à coût CONSTANT. Donc accéder à une case connaissant sa clé est à cout constant.
17° Quel est le problème de stockage de données sous de dictionnaires par rapport à un simple tableau ?
