views:

674

answers:

5

I'm wondering whether anyone here has ever used a skip list. It looks to have roughly the same advantages as a balanced binary tree, but is simpler to implement. If you have, did you write your own, or use a pre-written library (and if so, what was its name)?

+2  A: 

I implemented a variant that I termed a Reverse Skip List for a rules engine a few years ago. Much the same, but the reference links run backwards from the last element.

This is because it was faster for inserting sorted items that were most likely to towards the back-end of the collection.

It was written in C# and took a few iterations to get working successfully.

Steve Morgan
Couldn't you invert the comparison for the type, and use a standard skiplist to achieve the same result?
oɔɯǝɹ
+5  A: 

Actually, for one of my projects I am implementing my own full STL. And I used a skiplist to implement my std::map. The reason I went with it is because it is a simple algorithm which is very close to the performance of a balanced tree but has much simpler iteration capabilities.

Also, QT4's QMap is a skiplist as well which was the original inspiration for my using it in my std::map.

Evan Teran
Evan, have you made your skiplist code available anywhere? Thanks
not quite yet, but things are almost to the point where i may release my STL. But there is plenty of example skip list implementations out there.
Evan Teran
Yes, there is plenty of skip list code available. I was looking for something that specifically complies with std::map<> interface. QMap looks quite close, so I'll give that a try. Thank-you
+2  A: 

Years ago I implemented my own for a probabilistic algorithms class. I'm not aware of any library implementations, but it's been a long time. It is pretty simple to implement. As I recall they had some really nice properties for large data sets and avoided some of the problems of rebalancing. I think the implementation is also simpler than binary tries in general. There is a nice discussion and some sample c++ code here:

http://www.ddj.us/cpp/184403579?pgno=1

There's also an applet with a running demonstration. Cute 90's Java shininess here:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

Todd
I'm accepting this one because of the DDJ article it references. Apologies to Even and Steve, I'd accept all three answers if I could.
Head Geek
+4  A: 

Java 1.6 (Java SE 6) introduced ConcurrentSkipListSet and ConcurrentSkipListMap to the collections framework. So, I'd speculate that someone out there is really using them.

Skiplists tend to offer far less contention for locks in a multithreaded situation, and (probabilistically) have performance characteristics similar to trees.

See the original paper [pdf] by William Pugh

mmagin
+3  A: 

My understanding is that they're not so much a useful alternative to binary trees (e.g. red-black trees) as they are to B-trees for database use, so that you can keep the # of levels down to a feasible minimum and deal w/ base-K logs rather than base-2 logs for performance characteristics. The algorithms for probabilistic skip-lists are (IMHO) easier to get right than the corresponding B-tree algorithms. Plus there's some literature on lock-free skip lists. I looked at using them a few months ago but then abandoned the effort on discovering the HDF5 library.

literature on the subject:

Papers by Bill Pugh:

non-academic papers/tutorials:

Jason S