On Tue, 25 Sep 2001, Andreas Raab wrote:

> Folks,
>
> I noticed them coming into Squeak a while ago and always since I wanted to
> ask this question: What the heck are they good for?! ;-) I don't see them

Skiplists are an implementation of the sorted-list pattern, in that they
are paramaterized by some sort of ordering relation, and support the
following operations. Basically, this is the SortedCollection pattern:


Create()
Insert(item)
Delete(item)
Next(item)
Prev(item)
First()
Last()
Lookup(Item)  ;; return the item in the list that is equal (by the
              ;; ordering relation) with the requested item.

Items can be thought of as being key-value pairs, where the ordering
relation in the items is the ordering relation on the keys in those items.

The typical implementation of these uses balanced binary trees (splay
trees, red black trees, AVL trees, treaps, etc). That way you get O(log n)
for all operations except O(1) to create.

Skiplists are a different way of doing this; they are simpler than trees
and have tighter inner loops.

BTW, squeak currently uses arrays to implement SortedCollection, thus
Insert and Delete cost O(n) instead of O(log n). I was thinking of
reimplementing SortedCollection myself if profiling indicated that this
was a problem.

As an interesting aside, assuming that you have no other intervening
accesses or mutations to the splay tree, you can do enumerate
through all of the elements of a splay tree from start to
finish in O(1) amortized time, even though the individual operations are
O(log n) time.


> used anywhere and I've never heard of 'em before (yeah, well, my
> introductory courses in algorithms and data structures were plenty of years
> back ;-) but somebody found them important enough to write and include them.
> Since I like data structures (in particular efficient ones) I'd like to hear
> more about the places in which SkipLists could and should be used instead of
> other approaches. Pointers to comparisons would be nice, examples in Squeak
> even nicer ;-)

Basically, Skiplists (and/or balanced tree implementations of
SortedCollection) should be used anywhere where you have a lot of
inserts/removals from a sorted collection, and profiling shows that that
is a problem.

Now, if you integrated them so that they supported the same sort of
operations as SortedCollection, I'd really thank you. (I'm not at the
point where I am dealing with large collections of sorted data for the
difference to be noticable in the profiling results. As such, I've not
bothered with examining the code closely, but I think that they should be
resuperclassed to inherit from OrderedCollection, not Collection.)


Scott



--
No DVD movie will ever enter the public domain, nor will any CD. The last CD
and the last DVD will have moldered away decades before they leave copyright.
This is not encouraging the creation of knowledge in the public domain.