Algo Parcours Suite

Identification

Infoforall

3 - Différents algorithmes de parcours


Nous avons vu que parcourir un tableau élément par élément nécessite un algorithme dont le coût est linéaire : sa complexité est Θ(n).

Nous allons voir aujourd'hui d'autres algorithmes ayant la même complexité (le même cout) mais permettant de faire d'autres choses.

On y parlera d'ailleurs de tableaux et de dictionnaires.

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...

Prérequis ✎ : Python - Stocker dans un dictionnaire

Evaluation ✎ : questions 01-02-05-06-07-16-18.

1 - Recherche du premier indice comportant un élément

Nous avons vu un algorithme permettant de rechercher un élément dans un tableau :

Algorithme de recherche

    i0

    TANT QUE i < longueur et que t[i] est différent de x

      ii + 1

    Fin du TANT QUE

    SI i < longueur

      Renvoyer i

    Fin du Si

    Renvoyer VIDE

On peut alors l'implémenter de différentes façons en fonction du langage utilisé. Voici l'exemple de sa transposition directe en Python (vu dans l'activité précédente).

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 trouverIndex(t, x): '''Fonction qui renvoie l'indice de l'élément x dans le tableau t. None en cas d'échec de la recherche :: param t(list) :: un tableau contenant le même type d'élément que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: le numéro d'indice :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' i = 0 longueur = len(t) while i < longueur and t[i] != x : i = i + 1 if i < longueur : return i return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()

✎ 01° Lancer le programme en mémoire pour vérifier qu'il passe bien les tests de la documentation. Rajouter un autre exemple dans la documentation au passage.

Rappel : les exemples de la documentation sont bien de la DOCUMENTATION. C'est l'activation de la fonction testmod présente dans le module doctest.

On peut néanmoins faire plus simple en Python en profitant des boucles FOR et du fait qu'on sorte immédiatement des fonctions dès qu'on rencontre un return. De l'extérieur, ça ne change rien : seul le code interne est différent.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
def trouverIndex(t, x): '''Fonction qui renvoie l'indice de l'élément x dans le tableau. None en cas d'échec de la recherche :: param t(list) :: un tableau contenant le même type d'élément que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: le numéro d'indice :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' for i in range(len(t)) : if t[i] == x : return i return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()

✎ 02° Lancer le programme en mémoire pour vérifier qu'il passe bien les tests. Expliquer pourquoi la fonction ne renvoie pas systématiquement None alors que la dernière instruction de la fonction (ligne 17) est return None.

Ici, on n'utilise pas une boucle FOR nominative car on a besoin de renvoyer le numéro d'indice.

2 - Recherche de valeur maximale ou minimale

Nous n'avons pas le choix : il va falloir lire les éléments un par un. Et jusqu'au bout cette fois.

Il s'agit donc encore une fois d'un algorithme linéaire. On pourra donc écrire Θ(n).

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56

Comme vous le voyez, le principe est de lire les éléments un par un et d'écraser les valeurs anciennes du maximum si on en découvre une plus grande.

Seule la valeur finale de maxi après avoir parcouru tout le tableau a donc un sens.

Algorithme de recherche de maximum

Principe

On place le premier élément du tableau en tant que valeur maximale. Ensuite, on compare chaque élément lu séquentiellememt à ce maximum : on remplace le maximum si l'élément lu est plus grand.

Description des entrées / sortie

  • ENTREES :
    • t : un tableau d'au moins un élément.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : la valeur maximale.

Description de l'algorithme

    maxit[0]

    i ← 1

    TANT QUE i < longueur

      SI t[i] > maxi

        maxit[i]

      Fin du SI

      ii + 1

    Fin du TANT QUE

    Renvoyer maxi

03° Montrer la terminaison de l'algorithme : on doit pouvoir montrer que le TANT QUE peut s'écrire TANT uN > 0 avec uN une suite strictement décroissante d'entiers.

...CORRECTION...

Etape 1 : avant de rentrer dans la boucle

Ligne 2 : on voit que i vaut 1 initialement.

2
i1

Comme nous avons fait 0 tour de boucle TANT QUE, nous noterons ceci :

i0 = 1 (1)

Etape 2 : que se passe-t-il à chaque tour de boucle ?

Ligne 6 : on voit qu'on augmente i de 1 à chaque tour de boucle. La raison vaut donc +1.

6
ii + 1

On peut donc écrire que i après n+1 tours de boucles vaut i après n tours plus 1.

iN+1iN + 1

Nous avons donc affaire à une suite iN arithmétique de raison r = +1 et de valeur initiale i0 = 1 (voir (1)).

iN = i0 + r*n

iN = 1 + 1*n

On obtient donc juste :

iN = 1 + n (2)

Etape 3 : recherche du VARIANT

On cherche à voir si la condition de boucle de la ligne 3 peut s'écrire sous cette forme :

L3?
TANT QUE un > 0:

On commence la démonstration en récupérant la condition de boucle réelle et on tente de la ramener à la forme attendue pour prouver la terminaison :

L3
TANT QUE i < longueur:

On remplace donc i par iN et on en tente de revenir à la forme attendue.

L3
TANT QUE iN < longueur:

On remplace iN en utilisant (2) :

L3
TANT QUE (1 + n) < longueur:

Pour revenir à la forme attendue, on écrit b > a plutôt que a < b :

L3
TANT QUE (1 + n) < longueur:
L3
TANT QUE longueur > (1 + n):

Pour revenir à la forme attendue, on doit passer les termes de droite à gauche :

L3
TANT QUE longueur > + (1 + n):
L3
TANT QUE (longueur - (1 + n) ) > 0 :
L3
TANT QUE (longueur - 1 - n) > 0 :

Nous obtenons alors le VARIANT de boucle uN exprimé de cette façon :

L2
while uN > 0:    avec uN = (longueur - 1) - n

Etape 4 : conclusion

On voit que le variant est une suite d'entiers dont la raison est r = -1 : on perd 1 à chaque fois. La suite est donc décroissante.

Nous obtenons donc bien

  1. une condition du type  while uN > 0 
  2. avec  uN = (longueur - 1) - n  une suite d'entiers strictement décroissante.

Nous venons donc de prouver la terminaison de cette boucle.

Voici une implémentation en Python utilisant les boucles bornées FOR sur les indices : elle joue le même rôle que la boucle non bornée WHILE.

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 trouverMax(t): '''Fonction qui renvoie la valeur maximale lue dans le tableau :: param t(list) :: un tableau d'éléments qu'on peut comparer :: return (type des valeurs du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMax(test) 60 >>> test = [10,20,60,40,50,100] >>> trouverMax(test) 100 >>> test = [100,20,60,40,50] >>> trouverMax(test) 100 ''' maxi = t[0] for i in range( 1, len(t) ): if t[i] > maxi : maxi = t[i] return maxi if __name__ == '__main__' : import doctest doctest.testmod()

04° La boucle FOR commence-t-elle à zéro ?

Autre question : quelle ligne poserait problème si le tableau était vide ?

...CORRECTION...

Non, elle commence à 1.

Par défaut, si on ne précise pas la valeur de départ, l'interpréteur Python place 0. Mais on peut placer une première valeur.

Sinon, c'est maxi = t[0] qui posera problème avec un tableau vide : l'élément 0 n'existe pas.

range

Taper range(6) permet d'obtenir l'ensemble suivant (0,1,2,3,4,5).

En réalité, Python remplit la valeur initiale par 0 et l'incrémentation par 1.

Taper range(6) revient à avoir tapé range(0, 6, 1)

Quelques exemples :

>>> for x in range(0,6,1) : print(x,end='-') 0-1-2-3-4-5- >>> for x in range(2,6,1) : print(x,end='-') 2-3-4-5- >>> for x in range(1,6,2) : print(x,end='-') 1-3-5- >>> for x in range(6,1,-1) : print(x,end='-') 6-5-4-3-2-

✎ 05° Ecrire une fonction trouverMin en vous inspirant de notre version maximale.

Dernière fonction typique : la moyenne.

On doit alors créer une variable-mémoire, disons s (s comme somme) dans laquelle on place la somme progressive des éléments du tableau.

Connaissant la longueur du tableau, on va alors renvoyer s / longueur.

✎ 06° Ecrire un algorithme (en français donc) qui réalise cette tâche. L'algorithme doit être transposable dans n'importe quel langage et ne doit pas contenir d'instructions non basiques.

Et voici une version Python possible de cette fonction :

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 trouverMoy(t): '''Fonction qui renvoie la valeur moyenne des valeurs du tableau :: param t(list) :: un tableau NON VIDE d'entiers ou de flottants :: return (float) :: la valeur moyenne :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMoy(test) 36.0 >>> test = [100,20,60,40,50] >>> trouverMoy(test) 54.0 ''' s = 0 longueur = len(t) for i in range(longueur): s = s + t[i] return s / longueur if __name__ == '__main__' : import doctest doctest.testmod()

✎ 07° La méthode du FOR avec l'indice n'est pas indispensable : on ne modifie pas les éléments du tableau. Créer une fonction qui calcule la moyenne mais en utilisant plutôt  for v in t , où on note v pour valeur.

Dernière chose : on remarque que si le tableau est vide, sa longueur vaut 0. C'est bien pour cela que nous avons rajouté la précondition documentaire sur la ligne 4.

4
:: param t(list) :: un tableau NON VIDE d'entiers ou de flottants

08° QCM. Ces algorithmes (recherche, maximum, minimum et moyenne) ont donc besoin de lire les éléments un par un. Sont-ils :

  • A : Des algorithmes à complexité constante (en Θ(1)) : temps d'exécution constant quelque soit la taille du tableau d'entrée
  • B : Des algorithmes à complexité linéaire (en Θ(n)) : le temps d'exécution double si l'entrée double
  • C : Des algorithmes à complexité quadratique (en Θ(n2)) : le temps d'exécution est multiplié par 4 si l'entrée double
  • D : Des algorithmes à complexité cubique (en Θ(n3)) : le temps d'exécution est multiplié par 8 si l'entrée double

...CORRECTION...

Comme on parcourt le tableau séquentiellement et une seule fois, la réponse est bien entendue la réponse B.

3 - Et pour les dictionnaires ?

Cette partie nécessite que vous sachiez travailler avec les dictionnaires.

Deux solutions :

  1. Vous n'avez pas encore eu le temps de faire les activités Python traitant des dictionnaires (Stocker dans un dictionnaire et Lire le contenu d'un dictionnaire)
  2. Vous les avez réalisées mais ça date d'avant les vacances : plus trop de souvenirs...

Dans un cas comme dans l'autre, nous allons voir un petit résumé dans la partie FAQ en bas de page.

Revenez ici ensuite.

Voyons maintenant comment faire tout cela avec les dictionnaires.

On peut faire la même chose avec les dictionnaires en lisant une à une les clés à l'aide de la méthode keys. Il suffit de modifier un peu le code : la recherche se fait juste par clé et pas par indice.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(d, x): '''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche :: param d(dict) :: un dictionnaire :: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire :: return (comme les clés) :: la clé correspondant à la valeur x :: exemples :: >>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'} >>> trouverCle(test, 'data') 'données' >>> trouverCle(test, 'stack') ''' for cle in d.keys(): if d[cle] == x : return cle return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()
Méthode keys

La méthode des dictionnaires keys permet de créer un ensemble contenant les clés du dictionnaire. On pourra ainsi le lire une à une avec une boucle for.

Cela nous permettra d'écrire un code qui veut dire en Français : Pour chaque clé du dictionnaire, réalise ce qui est indenté.

13 14 15
for cle in d.keys(): if d[cle] == x : return cle

09° Expliquer le fonctionnement de ce programme. Vous pouvez prendre l'exemple du doctest si vous le désirez. Attention, vous devez être capable d'écrire ce programme seul lors du DS. Comprendre son fonctionnement est donc fondamental.

...CORRECTION...

Si le dictionnaire est {'boucle':'loop', 'données':'data', 'tant que':'while'}, alors on commence la boucle avec cle valant 'boucle'.

On vérifie donc via la ligne 14 si la valeur d[cle] correspond bien à x.

Si c'est le cas, on sort de la fonction en renvoyant la clé.

Sinon, on passe à la clé 'données', puis la clé 'tant que'...

Comme vous le voyez, on est obligé de taper d[cle] pour obtenir la valeur associée à la clé.

Python intègre une méthode qui renvoie la clé ET la valeur, sous forme d'un tuple. Voici comme cela fonctionne :

Méthode items

La méthode des dictionnaires items permet de créer un ensemble contenant des tuples : les clés du dictionnaire ET leurs valeurs associées. On pourra ainsi lire une à une clé et valeur avec une boucle for.

13 14 15
for (cle, valeur) in d.items(): if valeur == x : return cle

10° En regardant la ligne 13, à quoi voit-on que items renvoie bien un tuple ? Cette indication est-elle indispensable pour l'interpréteur ?

...CORRECTION...

Aux parenthèses autour de (cle, valeur).

Elles sont au final plus destinées à l'humain qui lit le code qu'à l'interpréteur Python qui l'interprète.

Dans la plupart des codes, les parenthèses seront absentes.

11° Exécuter le code suivant pour placer la fonction en mémoire. La tester dans le Shell. Fournir au moins un de vos tests ainsi que le résultat. Expliquer alors comment fonctionne la fonction en vous basant sur votre exemple.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(d, x): '''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche :: param d(dict) :: un dictionnaire :: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire :: return (comme les clés) :: la clé correspondant à la valeur x :: exemples :: >>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'} >>> trouverCle(test, 'data') 'données' >>> trouverCle(test, 'stack') ''' for (cle, valeur) in d.items(): if valeur == x : return cle return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()

...CORRECTION...

Si le dictionnaire est { 'a':45, 'b':55, 'c':20}

  • Lors de la première boucle, on aura cle valant 'a' et valeur valant 45.
  • Lors du deuxième passage, on aura cle valant 'b' et valeur valant 55.
  • Lors du dernier passage, on aura cle valant 'c' et valeur valant 20.

Maintenant que nous savons trouver le premier élément, nous allons voir d'autres lectures séquentielles : la recherche d'un maximum ou d'un minimum.

Comment choisir si on utilise keys ou items ?

C'est comme on veut. On a juste le choix et les deux méthodes sont au programme.

Pour la recherche du maximum et du minimum, reprenons par exemple notre exemple des lettres dans le texte de Lovecraft, celui de l'activité Python.

1 2 3 4 5 6 7 8 9 10 11
lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 }

Nous allons devoir feinter pour l'initialisation puisqu'il n'y a pas de première valeur : l'indice 0 n'existe pas.

L'une des solutions peut consister à placer None dans maxi au départ. Regardons ce que cela peut donner :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverMax(d): maxi = None for cle in d.keys(): if maxi == None : maxi = d[cle] elif d[cle] > maxi : maxi = d[cle] return maxi

12° Placer la fonction trouverMax et le dictionnaire lettres en mémoire. Tester l'instruction suivante dans le Shell :

>>> trouverMax(lettres) 10006

Ca fonctionne. Mais ...

13° Imaginons que vous ayez un dictionnaire ayant 1 milliard d'entrées. Combien de fois allez-vous faire le test de la ligne 16 inutilement ?

...CORRECTION...

Comme on lit les entrées une à une et que maximum n'est None qu'au début, nous allons faire 999 999 999 fois le test pour rien.

Pour faire mieux, il faudra une valeur initiale qui soit la plus petite possible. Moins l'infini ?

Elle est encodé sous le nom de inf dans le module math de Python.

>>> from math import inf >>> -78000 > -inf True

Voilà une fonction de recherche de maximum basée sur une valeur initiale de -∞ et sur la méthode keys.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
from math import inf lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverMax(d): maxi = - inf for cle in d.keys(): if d[cle] > maxi : maxi = d[cle] return maxi

14° Mettre en mémoire la fonction et le dictionnaire. Tester dans le Shell :

>>> trouverMax(lettres) 10006

...CORRECTION...

Comme on lit les entrées une à une et que maximum n'est None qu'au début, nous allons faire 999 999 999 fois le test pour rien.

En réalité, nous n'avons pas besoin ici de la clé, nous n'avons besoin que des valeurs. Et bien, il existe une méthode permettant de faire cela !

  • La méthode keys permet de récupérer les clés du dictionnaire.
  • La méthode items permet de récupérer les clés ET les valeurs associées du dictionnaire.
  • La méthode values permet de récupérer les valeurs du dictionnaire.

15° Mettre en mémoire la fonction utilisant values et le dictionnaire. Tester dans le Shell :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
from math import inf lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverMax(d): maxi = - inf for valeur in d.values(): if valeur > maxi : maxi = valeur return maxi
>>> trouverMax(lettres) 10006

Comme vous pouvez le voir, on obtient juste la valeur maximum. Pas la lettre correspondante. Comment faire ? Utiliser la méthode items plutôt que juste values.

✎ 16° Utiliser la fonction trouverCleMax qui ne renvoie pas la VALEUR maximale mais un tuple contenant une CLE correspondant à la valeur MAXIMALE et la valeur elle-même.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
from math import inf lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverCleMax(d): maxi = - inf cle_max = None for cle, valeur in d.items(): if valeur > maxi : maxi = valeur cle_max = cle return cle_max, maxi

Que renvoie la fonction si on l'utilise ainsi dans le Shell ?

>>> trouverCleMax(lettres)

17° QCM. Cet algorithme qui a besoin de lire les éléments un par un est :

  • A : un algorithme à complexité constante (en Θ(1)) : temps d'exécution constant quelque soit la taille du tableau d'entrée
  • B : un algorithme à complexité linéaire (en Θ(n)) : le temps d'exécution double si l'entrée double
  • C : Un algorithme à complexité quadratique (en Θ(n2)) : le temps d'exécution est multiplié par 4 si l'entrée double
  • D : Un algorithme à complexité cubique (en Θ(n3)) : le temps d'exécution est multiplié par 8 si l'entrée double

...CORRECTION...

Comme on parcourt une à une toutes les clés du dictionnaire : linéaire.

✎ 18° Question finale pas facile : modifier maintenant la fonction précédente : on veut renvoyer le pourcentage de présence de cette lettre par rapport aux autres. Il va donc falloir calculer en plus le nombre total de caractères lus en faisant la somme des lettres rencontrées. La fonction devra donc renvoyer la clé maximale et le pourcentage de cette lettre dans le texte.

4 - FAQ

Un petit rappel sur les dictionnaires ?

1 - Déclaration d'un dictionnaire en Python

Les éléments délimitateurs sont les accolades. Chaque élément du dictionnaire est séparé des autres par une virgule. On donne d'abord la clé, suivi du symbole : puis de la valeur associée à la clé.

Exemple avec un dictionnaire de traduction FRANCAIS (pour la clé) et ANGLAIS (pour la valeur)

1
dicoFR_AN = {'encodage' : "encoding", 'cryptage' : "encryption"}

Pour plus de clarté, on pourrait taper le code ainsi :

1 2 3 4
dicoFR_AN = { 'encodage' : "encoding", 'cryptage' : "encryption" }

Une fois, cette variable en mémoire, on peut chercher son type :

>>> type(dicoFR_AN) <class 'dict'>
2 - Nombre de couples clés-valeurs enregistrées

On peut utiliser la fonction native len pour obtenir le nombre de clés-valeurs enregistrées dans un dictionnaire.

Exemple

>>> d = {'encodage' : "encoding", 'cryptage' : "encryption"} >>> nbr = len(d) >>> nbr 2

Le dictionnaire contient bien 2 ensembles clés-valeurs, et pas 4 éléments indépendants.

3 - Rajouter une clé et sa valeur associée

Contrairement aux tableaux, on peut facilement rajouter des éléments dans un dictionnaire.

Par contre, attention à la syntaxe : on utilise des crochets et pas des accolades !

Exemple

>>> d = {'encodage' : "encoding", 'cryptage' : "encryption"} >>> d {'encodage': 'encoding', 'cryptage': 'encryption'} >>> d['balise'] = "tag" >>> d {'encodage': 'encoding', 'cryptage': 'encryption', 'balise': 'tag'} >>> nbr = len(d) >>> nbr 3

Le dictionnaire contient bien maintenant 3 ensembles clés-valeurs.

4 - Accès à l'une des valeurs

Pour accéder à l'un des éléments en particulier, on peut noter le nom de la variable-dictionnaire suivi de crochets et y placer la clé voulue. Comme avec un tableau mais avec la clé plutôt qu'avec un index chiffré.

Cela donne donc la notation monDictionnaire[maCle] donne maValeur.

Exemple

>>> d['boucle'] 'loop' >>> d['tableau'] 'array'
>>> d['lapin'] 'Traceback (most recent call last): File "", line 1, in d['lapin'] KeyError: 'lapin'

On remarquera que tenter d'accéder à une clé inconnue crée une erreur et une interruption du programme. Comme lorsqu'on demande l'index 20 d'un tableau qui ne comporte que 10 éléments.

La correspondance clé - valeur donne ceci sur l'exemple

Clé 'boucle' 'tableau'
Elément 'loop' 'array'
5 - Que peut-on utiliser pour faire une clé ?

Presque tout.

La seule chose qui ne puisse pas être une clé, c'est une variable mutable ou un contenu mutable.

6 - Le dictionnaire Python est mutable

Les objets dict sont des objets mutables : on peut modifier leur contenu sans modifier la référence de l'objet en lui-même.

En gros, comme les tableaux.

Du coup, on peut modifier un dictionnaire qu'on passe en paramètre à une fonction par effet de bord.

La puissance de cet objet est que

  • Si on veut modifier la valeur associée à une clé existence : on modifie la valeur
  • Si on veut "modifier" la valeur associée à une clé qui n'existe pas en réalité : on crée le couple
  • Un exemple avec un oubli un remplacement initial de overflow par overflaw :

    >>> d = {} >>> d['boucle'] = 'loop' >>> d['dépassement'] = 'overflaw' >>> d {'boucle': 'loop', 'dépassement': 'overflaw'}

    Tentons de changer la valeur associée à "dépassement" :

    >>> d['dépassement'] = 'overflow' >>> d {'boucle': 'loop', 'dépassement': 'overflow'}

    Et pour rappel : si la clé n'existe pas, on crée juste une nouvelle entrée :

    >>> d['balise'] = 'tag' >>> d {'boucle': 'loop', 'dépassement': 'overflow', 'balise': 'tag'}
7 - Connaître l'existence d'une clé

C'est très facile, puisque c'est fondamental pour ne pas déclencher d'erreur.

Il existe un mot-clé Python qui permet de tester l'existence d'un élément dans un conteneur : in (dans, en anglais)

Il suffit d'évaluer l'expression suivante : cleTestee in monDict : l'interpréteur Python va renvoyer une valeur booléenne : True ou False.

Un exemple :

>>> d = {} >>> d['boucle'] = 'loop' >>> d['dépassement'] = 'overflow' >>> 'boucle' in d True >>> 'toto' in d False >>> 'loop' in d False

On notera donc qu'on teste l'existence de la clé et pas l'existence d'une valeur.

D'ailleurs, en réalité, il s'agit d'un raccourci pour l'expression suivante que nous allons voir dans la partie suivante : cleTestee in monDict.keys() : l'interpréteur Python va renvoyer une valeur booléenne : True ou False.

Un exemple :

>>> d = {} >>> d['boucle'] = 'loop' >>> d['dépassement'] = 'overflow' >>> 'boucle' in d True >>> 'toto' in d False >>> 'loop' in d False

Dans les prochaines activités Algorithmique, nous verrons comment créer un algorithme plus performant qu'un algorithme linéaire mais nécessitant des données triées.

Si vous avez fait l'activité OpenData, vous savez ce que nous allons faire maintenant : des calculs et de l'évaluation non pas d'un tableau de valeurs mais d'un tableau d'enregistrements !

Activité publiée le 13 03 2020
Dernière modification : 13 09 2020
Auteur : ows. h.