Difference list (original) (raw)
Der Begriff Difference List (Unterschiedsliste) kann sich auf zwei verschiedene Datenstrukturen in der Informatik beziehen. Zum einen bezeichnet es eine Datenstruktur, die zwei Listen enthält und den Unterschied zwischen diesen repräsentiert. Die zweite Datenstruktur ist eine funktionale Repräsentation einer Liste, die effiziente Konkatenation ermöglicht. In diesem Fall wird eine Unterschiedsliste als einargumentige Funktion implementiert, die eine Liste als Argument nimmt und an vorne an diese anfügt. Daher wird Konkatenation von Unterschiedslisten des zweiten Typs als Funktionskomposition implementiert, welche eine konstante Laufzeit aufweist.
| Property | Value |
|---|---|
| dbo:abstract | Der Begriff Difference List (Unterschiedsliste) kann sich auf zwei verschiedene Datenstrukturen in der Informatik beziehen. Zum einen bezeichnet es eine Datenstruktur, die zwei Listen enthält und den Unterschied zwischen diesen repräsentiert. Die zweite Datenstruktur ist eine funktionale Repräsentation einer Liste, die effiziente Konkatenation ermöglicht. In diesem Fall wird eine Unterschiedsliste als einargumentige Funktion implementiert, die eine Liste als Argument nimmt und an vorne an diese anfügt. Daher wird Konkatenation von Unterschiedslisten des zweiten Typs als Funktionskomposition implementiert, welche eine konstante Laufzeit aufweist. (de) In computer science, the term difference list refers to a data structure representing a list with an efficient O(1) concatenation operation and conversion to a linked list in time proportional to its length. Difference lists can be implemented using first-class functions or using unification. Whether a difference list is more efficient than another list representations depends on usage patterns. If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, then use of difference lists can improve performance by effectively "flattening" the list building computations. (en) |
| dbo:wikiPageExternalLink | http://hackage.haskell.org/package/dlist |
| dbo:wikiPageID | 11436072 (xsd:integer) |
| dbo:wikiPageLength | 2604 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121408080 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prolog dbr:Concatenation dbr:Function_composition dbr:Computer_science dbr:Functional_programming dbr:Transformation_monoid dbr:Data_structure dbr:Linked_list dbr:List_(information) dbr:Logic_programming dbr:Haskell_(programming_language) dbc:Linked_lists dbr:Constant_time dbr:List_(computing) dbr:Argument_(programming) dbr:Function_(programming) |
| dbp:wikiPageUsesTemplate | dbt:Datastructure-stub dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Linked_lists |
| rdfs:comment | Der Begriff Difference List (Unterschiedsliste) kann sich auf zwei verschiedene Datenstrukturen in der Informatik beziehen. Zum einen bezeichnet es eine Datenstruktur, die zwei Listen enthält und den Unterschied zwischen diesen repräsentiert. Die zweite Datenstruktur ist eine funktionale Repräsentation einer Liste, die effiziente Konkatenation ermöglicht. In diesem Fall wird eine Unterschiedsliste als einargumentige Funktion implementiert, die eine Liste als Argument nimmt und an vorne an diese anfügt. Daher wird Konkatenation von Unterschiedslisten des zweiten Typs als Funktionskomposition implementiert, welche eine konstante Laufzeit aufweist. (de) In computer science, the term difference list refers to a data structure representing a list with an efficient O(1) concatenation operation and conversion to a linked list in time proportional to its length. Difference lists can be implemented using first-class functions or using unification. Whether a difference list is more efficient than another list representations depends on usage patterns. If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, then use of difference lists can improve performance by effectively "flattening" the list building computations. (en) |
| rdfs:label | Difference List (de) Difference list (en) |
| owl:sameAs | freebase:Difference list wikidata:Difference list dbpedia-de:Difference list https://global.dbpedia.org/id/GkQr |
| prov:wasDerivedFrom | wikipedia-en:Difference_list?oldid=1121408080&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Difference_list |
| is dbo:wikiPageRedirects of | dbr:Difference_lists |
| is dbo:wikiPageWikiLink of | dbr:List_of_data_structures dbr:Definite_clause_grammar dbr:D-list dbr:List_(information) dbr:Transformation_semigroup dbr:Difference_lists |
| is foaf:primaryTopic of | wikipedia-en:Difference_list |