Des tableaux dont les éléments sont accessibles par des clés plutôt que par des indices entiers.
rot13 = {} # initialisation
abc = "abcdefghijklmnopqrstuvwxyz"
for i in range(26) :
rot13[abc[i]] = abc[(i+13)%26]
Par compréhension :
abc = "abcdefghijklmnopqrstuvwxyz"
rot13 = {abc[i] : abc[(i+13)%26] for i in range(26)}
Utilisation :
def encode(texte) :
secret = ""
for char in texte :
if char in rot13 : # vérifie si char est une clé
secret += rot13[char]
else :
secret += char
return secret
Comment aurait-on fait seulement avec des listes ?
for k in dico.keys() :
print(k)
équivalent à :
for k in dico :
print(k)
Pour obtenir la liste des clés :
L_keys = list(dico.keys())
for v in dico.values() :
print(v)
équivalent à :
for k in dico :
print(dico[k])
Pour obtenir la liste des valeurs :
L_valeurs = list(dico.values())
for k,v in dico.items() :
print(f"{k}:{v}")
équivalent à :
for k in dico :
print(f"{k}:{dico[k]}")
Pour obtenir la liste des tuples (clé,valeur) :
L_couples = list(dico.items())
dico = {}
dico[(46.16,-1.15)] = "La Rochelle" # ajoute la clé
del dico[(46.16,-1.15)] # retire la clé
Un tuple est une clé possible,
car c’est une structure non mutable.
Par contre, l’instruction suivante lève une erreur :
dico[[46.16,-1.15]] = "La Rochelle"
TypeError: unhashable type: 'list'
Quelle est la taille du dictionnaire Notes ?
Notes = {"Bob" : 5 , "Joe" : 12 , "Bob" : 10}
2
Les commandements :
Une clé est unique
Une clé est non mutable
En fait, le 2e commandement
est là pour s’assurer du premier…
On se fixe au départ une taille de tableau.
Pour Python, c’est 64 bits
(taille d’un espace mémoire).
On utilise ensuite une fonction de hachage
qui transforme l’objet non mutable donné en argument en un entier compris entre $0$ et $2^{64}-1$.
Python donne accès nativement
à la fonction de hachage hash :
>>> hash(28)
28
>>> hash(28.0)
28
>>> hash(28.1)
230584300921372700
>>> hash("2")
7599881246238757835
>>> hash("Eh alors ?")
2149932438138104006
>>> hash("🍇")
3426984333240570475
>>> hash((1,2,3))
529344067295497451
Ses propriétés peuvent être interrogées :
>>> import sys
>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
modulus = $2^{61}-1$ est le plus grand
nombre premier de Mersenne $<2^{64}$
(ça permet d’optimiser la distribution des
entiers obtenus tout en ayant des calculs rapides)
Une fonction de hachage
travaille en temps constant
(complexité en $O(1)$).
Et que faire si le hachage donne le même entier pour deux clés différentes
(ce qu’on appelle une collision) ?
Une idée possible est de commencer
une liste chaînée depuis l’emplacement
déjà occupée du tableau.
Si ça n’arrive pas trop souvent,
l’accès à une valeur et l’insertion d’une nouvelle reste globalement en $O(1)$.
Sa rapidité !
Supposons que l’on veuille la note de Bob :
# Liste de tuples :
L = [("Joe",12),("Bill",8),("Al",4),("Bob",13),("Tom",9)]
# Dictionnaire
D = { "Joe":12 , "Bill":8 , "Al":4 , "Bob":13 , "Tom":9 }
Pour afficher la note de Bob avec L :
for prenom,note in L :
if prenom == "Bob" :
print(note)
ou
for i in range(len(L)) :
if L[i][0] == "Bob" :
print(L[i][1])
Complexité ?
$\color{red}O(len(L))$
Pour afficher la note de Bob avec D :
print(D["Bob"])
Complexité ?
$\color{red}O(1)$
On a mis à profit cette rapidité dans l’implémentation de BFS et DFS pour tester
si un sommet avait déjà été visité.
Utiliser une liste répertoriant les sommets visités plutôt qu’un dictionnaire fait passer la complexité de linéaire à quadratique !
Pas bien 🤮
from collections import deque
def parcours_largeur(G,depart):
file = deque()
file.append(depart)
Vus = []
Sommets = []
while file : # tant que la file n'est pas vide
sommet = file.popleft()
if not sommet in Vus :
file += G[sommet]
Vus.append(sommet)
Sommets.append(sommet)
return Sommets
Bien 😇
from collections import deque
def parcours_largeur(G,depart):
file = deque()
file.append(depart)
Vus = {s : False for s in G}
Sommets = []
while file : # tant que la file n'est pas vide
sommet = file.popleft()
if not Vus[sommet] :
file += G[sommet]
Vus[sommet] = True
Sommets.append(sommet)
return Sommets