Matches in DBpedia 2014 for { <http://dbpedia.org/resource/VList> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- VList abstract "In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly linked) linked lists.Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like singly linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log n) time.The primary operations of a VList are: Locate the kth element (O(1) average, O(log n) worst-case) Add an element to the front of the VList (O(1) average, with an occasional allocation) Obtain a new array beginning at the second element of an old array (O(1)) Compute the length of the list (O(log n))The primary advantage VLists have over arrays is that different updated versions of the VList automatically share structure. Because VLists are immutable, they are most useful in functional programming languages, where their efficiency allows a purely functional implementation of data structures traditionally thought to require mutable arrays, such as hash tables. However, VLists also have a number of disadvantages over their competitors: While immutability is a benefit, it is also a drawback, making it inefficient to modify elements in the middle of the array. Access near the end of the list can be as expensive as O(log n); it is only constant on average over all elements. This is still, however, much better than performing the same operation on cons-based lists. Wasted space in the first block is proportional to n. This is similar to linked lists, but there are data structures with less overhead. When used as a fully persistent data structure, the overhead may be considerably higher and this data structure may not be appropriate.↑".
- VList thumbnail VList_example_diagram.png?width=300.
- VList wikiPageExternalLink vlist.scm.
- VList wikiPageExternalLink vlist.ss.
- VList wikiPageExternalLink vlist.aspx.
- VList wikiPageExternalLink vlist.html.
- VList wikiPageID "558740".
- VList wikiPageRevisionID "569987139".
- VList hasPhotoCollection VList.
- VList subject Category:Arrays.
- VList subject Category:Linked_lists.
- VList type Abstraction100002137.
- VList type Arrangement107938773.
- VList type Array107939382.
- VList type Arrays.
- VList type Group100031264.
- VList comment "In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly linked) linked lists.Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference.".
- VList label "V-список".
- VList label "VList".
- VList label "VList".
- VList sameAs VList.
- VList sameAs m.02py3z.
- VList sameAs Q2386652.
- VList sameAs Q2386652.
- VList sameAs VList.
- VList wasDerivedFrom VList?oldid=569987139.
- VList depiction VList_example_diagram.png.
- VList isPrimaryTopicOf VList.
