Re:What are the lesser known but cool data structures?
by jules on Saturday May 22, 2010 @08:21PM
(#1371355)
An 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.
Re:What are the lesser known but cool data structures?
by pjscott on Saturday May 22, 2010 @10:22PM
(#1371584)
At one point, Python tried to move to something similar for their standard list data structure:
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.
Re:What are the lesser known but cool data structures?
by _delirium on Saturday May 22, 2010 @11:11PM
(#1371667)
Some lisp and scheme implementations have used it as well, partly spurred by this 1994 paper: http://portal.acm.org/citation.cfm?id=182453
(I don't know offhand if any widely used ones currently do, though.)
Re:What are the lesser known but cool data structures?
by Retric on Saturday May 22, 2010 @09:38PM
(#1371507)
Yep, unrolled liked lists often work great for sparse 2D data structures especially when you get a lot of clustering around small areas. (think spreadsheets)
Re:What are the lesser known but cool data structures?
by jacquesm on Saturday May 22, 2010 @11:32PM
(#1371703)
Isn't that how clojure works?
Re:What are the lesser known but cool data structures?
by lmkg on Sunday May 23, 2010 @01:02PM
(#1372572)
IIRC, 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.
Re:What are the lesser known but cool data structures?
by jacquesm on Sunday May 23, 2010 @03:40PM
(#1372829)
I found a link to the implementation details, you are correct:
http://blog.higher-order.net/2009/02/01/understanding-clojur...
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.