From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-11-06 07:19:46
At 06:13 AM 11/6/2001, Erdei Andras wrote:
>> I'm sorry, I've never read this and can't find it on ACM or Yahoo.
>you can find the some articles at http://www.cs.umd.edu/~pugh/
>[the homepage of the original skip list author]
>and a lot more around http://citeseer.nj.nec.com/messeguer97skip.html
>Sofus Mortensen wrote:
>> I wonder what skip list's will bring us that we don't already
>> have with either set/multiset or map/multimap ?
>customizable memory complexity, additional functionality
>(like utilizing the locality of searches), and (at least in theory)
>greater speed -- i'm toying around with my own skip list
>implementation, but so far i'm stuck speed-wise. it is supposed
>to be faster than the red-black tree set in my STL, but right
>now the debug skip list is about 10 times faster than the
>debug red-black tree, while the release (optimized) version
>is slightly faster for insert and delete, but about 10% slower for
>search... most likely i'm not too good at writing fast code :O)
My first try at a skip list implementation also had unexpected performance
problems. Tracked it down to a poor implementation of rand(). You might
want to use the Boost random number library if you aren't doing so already.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk