Hash consing (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | In computer science, particularly in functional programming, hash consing is a technique used to share values that are structurally equal. The term hash consing originates from implementations of Lisp that attempt to reuse cons cells that have been constructed before, avoiding the penalty of memory allocation. Hash consing is most commonly implemented with hash tables storing weak references that may be garbage-collected when the data stored therein contains no references from outside the table. Hash consing has been shown to give dramatic performance improvements—both space and time—for symbolic and dynamic programming algorithms. An interesting property of hash consing is that two structures can be tested for equality in constant time, which in turn can improve efficiency of divide and conquer algorithms when data sets contain overlapping blocks. (en) 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. (fr) |
| dbo:wikiPageID | 21898171 (xsd:integer) |
| dbo:wikiPageLength | 4333 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102289576 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scheme_(programming_language) dbr:Memoization dbr:Merkle_tree dbr:Interning_(computer_science) dbr:Memory_allocation dbr:Cons dbr:Lisp_(programming_language) dbr:Communications_of_the_ACM dbr:Computer_science dbr:Functional_programming dbc:Implementation_of_functional_programming_languages dbr:Garbage_collection_(computer_science) dbr:Hashlife dbr:Dynamic_programming dbr:Flyweight_pattern dbr:Reference_(computer_science) dbc:Hashing dbr:Hash_table dbc:Articles_with_example_Scheme_(programming_language)_code dbr:Symbolic_computation dbr:Divide_and_conquer_algorithms dbr:Weak_reference dbr:String_interning |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_journal dbt:Comp-sci-stub dbt:Reflist |
| dcterms:subject | dbc:Implementation_of_functional_programming_languages dbc:Hashing dbc:Articles_with_example_Scheme_(programming_language)_code |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:WikicatSoftwareDesignPatterns yago:Abstraction100002137 yago:Cognition100023271 yago:Form105930736 yago:PsychologicalFeature100023100 yago:Structure105726345 |
| rdfs:comment | 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. (fr) In computer science, particularly in functional programming, hash consing is a technique used to share values that are structurally equal. The term hash consing originates from implementations of Lisp that attempt to reuse cons cells that have been constructed before, avoiding the penalty of memory allocation. Hash consing is most commonly implemented with hash tables storing weak references that may be garbage-collected when the data stored therein contains no references from outside the table. Hash consing has been shown to give dramatic performance improvements—both space and time—for symbolic and dynamic programming algorithms. An interesting property of hash consing is that two structures can be tested for equality in constant time, which in turn can improve efficiency of divide and c (en) |
| rdfs:label | Partage maximal (fr) Hash consing (en) |
| owl:sameAs | freebase:Hash consing yago-res:Hash consing wikidata:Hash consing dbpedia-fr:Hash consing dbpedia-hu:Hash consing https://global.dbpedia.org/id/36hoz |
| prov:wasDerivedFrom | wikipedia-en:Hash_consing?oldid=1102289576&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Hash_consing |
| is dbo:wikiPageRedirects of | dbr:Hash_cons dbr:Hashcons |
| is dbo:wikiPageWikiLink of | dbr:E-graph dbr:Interning_(computer_science) dbr:Eiichi_Goto dbr:Cons dbr:Hashlife dbr:Flyweight_pattern dbr:Purely_functional_data_structure dbr:Sharing dbr:Hash_cons dbr:Hashcons |
| is foaf:primaryTopic of | wikipedia-en:Hash_consing |