Les dictionnaires

On les appelle également tableaux associatifs.

Exemple

class Dictionnaire:

    def __init__(self):
        self._stockage = [None]*10

    def __getitem__(self, key):
        pass

    def __setitem__(self, key, value):
        pass

if __name__ == '__main__':
    d = Dictionnaire()
    d['toto'] = 10
    print(d['toto'])

Exercice 1 : approche naïve

Le Dictionnaire stockera dans un tableau des tuples de la forme (hash, clé, valeur).

  • Le constructeur initialise le tableau de stockage à une taille fixe et rempli de None
  • Créez une méthode __setitem__(self, key, value) qui permet de stocker la valeur value à la clé key.

Pour ce faire, il suffit de :

  1. calculer la clé de hashage de key avec la fonction Python hash existante ;

  2. ramener cette clé à un index dans le tableau par un calcul de reste modulo sa longueur ;

  3. insérer la valeur à l'index calculé.

Ensuite

  • Créez une méthode __getitem__(self, key) qui retourne la valeur stockée à l'index indiqué par la clé ou qui lance une exception si la clé n'est pas présente.
  • Testez votre code
if __name__ == "__main__":

    d = Dictionnaire()
    l = [1, 2, 3]

    for i in l:
        d[i] = i+10

    print([d[i] for i in l])

doit afficher

[ 11, 12, 13 ]

Des tests unitaires sont disponibles ici

Exercice 2 : collisions

La solution naïve ci-dessus ne prend pas en compte la notion de collision. Une collision arrive lorsque deux clés correspondent au même indice dans le tableau.

Par exemple, si vous avez gardé la taille initiale du tableau à 10 éléments comme le code ci-dessus, observez ce qui se passe avec le code suivant :

if __name__ == "__main__":

    d = Dictionnaire()
    l = [1, 2, 3]

    for i in l:
        d[i] = i+10
        d[i+10] = 'bug'

    print([d[i] for i in l])

Modifiez les méthodes __getitem__() et __setitem()__ de sorte à pouvoir gérer les collisions. L'algorithme à mettre en place est le suivant :

  1. Calculer l'indice de la clé dans le tableau comme précédemment.
  2. Si l'emplacement est libre (pour l'insertion), ou si l'emplacement est déjà occupé avec une valeur associée à cette clé (pour l'insertion ou la consultation) il n'y a rien à faire de plus qu'avant.
  3. Si l'emplacement est déjà occupé par une autre clé, on regarde successivement les emplacements suivants et on traitera la situation différemment en cas d'insertion ou de consultation.

Le cas de l'insertion

Soit l'emplacement suivant est vide, et on peut procéder à une insertion, soit il n'est pas vide. Si c'est le cas, trois configurations sont possibles :

  1. l'emplacement est occupé par la clé recherchée, et on peut procéder à une insertion ;
  2. l'emplacement est occupé par une clé autre, mais ayant la même valeur d'index que la clé actuelle (hash % len(stockage)), et on peut continuer à examiner l'emplacement suivant et itérer le processus ;

  3. l'emplacement est occupé par une clé autre ayant une autre valeur d'index que la clé actuelle et il est nécessaire d'agrandir l'espace de stockage.

    Créez une méthode reallocation(self) -> None qui double l'espace de stockage et qui réaffecte les données initialement stockées dans le nouvel espace, puis effectuez l'insertion.

Le cas de la consultation

Soit l'emplacement suivant est vide, et on peut conclure à l'absence de la clé recherchée, soit il n'est pas vide. S'il n'est pas vide, trois cas de figure sont possibles :

  1. l'emplacement est occupé par la clé recherchée, et on peut renvoyer la valeur ;
  2. l'emplacement est occupé par une clé autre, mais ayant la même valeur d'index que la clé actuelle (hash % len(stockage)), et on peut continuer à examiner l'emplacement suivant et itérer le processus ;
  3. l'emplacement est occupé par une clé autre ayant une autre valeur d'index que la clé actuelle et on peut conclure à l'absence de la clé recherchée.

Testez votre code (des tests unitaires sont disponibles ici )

Exercice 3 : suppressions

Créez une méthode __delitem__(self, key) -> None qui efface la clé et la valeur stockée associée du dictionnaire ou lance une exception si la clé n'existe pas.

Testez votre code (des tests unitaires sont disponibles ici )

Exercice 4 : test de présence

Créez une méthode __contains__(self, key) -> bool qui répond avec True si une clé est dans le dictionnaire, et False sinon.

Testez votre code (des tests unitaires sont disponibles ici )

Exercice 5 : itérateur

Créez une méthode __iter__(self) afin que le code suivant puisse marcher :

if __name__ == "__main__":

    d = Dictionnaire()
    l = [1, 2, 3]

    for i in l:
        d[i] = i+10

    for i in d:
        print(i)

Exercice 6 : complexité

Quelle est la complexité algorithmique de l'insertion, suppression et consultation dans un dictionnaire ? Comparez votre réponse avec l'observation du TD précédent.

Validez votre implémentation avec le code ci-dessous.

# La structure persistente partagée
structure = None


def setstructure(val):
    """
    Initialise la structure persistante partagée
    :param val:
    :return:
    """
    global structure
    structure = val
    return structure


def getstructure():
    """
    Récupère la structure persistante partagée
    :return:
    """
    global structure
    return structure


def test_insertion(donnees):
    """
    Exécute l'opération `insert()` sur la structure persistente partagée
    de façon itérative sur toutes les données passées en argument
    :param donnees:
    :return:
    """
    global structure

    for i in donnees:
        structure[i] = i


def test_contains(donnees):
    """
    Exécute l'opération `contains()` sur la structure persistente partagée
    de façon itérative sur toutes les données passées en argument
    :param donnees:
    :return:
    """
    global structure

    for i in donnees:
        i in structure


def test_delete(donnees):
    """
    Exécute l'opération `delete()` sur la structure persistente partagée
    de façon itérative sur toutes les données passées en argument
    :param donnees:
    :return:
    """
    global structure

    for i in donnees:
        del structure[i]


def gen_dict_n(n: int) -> list[int]:
    """
    Génère un tableau de n valeurs aléatoires tel qu'attendu par `ProfileRunner`
    et initialise en également la structure persistante partagée à une collection
    triée avec ces mêmes valeurs.

    :param n: nombre de donées à générer
    :return: tableau des données aléatoires généré
    """
    lst = ProfileRunner.gen_intList(n)
    data = [(i, i) for i in lst]
    setstructure(Dictionnaire())
    for i in data:
        getstructure()[i[0]] = i[1]

    return lst


if __name__ == '__main__':
    tt = Dictionnaire()  
    setstructure(tt)

    pr = ProfileRunner.ProfileRunner()

    pr.addFunction(test_insertion, ProfileRunner.gen_intList)
    pr.addFunction(test_contains, gen_dict_n)
    pr.addFunction(test_delete, gen_dict_n)

    pr.runProfiler(range(1, 200_000, 5_000), correct=lambda v, n: v / n)
    pr.plotResults()

    plt.show()

Est-ce que vous observez le comportement attendu ?

Temps d'exécution Dictionnaire

Pouvez-vous expliquer les pics réguliers pour l'insertion ? À quelle fréquence arrivent-ils ? Pourquoi ?