Partage maximal

En programmation informatique, le partage maximal, ou hash consing, est une technique utilisée pour économiser de la mémoire et du temps de calcul. Dans un programme qui manipule des structures de données que l'on ne cherche pas à déconstruire, mais seulement à comparer entre elles, la partage maximal fonctionne ainsi : lorsqu'une structure de données est créée, on vérifie si une structure de donnée identique se trouve déjà en mémoire. Si c'est le cas, on réutilise cette même structure au lieu d'en créer une nouvelle. D'autre part, on associe à chaque structure un nombre unique (hachage) qui permet de ramener la comparaison des deux structures à la comparaison de deux nombres, ce qui est beaucoup plus économique que la comparaison récursive de deux structures.

Explications détaillées

Cela nécessite que la structure de donnée ne puisse pas être modifiée ; on parle alors de structure de données immutable.

Le hash consing[1] attache à chaque structure une valeur de hachage qui est un nombre associé de façon unique. Si deux structures sont égales, elles auront la même valeur de hachage. Pour tester l'égalité, il suffira donc de comparer deux nombres.

En pratique, pour utiliser le hash consing, on crée une valeur puis on recherche une valeur égale dans une table de hachage. Si la valeur existe dans la table, c'est que la structure a déjà été créée et on utilise cette valeur. Si on ne la trouve pas, alors on ajoute la valeur à la table de hachage.

On peut aussi gagner du temps de calcul avec le hash consing en utilisant les valeurs de hachage pour mémoïser.

Notes et références

L'expression hash consing vient de son utilisation originelle par les concepteurs du langage Lisp pour leur besoin. Or en Lisp, cons est le constructeur des arbres binaires du langage et c'est au moment de la mise en œuvre de l'opération cons que le hachage était fait.

Annexes

Bibliographie

(en) Allen, John, Anatomy of Lisp, McGraw Hill, 1978
(en) Ershov, A.P., « On programming of arithmetic operations », Communications of the ACM, vol. 1, n^o 8,‎ 1958, p. 3–6
Jean-Christophe Filliâtre et Sylvain Conchon, « Type-Safe Modular Hash-Consing », SIGPLAN Workshop on ML, Portland,Oregon, ACM,‎ septembre 2006.
Eiichi Goto, Monocopy and associative algorithms in extended Lisp, University of Tokyo Technical Report TR 74-03, 1974. .

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.