From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-11-06 07:19:46
At 06:13 AM 11/6/2001, Erdei Andras wrote:
>Michael 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.
--Beman