Bonjour,
J’ai bien aimé cette documentation, c’est pourquoi j’ai voulu aller plus loin en m’amusant à programmer un dictionnaire s’appuyant sur les notions présentées. En me contentant de ne gérer que des entrées au format alphabétiques (non vides, et en faisant l’impasse sur les objets complexes, tables de structures et autres).
J’ai vite été confronté à deux problèmes :
- Comment « hacher » rapidement la clé pour obtenir un entier (compris entre 1 et N) qui donne la position où l’enregistrer dans le dictionnaire.
- Comment gérer les collisions lorsque plusieurs clés donnent la même position.
Pour le hachage, j’ai utilisé dans un premier temps l’algorithme MD5. Mais sa lenteur d’exécution m’a poussé à chercher une autre piste, et j’ai trouvé l’algorithme de hachage XxHash : «
C'est un algorithme de hachage non cryptographique extrêmement populaire, célèbre pour sa vitesse d'exécution exceptionnelle, jusqu’à 20 fois plus rapide que MD5 ». l’IA m’a bien aidé à le convertir en une version 32 bits optimisée et compatible avec le VBA.
Pour la gestion des collisions, j’ai pensé à une mémoire annexe « Mx », qui contient dans une liste chaînée les clés qui ont la même valeur de hachage. L’indexation permet de passer en revue les données sans avoir à lire la liste en intégralité, d’où un gain de temps. Arbitrairement cette liste annexe est 50% de la taille du dictionnaire. Quand la liste est pleine on double la taille du dictionnaire, et donc de l’annexe, et l’on reconstruit le dictionnaire avec les données existantes, avant d’accueillir les nouvelles.
La mémoire « M » du dictionnaire a trois attributs :
- Clé : la chaine alphabétique qui représente la clé du dictionnaire (par exemple un mot).
- Valeur : la valeur du dictionnaire (par exemple sa définition).
- Index : l’indexation dans la mémoire annexe, soit 0 s’il n’y a pas d’autre clé identique dans la mémoire annexe, soit « j » qui représente l’entrée dans la mémoire annexe.
En résumé :
Chaque clé est hachée. On obtient un entier « i ».
Si M(i).Clé est vide, c’est que la position est libre : on enregistre dans M(i).Clé la clé, dans M(i).Valeur la valeur, et M(i).Index = 0.
Sinon, on va alimenter la mémoire annexe (« Mx » a les mêmes attributs que « M »). C’est le principe d’une liste chainée, je ne vais pas m’y étendre, mais en gros :
M(i).Index = j (à savoir que « j » est incrémenté de 1 à chaque fois), et Mx(j).Clé = la clé, Mx(j).Valeur = la valeur, Mx(j).Index = 0.
Sauf que, si M(i).Index est différent de 0, c’est que l’annexe est déjà occupée, on parcours donc les clés dans Mx() en commençant par j = M(i).Index. Chaque fois Mx(j).Index donne la position suivante dans la liste chainées. Quand Mx(j).Index = 0 alors il n’y a plus de suite. On enregistre dans Mx(j).Index = k+1, ou k est la dernière position de l’annexe. Et dans Mx(k+1) les données.
Je ne vais pas vous embêter avec le code source en VBA, mais je le tiens à votre disposition si cela vous intéresse.
J’ai remarqué que mon dictionnaire est bien plus rapide que la fonction native du VBA qui appelle un objet COM (ActiveX). Explication : «
En VBA, chaque appel à ses méthodes (.Add, .Exists) subit une surcharge liée à l'interface COM (COM overhead), ce qui ralentit considérablement les boucles massives. »
Je ne sais pas si c’est le cas avec Python ou dans vos langages de programmation.
En tout cas, je remercie Denis Hulo pour cette excellente documentation qui m’a permis de découvrir un domaine que j’ignorais.
Bonne programmation à vous.
1 |
0 |
Bonjour à tous,