7 ms·
Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure. http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.w
by panic 16y ago
Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure.
http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list
The idea is the same as a linked list, but instead of just one element in each node, it stores an entire array. This simple change fixes the two biggest problems with linked lists — memory overhead and cache efficiency. It's also easy to tweak to be more "array-like" or more "list-like" as needed.
- sjf 16y agoHah, I never knew there was a name for it, thanks.
- jules 16y agoAn interesting variation on this is the VList, which works the same way except the inner arrays have variable size. This gives you an asymptotic rather than constant speedup for many operations. http://en.wikipedia.org/wiki/VList http://en.wikipedia.org/wiki/VList
- Retric 16y agoYep, unrolled liked lists often work great for sparse 2D data structures especially when you get a lot of clustering around small areas. (think spreadsheets)
- pjscott 16y agoAt one point, Python tried to move to something similar for their standard list data structure: http://www.python.org/dev/peps/pep-3128/ http://www.python.org/dev/peps/pep-3128/ The BList is similar to a B+Tree. It was meant to act like an array for small lists, but to make operations like append, concatenation, and slicing faster. It was a pretty cool combination of arrays (for memory compactness and good cache performance and small constant factors) with trees, for the asymptotic improvements they can bring. Sadly, it didn't take off, as it would have broken backward compatibility with extension modules.
- _delirium 16y agoSome lisp and scheme implementations have used it as well, partly spurred by this 1994 paper: http://portal.acm.org/citation.cfm?id=182453 http://portal.acm.org/citation.cfm?id=182453 (I don't know offhand if any widely used ones currently do, though.)
- jacquesm 16y agoIsn't that how clojure works?
- lmkg 16y agoIIRC, clojure works with 64-ary trees, which are a different data structure, but both share the property that 'leaves' contain more than one object. An unrolled linked list node would have, say, 63 objects and a pointer to another node. A 64-ary tree node will either have 64 objects, or pointers to 64 other nodes. One important property is that because each middle node in the tree has 64 children instead of 2, the depth of the trees are very very shallow in practice. However, it's possible that clojure uses this layout for arrays and a different ones for lists or other sequences.
- jacquesm 16y agoI found a link to the implementation details, you are correct: http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ http://blog.higher-order.net/2009/02/01/understanding-clojur...