Partage maximal
Pour les articles homonymes, voir Partage.
L'article doit être débarrassé d'une partie de son jargon ().
Sa qualité peut être largement améliorée en utilisant un vocabulaire plus directement compréhensible. Discutez des points à améliorer en page de discussion.
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
Articles détaillés : partage (programmation informatique) et hachage.
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
Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.
- (en) Allen, John, Anatomy of Lisp, McGraw Hill,
- (en) Ershov, A.P., « On programming of arithmetic operations », Communications of the ACM, vol. 1, no 8, , p. 3–6
- Jean-Christophe Filliâtre et Sylvain Conchon, « Type-Safe Modular Hash-Consing », SIGPLAN Workshop on ML, Portland,Oregon, ACM, .
- Eiichi Goto, Monocopy and associative algorithms in extended Lisp, University of Tokyo Technical Report TR 74-03, .
.
Portail de l’informatique
