1. Pourquoi un autre type ?¶
Lorsque l'on cherche un élément dans une liste ou un tuple, la recherche se fait en \(O(n)\) dans le pire des cas. On souhaite trouver un élément plus rapidement en utilisant ce qu'on appelle une clé.
Pour cela on utilise tableau associatif appelé dictionnaire qui associe une clé à une valeur.
A la différence des séquences (tuples et listes) les éléments ne sont donc pas récupérables en utilisant des indices correspondant à leurs positions.
C'est en utilisant une clé associé à une valeur que l'on accède à un élément.
Dans le pire des cas cette recherche est aussi en \(O(n)\), on peut alors se demander quel est l'intérêt d'utiliser un dictionnaire. En fait, en pratique le cas où la recherche se fait en \(O(n)\) arrive rarement et en moyenne la complexité est en \(O(1)\), c'est à dire en temps constant.
2. Un tableau associatif¶
On peut intuitivement comprendre pourquoi on peut obtenir dans le pire des cas une complexité linéaire et pourquoi ce cas arrive rarement en pratique . Il existe plusieurs techniques, je présente celle qui correspond au chaînage.
On utilise une fonction de hachage pour déterminer la position d’un couple clé / valeur en fonction de la clé. Par exemple, dans le schéma ci-dessous, hash(S) = 3.
Lorsque deux clés différentes ont la même valeur retournée par la fonction de hachage, nous disons qu’il y a collision.
On voit donc que pour que le pire des cas soit linéaire il faudrait qu’un grand nombre de clés aient la même valeur de hachage. En pratique on utilise des fonctions telles que la probabilité de collisions soit suffisamment faible.
Arithmétique modulaire
Pour réduire l’espace des valeurs reçues en entrée et leur affecter un indice (plus précisément une adresse mémoire) qui correspond à la position de la clé / valeur dans le tableau, on utilise habituellement l’arithmétique modulaire et plus précisément la congruence sur les entiers.
Donnons comme exemple, l'« arithmétique de l'horloge » qui se réfère à l'« addition » des heures indiquées par la petite aiguille d'une horloge : concrètement, si nous commençons à 9 heures et ajoutons 4 heures, alors plutôt que de terminer à 13 heures (comme dans l'addition normale), nous sommes à 1 heure.
De la même manière, si nous commençons à minuit et nous attendons 7 heures trois fois de suite, nous nous retrouvons à 9 heures (au lieu de 21).
Fondamentalement, quand nous atteignons 12, nous recommençons à zéro ; nous travaillons modulo 12. Pour reprendre l'exemple précédent, on dit que 9 et 21 sont congrus modulo 12.
Ce que l’on note :
\(21 \equiv 9[12]\)
Deux entiers a et b sont congrus modulo n lorsque a - b est divisible par n.
Etudions maintenant l’implémentation des dictionnaires en Python.
3. Dictionnaire Python¶
3.1) Créer un dictionnaire et accéder à une valeur à partir de sa clé¶
Création d’un dictionnaire qui associe un nom (clé) et une valeur (numéro de téléphone).
Pour accéder à une valeur valeur à partir de la clé cle d'un dictionnaire dictionnaire, il suffit d'utiliser la notation suivante :
Par exemple si je souhaite accéder au numéro de téléphone de fifi :
Si on cherche à accéder à une valeur en utilisant une clé qui n’existe pas alors on obtient une erreur de type KeyError:
contacts['mcnugget']
Traceback (most recent call last):
File "<input>", line 3, in <module>
KeyError: 'mcnugget'
3.2) Modifier la valeur associée à une clé et ajouter un couple clé / valeur¶
Pour modifier le numéro de fifi:
Pour ajouter un couple clé / valeur:
3.3) Vérifier si une clé est présente dans un dictionnaire¶
On utilise le mot clé in
3.4) Récupérer toutes les clés / valeurs¶
Pour récupérer toutes les clés d’un dictionnaire :
Il peut parfois être utile de convertir ces clés en liste :
Itérer toutes les clés et valeurs d’un dictionnaire en utilisant une boucle :
On peut également plus simplement faire:
Note : contrairement à ce qui est indiqué sur certains sites de NSI, utiliser contacts.items() ne sera pas moins performant en général que contacts.keys() (second exemple)
On peut également récupérer toutes les valeurs :
3.5) Méthode get¶
Pour éviter d’obtenir une erreur de type KeyError lorsque l’on utilise une clé qui n’existe pas, il peut être avantageux d’utiliser la méthode get qui retourne None lorsque la clé n’existe pas.