Re: [boost] Re: Skip List

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