Correction : Dictionnaires

Implémentation par tableau de tableaux

Un élément du tableau = un tableau de 2 éléments [clef, valeur].

def creer_dico_vide():
    return []

def ajouter(dico, clef, valeur):
    dico.append([clef, valeur])
    return dico

def modifier(dico, clef, valeur):
    for i in range(len(dico)):
        if element[i][0] == clef:
            element[i][1] = valeur
            return dico
    assert not True, "KeyError : Clé introuvable dans le dictionnaire." # arrivé ici, c'est que la modification n'a pas été faite

def supprimer(dico, clef):   
    indice = None # indice de l'élément à supprimer. "None" signifiera que cet indice n'existe pas ( = la clé n'est pas présente dans le dictionnaire )
    for i in range(len(dico)): # recherche de cet indice
        if dico[i][0] == clef:
            indice = i
    assert index is not None, "KeyError : Clé introuvable dans le dictionnaire." # si 'indice' est toujours None, c'est que la clé à supprimer n'a pas été trouvée
    dico[indice][1] = valeur # sinon, on fait effectivement la modification
    return dico

def rechercher(dico, clef):
    for element in dico:
        if element[0] == clef:
            return element[1]
    assert not True, "KeyError : Clé introuvable dans le dictionnaire." 
    
# Quelques manipulations :
dict = creer_dico_vide()
print(dict)
dict = ajouter(dict, 'a', 'alpha')
dict = ajouter(dict, 'b', 'bêta')
dict = ajouter(dict, 'c', 'ceta')
dict = ajouter(dict, 'd', 'delta')
dict = ajouter(dict, 'e', 'epsilon')
dict = ajouter(dict, 'f', 'phi')
dict = modifier(dict, 'f', 'gamma')
print(dict)

dict = supprimer(dict, 'd')
print(dict)

print(rechercher(dict, 'f'))
print(rechercher(dict, 'z'))		
			

Remarques :

• noter l'utilisation des assertions pour lever une exception ( = une erreur à l'exécution ).
  Si on veut lever une exception dans tous les cas ( comme dans la fonction modifier, on utilise une expression qui sera toujours évaluée à False : 1 == 2, not True,...
• la suppression de l'élément à supprimer ( fonction supprimer ) doit se faire après la recherche de l'indice de cet élément dans le tableau ( et pas dans la boucle de recherche elle-même ) : en effet, il ne faut surtout pas modifier une structure de données alors qu'on est en train de la parcourir, cela peut entraîner des problèmes...

Rechercher une clé donnée oblige donc à parcourir l'intégralité du tableau dans le pire des cas : complexité en O(n).

Recherche en temps constant : hachage

Caractéristiques d'une clé de hachage

1. Rôle : calculer et renvoyer une valeur entière à partir des données d'un objet ( les clés pour un dictionnaire )
2. Caractéristiques :
   • une clé de hashage doit être rapide à calculer.
   • quelque soit la taille des données de l'objet, la clé de hashage doit toujours avoir la même taille.
   • une clé de hashage doit être unique : elle ne dépend que des données de l'objet; une petite modification de celles-ci doit entraîner une grande variation de la clé de hashage.

Implémentation simplifiée d'un hachage

def creer_dico_vide():
    return [None for i in range (128)] # ou [None]*128

def ajouter(dico, clef, valeur):
    indice = ord(clef)
    assert dico[indice] is None, "La clé existe déjà dans le dictionnaire."
    dico[indice] = [clef, valeur]
    return dico

def modif(dico, clef, valeur):
    indice = ord(clef)
    assert dico[indice] is not None, "KeyError : clé introuvable"
    dico[indice][1] = valeur
    return dico

def supprimer(dico, clef):
    indice = ord(clef)
    assert dico[indice] is not None, "KeyError : clé introuvable"
    dico[ord(clef)] = None
    return dico
    
def rechercher(dico,clef):
    indice = ord(clef)
    assert dico[indice] is not None, "KeyError : clé introuvable"
    return dico[indice][1]		
			

Ici, rechercher une valeur revient à :

• calculer la valeur de hachage de la clé
• adresser un élément dans un tableau, à un indice égal au hachage de la clé

Ces deux opérations ne dépendent pas de la taille du tableau, elle se font donc en temps constant ( O(1) ).

Comparaison des temps de recherche

Valeurs obtenues :

Conclusion :

• le temps de recherche dans le dictionnaire ne dépend pas de la taille de celui-ci : recherche en temps constant O(1).
• le temps de recherche dans la liste est multiplié sensiblement par 10 quand la taille de la liste est multipliée par 10 : recherche en temps linéaire O(n).