20 - Dictionnaire

⏪

⏬

⏩

1 - Dictionnaire

2 - Python

3 - Tableau

4 - Liste chaînée

5 - Parcours

6 - FAQ

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

La LISTE : un ensemble ordonné sur lequel on peut insérer, supprimer et lire n'importe quel élément
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)
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.

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

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 ?

...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 ?

...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 :

un principe général d'organisation des données stockées (c'est ce qu'on a vu ci-dessus)
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.

nouveauDictionnaire() -> Dictionnaire : on crée un nouveau DICTIONNAIRE vide {}.

dictA = nouveauDictionnaire()
Le contenu de dictA est alors {}.

ajouter(cle:Cle, valeur:Valeur, d:Dictionnaire) -> None : rajoute une nouvelle clé en lui associant la valeur fournie.

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}

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

modifier("Alice", 15, 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': 15}

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

rechercher("Alice", ds)

supprimer(cle:Cle, d:Dictionnaire) -> None : supprime la clé et la valeur associée du dictionnaire.

supprimer("Alice", ds)

ds contient {}

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".

Correction ?

...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 :

Nouveau dictionnaire

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'>

ajouter
modifier

Pas de différence entre les deux fonctions en Python : si on veut modifier une clé qui n'existe pas, on la crée.

ds = {}
ds['Alice'] = 15
ds['Bob'] = 12
ds['Charlie'] = 9
ds['Charlie'] = 19

On remarque que le type natif dict de Python est mutable puisqu'on parvient à modifier la valeur associée à Charlie 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, 'Charlie': 19}

rechercher

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, 'Charlie': 19}

supprimer

La fonction d'interface supprimer() peut être implémentée en Python avec le mot-clé del.

ds = {}
ds['Alice'] = 15
ds['Bob'] = 12
ds['Charlie'] = 19
del ds['Bob']


>>> ds
{'Alice': 15, 'Charlie': 19}

Mais on peut aussi utiliser une méthode du type natif Class) dict nommée ... pop(), comme pour le type natif 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. Par contre, 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
{'Charlie': 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.

ds = {}
ds['Alice'] = 'A'
ds['Bob'] = 12
ds['Charlie'] = '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 ?

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 (en 𝞞(n)).

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

def maximum(t:list) -> 'Element':
    """Renvoie la valeur maximale contenue dans le tableau d'entiers positifs"""
    maxi = 0
    for v in t:
        if v > maxi:
            maxi = v
    return maxi
 
def maximum(t:list) -> 'Element':
    """Renvoie la valeur maximale contenue dans le tableau d'entiers"""
    maxi = t[0]
    for v in t:
        if v > maxi:
            maxi = v
    return maxi
 
def maximum(t:list) -> 'Element':
    return max(t)
 
def trouve(t:list, x:'Element') bool::
    """Prédicat : True si on trouve x dans le tableau"""
    for v in t:
        if v == x:
            return True
    return False
 
def trouve(tableau, x):
    """Prédicat : True si on trouve x dans le tableau"""
    return x in tableau
 
def trouve(tableau, x):
    """Renvoie l'indice correspondant à la valeur x (ou None si x n'est pas dans le tableau"""
    for i in range( len(t) ):
        if t[i] == x:
            return i

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(t:list) -> 'Element'`

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

`1`	`def maximum(t:list) -> 'Element'`

06° Réaliser deux versions de la fonction trouver_indice() qui doit renvoyer l'indice correspondant à la valeur x demandée. None sinon.

Une version avec un for
Une version avec un while

`1`	`def trouver_indice(t:list, x:'Element') -> int`

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

On choisit de regarder la case centrale des zones à explorer
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 : (Θ (log₂ 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 sort() du type natif list 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.

def recherche_dicho(t, x):
    """Fonction qui cherche l'élément x dans le tableau trié
 
    :: param t(list)            :: un tableau trié d'éléments
    :: param x (variable)       :: l'élément à chercher dans le tableau
    :: return (NoneType ou int) :: l'indice de l'élément ou None
    .. Précondition 1 :: le tableau doit être NON 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(t) - 1
    while g <= d:
        print(f"Un tour de boucle avec l'intervalle [{g}; {d}]")
        c = (g + d) // 2 # Division entière
        if t[c] < x:
            g = c + 1
        elif t[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.

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(t, x):
    """Fonction qui cherche l'élément x dans le tableau trié
 
    :: param t(list)            :: un tableau trié d'éléments
    :: param x (variable)       :: l'élément à chercher dans le tableau
    :: return (NoneType ou int) :: l'indice de l'élément ou None
    .. Précondition 1 :: le tableau doit être NON 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(t) - 1
    while g <= d:
        print(f"Un tour de boucle avec l'intervalle [{g}; {d}]")
        c = (g + d) // 2 # Division entière
        if t[c] < x:
            g = c + 1
        elif t[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 maintenant la fonction de recherche dichotomique pour obtenir une forme récursive : cela permet de supprimer la boucle TANT QUE.

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.

def recherche_dicho(t, x, g=0, d=None):
    """Fonction qui cherche l'élément x dans le tableau trié
 
    :: param t(list)            :: un tableau trié d'éléments
    :: param x (variable)       :: l'élément à chercher dans le tableau
    :: return (NoneType ou int) :: l'indice de l'élément ou None
    .. Précondition 1 :: le tableau doit être NON 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(t) - 1
 
    print(f"Un tour de boucle avec l'intervalle [{g}; {d}]")
    c = (g + d) // 2 # Division entière

L'appel initial va être sous ce format car les paramètres g et d possèdent une valeur par défaut.


>>> t = ["Salut", "Au revoir", "Bonjour", "A plus", "Bonne journée"]
>>> recherche_dico(t, "Bonjour")
2

Correction ?

...CORRECTION...

def recherche_dicho(t, x, g=0, d=None):
    """Fonction qui cherche l'élément x dans le tableau trié
 
    :: param t(list)            :: un tableau trié d'éléments
    :: param x (variable)       :: l'élément à chercher dans le tableau
    :: return (NoneType ou int) :: l'indice de l'élément ou None
    .. Précondition 1 :: le tableau doit être NON 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(t) - 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 t[c] == x:
        return c
    else:
        if t[c] < x:
            g = c + 1
        elif t[c] > x:
            d = c - 1
        return recherche_dicho(t, x, g, d)

Conclusion : 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.

Nous avions vu 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.

# Déclarations des classes
 
class Cellule:
    """Classe permettant de créer des cellules-maillons basiques"""
 
    def __init__(self, valeur, suivant):
        self.v = valeur
        self.s = suivant
 
    def renvoyer_cellule_finale(self):
        if self.s == None:
            return self
        else:
            return self.s.renvoyer_cellule_finale()
 
    def valeur_max(self, maxi):
        if self.v > maxi:
            maxi = self.v
        if not self.s:
            return maxi
        else:
            return self.s.valeur_max(maxi)
 
class Liste:
    """Classe implémentant une Liste sous forme Liste chaînée """
 
    def __init__(self, tete=None):
        self.tete = tete
 
    def liste_vide(self):
        return self.tete == None
 
    def maximum(self):
        """Renvoie la valeur maximum de la liste"""
        if not self.liste_vide():
            maxi = self.tete.v
            if self.tete.s:
                return self.tete.s.valeur_max(maxi)
            else:
                return maxi
 
# Instructions du 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 ?

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

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

L'élément important pour trouver les valeurs d'un dictionnaire est de connaître... les clés. Voici la façon "implicite" de trouver les clés. Nous éviterons de l'utiliser par la suite.

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

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

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

On peut obtenir le même résultat en notant clairement qu'on utilise la méthode keys() sur le dictionnaire. Cette façon de faire est à privilégier sur vos copies.

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° 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 keys().

`1`	`def valeur_existe(d:dict, v:Elt) -> bool:`

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 ?

...CORRECTION...

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° Quel est le coût de la recherche ?

Correction ?

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

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 :

13° 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().

`1`	`def valeur_existe(d:dict, v:Elt) -> bool:`

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 ?

...CORRECTION...

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° Quel est le coût de la recherche ?

Correction ?

...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 veut juste lire les valeurs d'un dictionnaire (sans vouloir les modifier), on peut utiliser :

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]

Si on veut modifier les valeurs, il faut connaître la clé et nous n'avons donc pas le choix :

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

C'est donc comme avec le FOR "numérique" pour obtenir un indice ou le FOR nominatif pour accéder directement aux valeurs du tableau.

Si on veut juste lire les valeurs d'un tableau, nous avons deux choix :

soit for elt in t et on accédera aux éléments avec elt
soit for i in range( len(t) ) et on accédera aux éléments avec t[i]

Si on veut modifier les cases :

for i in range( len(t) ) et on modifiera les éléments avec t[i] = nouveau

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.

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).

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 :

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 :

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

On peut même se passer des parenthèses autour du tuple, mais on rend alors le code moins explicite.

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

15° 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().

`1`	`def valeur_existe(d:dict, v:Elt) -> bool:`

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 ?

...CORRECTION...

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° Quel est le coût de la recherche ?

Correction ?

...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 ?

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

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 ?

...CORRECTION...

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

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'ordonner 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

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 plus qu'un simple tableau dynamique, le type dict de Python possède plus de propriétés qu'un 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° 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.

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 ?

...CORRECTION...

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().

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 ?

...CORRECTION...

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

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 ?

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 table 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

qu'il existe plusieurs entrées qui peuvent provoquer la même sortie
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ères à 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 quoi 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 : 05 12 2020
Auteur : ows. h.

⏪

⏫

⏩