Données Dictionnaire

Identification

Infoforall

22 - Dictionnaire


Nous avons abordé 3 types abstraits linéaires et ordonnés.

  1. La LISTE : un ensemble ordonné sur lequel on peut insérer, supprimer et lire n'importe quel élément
  2. La PILE (LIFO) : un ensemble ordonné sur lequel on ne peut agir que sur le dernier élément (et donc uniquement agir sur une des extrémités)
  3. La FILE (FIFO) : un ensemble ordonné sur lequel on peut insérer d'un côté et supprimer à l'autre extrémité

Nous allons (re)découvrir aujourd'hui un dernier type abstrait linéaire : le dictionnaire.

1 - Le Dictionnaire en tant que type abstrait de données

1er partie de la définition du type abstrait de données DICTIONNAIRE

Principe général d'organisation

Un dictionnaire est un type abstrait de données ayant les propriétés suivantes :

  • il est composé de deux ensembles formant chacun une séquence finie mais non ordonnée.
    • L'un des ensembles correspond à ce qu'on nomme les clés
    • l'autre ensemble corresopnd aux valeurs associées aux 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')
  • ni les clés, ni les valeurs n'ont à être du même type

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

Un type abstrait de données est défini par deux choses :

  1. un principe général d'organisation des données stockées (c'est ce qu'on a vu ci-dessus)
  2. les fonctions d'interface permettant à l'algorithme d'interagir avec les données stockées

Description de l'interface minimale du type abstrait Dictionnaire

Je le décris ici sous forme d'un type mutable, mais on pourait faire la même chose en non-mutable.

  1. nouveauDictionnaire() -> Dictionnaire : on crée un nouveau DICTIONNAIRE vide {}.
  2. dictA = nouveauDictionnaire()
    Le contenu de dictA est alors {}.

  3. ajouter(cle:Cle, valeur:Valeur, d:Dictionnaire) -> None : rajoute une nouvelle clé en lui associant la valeur fournie.
  4. ds = nouveauDictionnaire()
    ajouter("Alice", 12, ds) va ajouter une nouvelle clé dans notre dictionnaire ds.

    Si on décrit le contenu du dictionnaire en utilisant la codification de Python plutôt que d'inventer un autre système, nous aurions ainsi cela :

    ds contient {'Alice': 12}

  5. modifier(cle:Cle, valeur:Valeur, d:Dictionnaire) -> None : modifie la valeur associée à la clé.

  6. modifier("Alice", 15, ds) va transformer le 12 en 15 dans le dictionnaire.

    Si on décrit le contenu du dictionnaire en utilisant la codification de Python plutôt que d'inventer un autre système, nous aurions ainsi cela :

    ds contient {'Alice': 15}

  7. rechercher(cle:Cle, d:Dictionnaire) -> Valeur : renvoie la valeur associée à une clé, si la clé existe.

  8. rechercher("Alice", ds) va renvoyer 15.
  9. supprimer(cle:Cle, d:Dictionnaire) -> None : supprime la clé et la valeur associée du dictionnaire.

  10. supprimer("Alice", ds) va supprimer la seule clé du dictionnaire.

    ds contient {}

03° Créer un dictionnaire plats qui contient 3 clés : vos trois plats préférés. La valeur associée sera à choisir parmi "Apéro", "Entrée", "Plat", "Dessert".

...CORRECTION...

2 - Implémentation Python

Python possède un type natif qui permet de gérer les dictionnaires : le type natif dict.

Voici comment on peut utiliser des codes correspondants aux fonctions d'interface :

  1. Nouveau dictionnaire
  2. 1
    ds = {}

    Les accolades servent à signaler qu'il s'agit d'un dictionnaire.

    La structure de données implémentant le type abstrait DICTIONNAIRE est le type natif dict dans Python :

    >>> ds = {} >>> ds {} >>> type(ds) <class 'dict'>
  3. ajouter
  4. modifier
  5. Pas de différence entre les deux fonctions en Python : si on veut modifier une clé qui n'existe pas, on la crée.

    1 2 3 4 5
    ds = {} ds['Alice'] = 15 ds['Bob'] = 12 ds['Clark'] = 9 ds['Clark'] = 19

    On remarque que le type natif dict de Python est mutable puisqu'on parvient à modifier la valeur associée à Clark sans erreur.

    Comme pour le type natif list (tableau), on accède à une valeur en utilisant des crochets. La différence vient de ce qu'on place à l'intérieur des crochets : le numéro d'index pour les tableaux mais la clé pour un dictionnaire.

    >>> ds {'Alice': 15, 'Bob': 12, 'Clark': 19}
  6. rechercher
  7. Avec Python, cette fonction d'interface est donc simplement réaliser en utilsant les crochets et en plaçant la clé voulue.

    >>> ds['Alice'] 15

    Par contre, attention : la recherche d'une clé qui n'existe pas, provoque une exception.

    >>> ds['Dédé'] KeyError: 'Dédé'

    Pour pallier à cela, Python permet de vérifier que la clé existe avec le mot-clé in. Oui, mais : à quel coût ?...

    >>> 'Dédé' in ds False >>> 'Alice' in ds True
    >>> if 'Dédé' in ds : ds['Dédé'] = 10 >>> if 'Alice' in ds : ds['Alice'] = 12 >>> ds {'Alice': 12, 'Bob': 12, 'Clark': 19}
  8. supprimer
  9. La fonction d'interface supprimer peut être implémenter en Python avec le mot-clé del.

    1 2 3 4 5
    ds = {} ds['Alice'] = 15 ds['Bob'] = 12 ds['Clark'] = 19 del ds['Bob']
    >>> ds {'Alice': 15, 'Clark': 19}

    Mais on peut aussi utiliser une méthode du type natif Class) dict nommée ... pop, comme pour le type natif (Class) list.

    Par contre, on ne peut pas juste noter ceci sans provoquer d'erreur :

    >>> ds.pop() TypeError: pop expected at least 1 arguments, got 0

    Pourquoi ? Le type natif list est un tableau dynamique : un ensemble linéaire et ordonné d'éléments. On peut donc facilement supprimer le dernier. Mais souvenez-vous : le dictionnaire n'est pas ordonné. Il n'a donc pas de "dernier" élément à suprrimer.

    Le fait qu'on ai inséré une clé plus tard ne donne aucun infériorité à cette clé en terme de suppression. Sur un dictionnaire, il faut donc préciser impérativement la clé à supprimer :

    >>> ds.pop('Alice') 15 >>> ds {'Clark': 19}

    Et en plus la méthode renvoie la valeur associée qu'on vient de supprimer en même temps que la clé. Elle peut le faire puisque le type dictionnaire est mutable en Python. La méthode n'a donc pas besoin de renvoyer un nouveau dictionnaire.

Une dernière remarque pour la fin :

Nature des clés et des valeurs

Le type abstrait DICTIONNAIRE et le type natif (structure de données) dict de Python permettent d'avoir des clés et des valeurs de nature totalement différentes.

On pourrait ainsi avoir des notes mais également des strings pour signaler une Absence ou le fait que l'élève est Non Noté sur ce DS.

1 2 3 4 5
ds = {} ds['Alice'] = 'A' ds['Bob'] = 12 ds['Clark'] = 'NN' ds['Dédé'] = 9.86

Les valeurs peuvent être absolument n'importe quoi.

Par contre, les clés ne doivent être que des types immuables, même un tuple contenant des coordonnées par exemple.

Coûts en lecture/modification et en insertion/suppression

Vous pouvez considérer que, dans le cas moyen, le coût des action suivantes est constant (Θ = 1) : (voir FAQ)

  • Lecture et modification
  • Insertion et suppression

Bon, du coup, ça à l'air top. Pourquoi ne pas utiliser le dictionnaire plutôt que les listes dont nous avons vu que les implémentations courantes basées sur un tableau et une liste chainée offrent au mieux un coût constant sur l'un et un coût linéaire sur l'autre !

Réponse : voir les parties suivantes.

3 - Rappel : parcours dans une liste sous forme d'un tableau

Comment trouver une valeur dans un tableau ?

Principe du tableau
Recherche dans un tableau

La solution générale est de lire les valeurs une à une jusqu'à trouver celle qu'on veut ! Du coup, le coût est linéaire (Θ = n).

Vous devez être capable de coder ces fonctions à partir de rien, à part le prototype peut-être.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
def maximum(tableau) : '''Renvoie la valeur maximale contenue dans le tableau d'entiers positifs''' maximum = 0 for valeur in tableau : if valeur > maximum : maximum = valeur return valeur def maximum(tableau) : '''Renvoie la valeur maximale contenue dans le tableau d'entiers''' maximum = tableau[0] for valeur in tableau : if valeur > maximum : maximum = valeur return valeur def maximum(tableau) : return max(tableau) def trouve(tableau, x) : '''Fonction booléenne : True si on trouve x dans le tableau''' for valeur in tableau : if valeur == x : return True return False def trouve(tableau, x) : '''Fonction booléenne : True si on trouve x dans le tableau''' return x in tableau def trouve_index(tableau, x) : '''Renvoie l'index correspondant à la valeur x (ou None si x n'est pas dans le tableau''' for index in range( len(tableau) ) : if tableau[index] == x : return index

La fonction maximum de la ligne 9 est également à coût linéaire : la complexité est cachée par l'utilisation de la fonction native max, c'est tout.

La fonction trouve de la ligne 19 est également à coût linéaire : la complexité est cachée par l'utilisation du mot clé in, c'est tout.

04° Réaliser la fonction minimum qui doit renvoyer le minimum qu'on peut trouver dans un tableau.

1
def minimum(tableau:list) -> Elt

05° Réaliser la fonction maximum qui doit renvoyer le maximum qu'on peut trouver dans un tableau.

1
def maximum(tableau:list) -> Elt

06° Réaliser la fonction trouverIndex qui doit renvoyer l'index correspondant à la valeur x demandée. None sinon.

1
def trouverIndex(tableau:list, x:Elt) -> int

Par contre, avec un tableau on peut faire une chose : le trier. Et du coup, on peut chercher plus efficacement une valeur.

  1. On choisit de regarder la case centrale des zones à explorer
  2. Le tableau étant trié, on supprime d'un coup la moitié des cas restants
Méthode dichotomique dans un tableau trié

Si vous n'avez plus aucun souvenir de cela : activité sur la dichotomie

La recherche dichotomique permet de réduire la taille des données à tester par deux à chaque étape.

Le coût d'une recherche est logarithmique, plus précisément log 2, noté lg en informatique : (Θ = log2 n)

>>> import math >>> math.log2(2) 1.0 >>> math.log2(4) 2.0 >>> math.log2(8) 3.0 >>> math.log2(16) 4.0

Le tableau permet donc d'obtenir une recherche plus avantageuse que le cas linéaire pourvu que le tableau soit trié.

On rappelle qu'on peut utiliser les méthodes de tri vues précédemment mais que Python possède deux façons natives (et efficaces) de trier les tableaux :

La fonction native sorted qui renvoie une COPIE triée du tableau transmis:

>>> t = [4, 1, 3, 12, 3] >>> t2 = sorted(t) >>> t [4, 1, 3, 12, 3] >>> t2 [1, 3, 3, 4, 12]

La méthode (de la classe/type natif list) sort qui trie sur place le tableau transmis :

>>> t = [4, 1, 3, 12, 3] >>> t [4, 1, 3, 12, 3] >>> t.sort() >>> t [1, 3, 3, 4, 12] >>> t.sort(reverse=True) >>> t [12, 4, 3, 3, 1]

Par contre, une fois le tableau trié, il est très facile de rechercher une valeur puisqu'on peut utiliser la dichotomie.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
def recherche_dicho(tableau, x) : '''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param tableau(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (NoneType ou int) :: l'index de l'élément ou None .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE .. Précondition 3 :: x doit être du même type que les éléments du tableau ''' g = 0 d = len(tableau) - 1 while g <= d : print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if tableau[c] < x : g = c + 1 elif tableau[c] > x : d = c - 1 else : return c

07° Tester le programme ci-dessous qui vous permettra de vous souvenir comment fonctionne la dichotomie au besoin.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
import random def creer(nbr) : '''Fonction qui renvoie un tableau de nbr éléments compris entre 0 et 100 :: param nbr(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nbr éléments compris entre 0 et 100 ''' tableau = [random.randint(0,100) for x in range(nbr)] return tableau def recherche_dicho(tableau, x) : '''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param tableau(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (NoneType ou int) :: l'index de l'élément ou None .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE .. Précondition 3 :: x doit être du même type que les éléments du tableau ''' g = 0 d = len(tableau) - 1 while g <= d : print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if tableau[c] < x : g = c + 1 elif tableau[c] > x : d = c - 1 else : return c if __name__ == '__main__' : tab_test = sorted( creer(100) ) print(tab_test) numero = recherche_dicho(tab_test, 5) print(numero)

08° Transformer la fonction de recherche dichotomique dans sa version récursive : cela permet de supprimer la boucle.

Pour cela, il faut trouver les conditions d'arrêt et les cas de base et penser à ce que doit renvoyer l'appel récursif sinon.

Voici le début car il faut penser à initialiser correctement les paramètres g et d qu'il faut transmettre dans le cas récursif.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def recherche_dicho(tableau, x, g=0, d=None) : '''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param tableau(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (NoneType ou int) :: l'index de l'élément ou None .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE .. Précondition 3 :: x doit être du même type que les éléments du tableau ''' if d == None : d = len(tableau) - 1 print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def recherche_dicho(tableau, x, g=0, d=None) : '''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param tableau(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (NoneType ou int) :: l'index de l'élément ou None .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE .. Précondition 3 :: x doit être du même type que les éléments du tableau ''' if d == None : d = len(tableau) - 1 print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if d < g : return None elif tableau[c] == x : return c else : if tableau[c] < x : g = c + 1 elif tableau[c] > x : d = c - 1 return recherche_dicho(tableau, x, g, d)

Comme vous venez de le revoir, le tableau ne permet pas une insertion à coût constant mais permet de faire des recherches à coût logarithmique pourvu qu'il soit trié.

Le résumé global de la liste sous forme d'un tableau :

Avantages

  • Accès (lecture et modification) à coût constant direct grace au numéro d'index de la 'case'
  • Parcours à coût logarithmique dans le le cas d'une recherche dichotomique dans une liste-tableau triée

Désavantages

  • Insertion et suppression à coût linéaire : il faut déplacer les 'cases'
  • Parcours à coût linéaire pour trouver une valeur dans une liste-tableau non triée
  • Contenu homogène : les cases ont toutes le même type (est-ce un défaut puisque ça permet de trier ?)
  • Concaténation à coût linéaire puisqu'il faut recréer un tableau et y placer les éléments

4 - Rappel : parcours dans une liste sous forme d'une liste chaînée

Plutôt que d'utiliser la version contiguë, on peut voir une liste comme une succession de cellules ou de zones mémoires qui contiennent la valeur à mémoriser ET l'adresse de la prochaine cellule.

Principe de la liste chaînée

Nous avions vu que la concaténation de deux listes chainées pouvait se faire à coût constant mais que le parcours des valeurs était linéaire. On ne peut pas vraiment faire mieux dans la mesure où il faut lire une cellule pour trouver la suivante.

09° Voir ligne 45 et + : Quelle est la tête de la liste produite par le programme ? Que vaut la queue ? Représenter la liste chaînée produite par ce programme.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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
# Déclarations des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() def valeur_max(self, maximum) : if self.v > maximum : maximum = self.v if not self.s : return maximum else : return self.s.valeur_max(maximum) class Liste : '''Classe implémentant une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete def listeVide(self) : return self.tete == None def maximum(self) : '''Renvoie la valeur maximum de la liste''' if not self.listeVide() : maximum = self.tete.v if self.tete.s : return self.tete.s.valeur_max(maximum) else : return maximum # Programme principal if __name__ == "__main__" : a = Cellule(12, None) b = Cellule(25, a) c = Cellule(-6, b) d = Cellule(20, c) lis1 = Liste(c) print(lis1.maximum())

...CORRECTION...

La tête est 20.

La queue est -6 --> 25 --> 12 --> None

La liste est 20 --> -6 --> 25 --> 12 --> None.

10° Expliquer étape par étape comment fonctionne la recherche du maximum dans cette implémentation.

Le résumé global de la liste sous forme d'une liste chaînée :

Avantages

  • Concaténation à coût constant si l'implémentation stocke l'adresse de la tête et de la dernière cellule.
  • Insertion / suppression à coût constant pourvu qu'on connaisse les adresses des cellules sur lesquelles agir (il faut donc une implémentation adaptée à ce qu'on désire faire : c'est le principe d'un bon choix d'implémentation !).

Désavantages

  • Accès (lecture et modification) à coût linéaire sauf sur les cellules dont on connait l'adresse
  • Parcours à coût linéaire dans le but de trouver une valeur dans la liste chaînée : même en triant la liste, on ne peut pas mémoriser toutes les adresses, sinon cela revient à créer un tableau. On ne peut donc pas utiliser la dichotomie facilement.
  • Contenu homogène : les valeurs ont typiquement toutes le même type (est-ce un défaut ?)

5 - Parcours dictionnaire

Retour au dictionnaire : nous avons vu que l'accès à une valeur, la modification d'une valeur se faisait à coût constant, pourvu qu'on connaisse la clé. Idem pour l'insertion / suppression à coût constant si on connait la clé. Si on rajoute le fait que les valeurs peuvent être de nature différentes, on a l'impression que le dictionnaire est merveileux.

Regardons maintenant si on peut rechercher aussi efficacement une valeur précise lorsqu'on ne connait pas la clé associée justement.

On rappelle qu'il existe 3 méthodes permettant d'énumérer le contenu d'un dictionnaire (plus une façon de faire implicite).

Enumération du contenu d'un dictionnaire à partir des clés avec keys

Ici, nous voulons trouver l'ensemble des valeurs associées à chaque clé.

Obtention de toutes les clés de manière implicite

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 tour à tour une clé for truc in dico : print(truc) # Méthode implicite : c'est plus clair en donnant un nom adapté à la variable de boucle for cle in dico : print(cle)

Dans les deux cas, on obtient ceci :

Ananas Bananes Cerises Kiwi Poires

Encore plus explicite : on peut obtenir le même résultat en noter clairement qu'on utilise la méthode keys.

1 2 3 4 5
dico = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} # Méthode explicite avec la méthode keys for cle in dico.keys() : print(cle)

11° Coder la fonction booléenne valeur_existe pour qu'elle renvoie True si la valeur transmise existe bien dans le dictionnaire. On vous impose l'utilisation de la méthode keys.

1
def valeur_existe(d:dict, v:Elt) -> bool :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def valeur_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 ''' pass if __name__ == '__main__' : import doctest doctest.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 20
def valeur_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 ''' for cle in d.keys() : if d[cle] == v : return True return False

12° Quelle est le coût de la recherche ?

...CORRECTION...

Linéaire : on regarde toutes les clés une par une.

Enumération directe des valeurs avec values

Si on ne cherche pas les clés ou si on ne cherche pas à modifier les valeurs, on peut utiliser plutôt 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() for valeur in dico.values() : print(valeur)

On obtient alors directement les valeurs une par une :

2 5 7 10 4

13° Coder la fonction booléenne valeur_existe pour qu'elle renvoie True si la valeur transmise existe bien dans le dictionnaire. On vous impose l'utilisation de la méthode values.

1
def valeur_existe(d:dict, v:Elt) -> bool :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def valeur_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 ''' pass if __name__ == '__main__' : import doctest doctest.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 20
def valeur_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 ''' for valeur in d.values() : if valeur == v : return True return False

14° Quelle 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 ?

Choisir la méthode

Si on ne veut lire que les valeurs d'un dictionnaire sans les modifier ou connaître leurs clés :

  • Soit for valeur in d.values() et on accédera aux éléments avec valeur
  • Soit for cle in d.keys() et on accédera aux éléments avec d[cle]

Par contre, si on veut modifier les valeurs, il faut connaître la clé. Du coup, pas le choix :

  • for cle in d.keys() et on modifiera les éléments avec d[cle] = nouveau

En réalité, c'est comme avec le FOR numérique pour obtenir un index ou le FOR nominatif pour accéder directement aux valeurs d'un tableau.

Si on ne veut lire que les valeurs d'un tableau sans les modifier ou connaître leurs positions :

  • Soit for element in tableau et on accédera aux éléments avec element
  • Soit for index in range( len(tableau) ) et on accédera aux éléments avec tableau[index]

Par contre, si on veut modifier les cases ou connaître leurs index, il faut connaître l'index :

  • for index in range( len(tableau) ) et on modifiera les éléments avec tableau[index] = nouveau

En réalité, avec les dictionnaires, il existe une troisième façon de faire : on peut obtenir directement un tuple contenant la clé et la valeur associée.

Enumération directe des (clés, valeurs) avec items

Si on veut obtenir à la fois les clés et les valeurs (sans repasser par la clé), on peut utiiser items qui renvoie un tuple. On peut donc le stocker directement dans une variable ou stocker directement la clé (index 0 du tuple) et la valeur (index 1 du tuple).

1 2 3 4
dico = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} for couple in dico.items() : print(couple)

On obtient des tuples sur la console :

('Ananas', 2) ('Bananes', 5) ('Cerises', 7) ('Kiwi', 10) ('Poires', 4)

On peut du coup isoler la clé et la valeur à partir du couple :

1 2 3 4 5 6
dico = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} for couple in dico.items() : cle = couple[0] valeur = couple[1] print(f"{cle} --> {valeur}")

L'affichage obtenu :

Ananas --> 2 Bananes --> 5 Cerises --> 7 Kiwi --> 10 Poires --> 4

On peut même récupérer directement la clé et la valeur à partir du couple renvoyé mais sans le mémoriser lui-même :

1 2 3 4
dico = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4} for cle, valeur in dico.items() : print(f"{cle} --> {valeur}")

L'affichage obtenu :

Ananas --> 2 Bananes --> 5 Cerises --> 7 Kiwi --> 10 Poires --> 4

15° Coder la fonction booléenne valeur_existe pour qu'elle renvoie True si la valeur transmise existe bien dans le dictionnaire. On vous impose l'utilisation de la méthode items.

1
def valeur_existe(d:dict, v:Elt) -> bool :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def valeur_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 ''' pass if __name__ == '__main__' : import doctest doctest.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 20
def valeur_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 ''' for cle, valeur in d.items() : if valeur == v : return True return False

16° Quelle 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.

17° On veut créer une fonction qui cherche la valeur et lui rajoute 2 si elle la trouve. 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.

18° On propose ceci. Qu'est-ce qui fait que cela ne fonctionne pas ? Modifier la fonction pour qu'elle fonctionne.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
def rajoute_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} ''' for cle, valeur in d.items() : if valeur == v : valeur = valeur + 2 if __name__ == '__main__' : import doctest doctest.testmod() dico = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4}

...CORRECTION...

Ligne 19 : on modifie la variable valeur, pas le contenu réel du dictionnaire. Pour ça, il faut agir via la clé !

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
def rajoute_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} ''' for cle, valeur in d.items() : if valeur == v : d[cle] = valeur + 2 if __name__ == '__main__' : import doctest doctest.testmod() dico = {'Ananas':2, 'Bananes':5, 'Cerises': 7, 'Kiwi':10, 'Poires':4}
Avantages / désavantages du dictionnaire en tant que structure de données

En tant que type abstrait, le dictionnaire peut être utilisé comme on le veut mais s'il est correctement implémenté dans une structure de données, il aura des avantages et des inconvients par rapport aux tableaux et aux listes.

Avantages

  • Lecture / modification à coût constant pourvu qu'on connaisse la clé
  • Insertion / suppression à coût constant pourvu qu'on connaisse 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

Désavantages

  • Impossibilité conceptuelle de classer les valeurs à moins d'utiliser la clé comme élément de classement. Mais dans ce cas, il faut que les clés soient toutes comparables entre elles.
  • Parcours pour faire une recherche de valeur à coût linéaire
  • Pas de possibilité d'ordonné les valeurs : les éléments sont stockés sans qu'on impose un ordre. Lorsqu'on lit les clés, l'ordre de lecture n'est absolument pas imposés par quoi que ce soit.
Ordre des clés dans les versions récentes de Python

Tout comme, le type list n'est pas juste un tableau mais possède d'autres méthodes, le type dict de Python possède plus de propriétés qu'un dictionnaire ou tableau associatif.

Par exemple, les clés sont toujours fournies par ordre d'apparition dans le dictionnaire.

>>> d = {} >>> d['z'] = "Première valeur rajoutée" >>> d {'z': 'Première valeur rajoutée'} >>> d['a'] = "Deuxième valeur rajoutée" >>> d {'z': 'Première valeur rajoutée', 'a': 'Deuxième valeur rajoutée'} >>> d[(45,23)] = "troisième valeur rajoutée" >>> d {'z': 'Première valeur rajoutée', 'a': 'Deuxième valeur rajoutée', (45, 23): 'troisième valeur rajoutée'}

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.

19° Imaginons que les valeurs de notre dictionnaire caractérise le nombre de jour d'arrivée d'un stock de fruits ou de 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
def plus_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) ''' pass if __name__ == '__main__' : import doctest doctest.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 20 21 22
def plus_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 = 0 cle_maximum = '' for cle, valeur in d.items() : if valeur > maximum : maximum = valeur cle_maximum = cle return (cle_maximum, maximum)

20° 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def produits_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'] ''' pass if __name__ == '__main__' : import doctest doctest.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
def produits_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 = [] for cle in d.keys() : if d[cle] >= nbr_jours : reponse = reponse + [cle] return reponse
Note finale : l'ordre obtenu dans la documentation est garanti par le type dict de Python mais pas par le type abstrait dictionnaire lui-même.

6 - FAQ

Et c'est implémenté comment sous le capot ?

Il y a plusieurs façons d'implémenter un dictionnaire.

Python utilise une tableau de hachage.

Et c'est quoi une table de hachage ?

En informatique, hacher veut dire transformer une entrée en un nombre à l'aide d'une fonction mathématique dite de hachage.

Le principe est qu'une légère modification de l'entrée provoque une grande variation du nombre obtenu. On peut faire cela avec Python facilement avec la fonction native hash.

>>> hash('Bonjour') -4357677828996342144 >>> hash('Donjour') -7265348244809284727

Le principe de la fonction de hachage est

  1. qu'il existe plusieurs entrées qui peuvent provoquer la même sortie
  2. qu'il est impossible ou presque de remonter jusqu'aux entrées à partir de la valeur de sortie.

C'est d'ailleurs sous cette forme que sont stockés les mots de passe sur les sites : on ne stocke pas directement la chaîne de caractères composant le mot de passe mais un hachage de celui-ci.

Même si quelqu'un tombe sur les 'mots de passe' stockés, il ne pourra donc pas en faire grand chose :

>>> hash('1234') 5217145266935398779

Pour rendre les choses encore plus complexe, on rajoute même une chaîne de caractère à votre propre mot de passe.

Par exemple, vous vous connecter avec le mot de passe '1234'. Le site hache plutôt 'ifa'+'1234', soit 'ifa1234'.

>>> hash('ifa'+'1234') -1370047763760331189

Plus tard, lorsque vous revenez sur ce site, il suffit de réaliser ce test pour savoir si c'est votre mot de passe :

>>> mdp = "NSI!' >>> hash('ifa'+'NSI!') == -1370047763760331189 False

Même si un hacker récupère le -1370047763760331189, il aura du mal à lui donner du sens...

Et c'est le lien avec le dictionnaire ?

On hache chaque clé mais cela donne un grand nombre comme vous l'avez vu.

Disons qu'on veuille n'avoir que 1000 valeurs différentes pour ne pas avoir à créer un tableau trop grand.

Il suffit donc de hacher ET de chercher le reste de la division par 1000. Le fameux modulo.

>>> hash('Alice') % 100 89

Et voilà. Pour implémenter un dictionnaire, on pourra créer un tableau de 1000 éléments et lorsqu'on veut créer une nouvelle clé, on hache sa valeur pour trouver à quel index elle est placé dans le tableau :

>>> dictionnaire = [None for x in range(1000)] >>> dictionnaire[hash('Alice') % 1000] = 12 >>> dictionnaire[hash('Alice') % 1000] 12

Comme c'est un tableau sous le capot, le coût d'accès à la lecture et à l'écriture est constant. Comme insérer une clé revient à écrire sur un index, le coût est constant aussi.

Bien entendu, c'est plus complexe que ça. Par exemple, que faire si deux clés donnent la même valeur d'index ?

C'est bien pour cela que j'ai mis cette explication est dans FAQ et pas ailleurs : ce n'est pas au programme car c'est assez technique en réalité si on veut rendre la méthode fonctionnelle. Mais vous avez compris le principe dans les grandes lignes sinon.

Activité publiée le 15 11 2020
Dernière modification : 01 12 2020
Auteur : ows. h.