News for hackers. Stuff that matters.
Re:What are the lesser known but cool data structures? by panic on Saturday May 22, 2010 @06:12PM (#1371161)
Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure.

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.

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.

http://en.wikipedia.org/wiki/VList

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...

Re:What are the lesser known but cool data structures? by sjf on Saturday May 22, 2010 @07:59PM (#1371315)
Hah, I never knew there was a name for it, thanks.