MIT’s Introduction to Algorithms, Lecture 12: Skip Lists - good coders code, great reuse

http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-eight/

by nreece • 18 years ago

29 4 18 years ago

hassy• 18 years ago

One of our projects in the algorithms class back at uni was to implement a skiplist and assess its performance.

While skiplists are indeed simple to implement and do have log(n) average time for most operations, they're an example of theory and practice being the same in theory but not in practice.

The real-world performance of skiplists is worse than that of B-trees, especially when you have costly comparisons. They also don't maintain as much locality and will thrash the cache more.

aston• 18 years ago

Skiplists are for most CS students their first and maybe only introduction to a data structure where the theoretical math comes out beautifully (impossibly?) small, and gets beaten by some variation of the binary tree if you actually try it in real life. There are a ton more, many of which I learned about from that same lecturer. Fun to talk about and toy with, but you'll never need Y-fast Tries in your day-to-day.

tptacek• 18 years ago

From Skiena, which buy right now:

Skip lists --- These are somewhat of a cult data structure. Their primary benefits seem to be ease of implementation relative to balanced trees. If you are using a canned tree implementation, and thus not coding it yourself, this benefit is eliminated. I wouldn't bother with them.

william-newman• 18 years ago

Skip lists seem to be a powerful way of thinking about the problem, anyway. Note that they lead nicely to the very nifty multidimensional generalization, skip quadtrees, www.ics.uci.edu/~goodrich/pubs/skip.pdf .

And, FWIW, they also lead to my algorithms for hash-consing digraphs, which I put up as rough preprints and and prototype code at http://www.wryttyndyffyryntly.com/preprint/. Those algorithms are unreviewed, and I made a bad mistake in an early version, so who knows? (I sent email about them to other people who had cited the Mauborgne papers that I cited, and got no response. I don't know whether it's worth trying to bang them into shape for submission to a journal, and whether or not it's worth it in principle, in practice last year I was too tired of working on them to consider it very objectively.)

MIT’s Introduction to Algorithms, Lecture 12: Skip Lists - good coders code, great reuse

Related Stories