Conc-tree list (original) (raw)
A conc-tree is a data structure that stores element sequences, and provides amortized O(1) time append and prepend operations, O(log n) time insert and remove operations and O(log n) time concatenation. This data structure is particularly viable for functional task-parallel and data-parallel programming, and is relatively simple to implement compared to other data-structures with similar asymptotic complexity. Conc-trees were designed to improve efficiency of data-parallel operations that do not require sequential left-to-right iteration order, and improve constant factors in these operations by avoiding unnecessary copies of the data. Orthogonally, they are used to efficiently aggregate data in functional-style task-parallel algorithms, as an implementation of the conc-list data abstract
| Property | Value |
|---|---|
| dbo:abstract | A conc-tree is a data structure that stores element sequences, and provides amortized O(1) time append and prepend operations, O(log n) time insert and remove operations and O(log n) time concatenation. This data structure is particularly viable for functional task-parallel and data-parallel programming, and is relatively simple to implement compared to other data-structures with similar asymptotic complexity. Conc-trees were designed to improve efficiency of data-parallel operations that do not require sequential left-to-right iteration order, and improve constant factors in these operations by avoiding unnecessary copies of the data. Orthogonally, they are used to efficiently aggregate data in functional-style task-parallel algorithms, as an implementation of the conc-list data abstraction. Conc-list is a parallel programming counterpart to functional cons-lists, and was originally introduced by the Fortress language. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Screen-conc.png?width=300 |
| dbo:wikiPageID | 50562924 (xsd:integer) |
| dbo:wikiPageLength | 6742 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1081660364 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_tree dbr:Task_parallelism dbr:Cons dbr:Data_structure dbr:Fortress_(programming_language) dbc:Trees_(data_structures) dbr:Big_O_notation dbr:AVL_trees dbr:Deque dbr:File:Screen-conc.png |
| dbp:wikiPageUsesTemplate | dbt:Distinguish dbt:Reflist |
| dct:subject | dbc:Trees_(data_structures) |
| rdf:type | owl:Thing |
| rdfs:comment | A conc-tree is a data structure that stores element sequences, and provides amortized O(1) time append and prepend operations, O(log n) time insert and remove operations and O(log n) time concatenation. This data structure is particularly viable for functional task-parallel and data-parallel programming, and is relatively simple to implement compared to other data-structures with similar asymptotic complexity. Conc-trees were designed to improve efficiency of data-parallel operations that do not require sequential left-to-right iteration order, and improve constant factors in these operations by avoiding unnecessary copies of the data. Orthogonally, they are used to efficiently aggregate data in functional-style task-parallel algorithms, as an implementation of the conc-list data abstract (en) |
| rdfs:label | Conc-tree list (en) |
| owl:differentFrom | dbr:Cons |
| owl:sameAs | wikidata:Conc-tree list https://global.dbpedia.org/id/2PHo5 |
| prov:wasDerivedFrom | wikipedia-en:Conc-tree_list?oldid=1081660364&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Screen-conc.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Conc-tree_list |
| is dbo:wikiPageRedirects of | dbr:Conc-Tree_list |
| is dbo:wikiPageWikiLink of | dbr:List_of_data_structures dbr:Conc-Tree_list |
| is foaf:primaryTopic of | wikipedia-en:Conc-tree_list |
