"Randal L. Schwartz" wrote:

Skip lists got snuck in with changeset 4308 with *no documentation* except the source code. Not even a class comment!

Can SqueakCentral at least set the bar high enough that *new* classes into the core will not be accepted without at least having a class comment? Please?

Especially something that is in the Collections category!

This came up just a few day ago. Someone who understand it could make a comment enhancement:-) Karl

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