Le type abstrait Dictionnaire

• Un agenda téléphonique -> clefs : noms ; valeurs : numéros de téléphone
• Fichier de carte d'identité -> clefs : numéros de carte ; valeurs : noms et prénoms des titulaires

Un dictionnaire peut aussi regrouper plusieurs informations de natures différentes :

• prénom : Léo
• nom : Gruoleb
• classe : 111
• spécialité 1 : NSI
• spécialité 2 : NSI
• option fac : Latin
• date de naissance : 03/12/2004

Ici prénom, nom, classe, spécialité 1, spécialité 2, option fac et date de naissance sont les clefs.
Et Léo, Gruoleb, 111, NSI, Latin, 03/12/2004 sont les valeurs.

Utiliser les dictionnaires python

Comme vous le savez, le type dictionnaire existe déjà en python, vous l'avez sûrement déjà expérimenté l’année dernière . Cependant, avant de "soulever le capot" du langage de programmation et de tenter de mettre en place nous même ce type abstrait de données nous allons un peu utiliser les dictionnaire en python, afin de nous remémorer leur fonctionnement.
Voici donc 2 exercices simples qui vous permettrons de vous remettre en tête le fonctionnement des dictionnaires en python.
Si vous manquez de bases...Tout est là.

Manipulations de base

Score au Scrabble

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

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

Primitives

Revenons maintenant au TAD "dictionnaire". Avant de l'implémenter étudions en détail ce TAD :

Pour "faire fonctionner" un dictionnaire, il faut disposer des opérations suivantes :

• créer un dictionnaire vide
• ajouter un élément dans le dictionnaire : on associe une nouvelle valeur à une nouvelle clé
• modifier un couple {clé:valeur} en remplaçant la valeur courante par une autre valeur (la clé restant identique)
• supprimer une clé (et donc la valeur qui lui est associée)
• rechercher une valeur à l'aide de la clé associée à cette valeur.

Comment coder un dictionnaire

Les dictionnaires peuvent être implémentées de différentes façons, comme vous avez déjà une bonne expérience de ce genre d'exercice nous n'aborderons qu'un seul codage :
Le codage grâce à un tableau indexé (une liste python).

codage par un tableau

Rechercher dans un dictionnaire en "temps constant" (O(1)) !

Comme vous avez pu le voir en codant la fonction rechercher, il est nécessaire de parcourir le dictionnaire pour trouver une clef...Pourtant une des particularités des dictionnaires (notamment en python), c'est de réaliser des recherches en "temps constant".
Cela signifie que le temps de recherche dans un dictionnaire n'augmente pas avec sa taille :

Le principe

Une seule question : comment ça marche ?
Et bien contrairement à ce que nous avons fait dans la partie précédente, les clef ne sont pas rangées au hasard en mémoire, mais leur place est déterminée par la valeur de la clef elle même. Il existe ainsi une fonction de hashage qui associe à chaque clef un entier qui déterminera la place des données stockées en mémoire. le processus se fait donc en deux temps :

• Lors de l'insertion d'un couple clef valeur, on applique à la clef la fonction de hashage : hashage(clef) renvoie un entier qui détermine la place de la clef et de la valeur en mémoire.
• Lors de la recherche d'une clef, on applique la fonction à la clef recherchée et hashage(clef) nous donne l'emplacement mémoire ou retrouver les données, il n'est pas nécessaire de parcourir le dictionnaire, on a bien une recherche en O(1) !!!!

Nous ne détaillerons pas les difficultés que l'on peut rencontrer pour construire une fonction de hashage, cependant :

Application simplifiée

Nous ne pouvons pas mettre en œuvre une fonction de hashage complexe (et d'ailleurs ce n'est pas au programme de terminale), mais pour bien comprendre le fonctionnement de la recherche en O(1) dans un dictionnaire vous allez améliorer votre travail précédent pour simuler la recherche en temps constant dans un dictionnaire.

Un contexte simplifié

Nous allons nous intéresser à un dictionnaire dont les clefs ne peuvent être que des caractères de la table AASCII. la taille du dictionnaire sera adonc limitée à 128 éléments maximum.
La fonction de hashage que nous allons utiliser est la fonction ord(). cette fonction renvoie le code ASCII correspondant à un caractère. Ainsi :

>>> ord('a')
97			
			

Comparaison des temps de recherche sur un tableau ou un dictionnaire en python

Nous allons maintenant faire quelques mesures de temps de recherche dans un tableau et dans un dictionnaire en utilisant les type construits existant dans python.
Voici la démarche que nous allons suivre :

• Construire par compréhension un dictionnaire et une liste comprenant des nombres aléatoires pris entre 0 et 1000
• Rechercher un élément ou une clef qui n'est pas présente dans chaque structure avec l'instruction in (rechercher une valeur non présente nous garanti que l'on parcourra l'ensemble des structures de données)
• Mesurer dans chaque cas le temps de recherche

La mesure de temps se fera grâce au module timeit qui permet de systématiser ce genre de tests. Voici le code de départ :

 
from random import *
from timeit import timeit

liste =[randint(0,1000) for i in range (1000000)]
dictionnaire={randint(0,1000): randint(0,1000) for i in range(1000000)}

print('liste : ',timeit(stmt='1001 in liste', globals=globals(), number=1000))
print('dictionnaire ',timeit(stmt='1001 in dictionnaire', globals=globals(), number=1000))
		

Les paramètres de timit sont les suivants :

• La chaîne de caractères stmt correspond à l’instruction qui sera exécutée.
• le paramètre globals permet d'utiliser les structures de données créées en dehors de la chaine stmt précédente
• number permet d'exécuter l'instruction contenue dans stmtautant de fois que nécessaire (afin d'être sur de ne pas tomber sur un état particulier dans les processus au moment de la mesure du temps)