[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps

Mike Skells mike.skells@ebizz-consulting.com
Mon, 21 Jun 2004 11:29:44 +0100


> -----Original Message-----
> From: Bill Pugh [mailto:pugh@cs.umd.edu] 
> Sent: Friday 18 June 2004 17:56
> To: mike.skells@ebizz-consulting.com
> Cc: concurrency-interest@altair.cs.oswego.edu
> Subject: Re: [concurrency-interest] Skip Lists, Concurrent 
> Skip Lists and Concurrent Sorted Maps
> 
> 
> 
> On Jun 18, 2004, at 11:09 AM, Mike Skells wrote:
> >>
> >> It would also be nice to expose methods that, given a key k,
> >> return the entry with the smallest key > k, and another method that
> >> returns the entry
> >> with the largest key < k. (Methods like this exist in the current
> >> TreeMap implementation,
> >> but are private).
> >>
> >> We might also release a nonconcurrent SkipList. For example,
> >> that would
> >> allow you
> >> to perform rank queries (get me the entry at position 42).  Rank
> >
> > I don't understand this. From my understanding a rank query is
> > List.get(int)
> > which is inefficent for a skip list, as it has to scan 
> every node like 
> > a
> > linked list doesn't it,
> > As the skiplist doesn't know its position due to the random 
> nature of
> > the skipping?
> >
> 
> You can implement a skip list that can efficiently perform 
> rank queries.
> 
> See the skip list cookbook, section 3.4
> 	ftp://ftp.cs.umd.edu/pub/skipLists/cookbook.pdf
This is interesting. How much of a performance hit does it take to
maintain the fDistance on each of the links?

Assuming that there is an overhead you proposing to have this as an
option or in a subclass, or is it proposed that this will be in the base
implementation.

> 
>