Skip List in #4308

Daniel Joyce daniel.a.joyce at att.net
Tue Oct 2 15:37:45 UTC 2001


>
> Skip lists use variable sized nodes (1-32 references), in most
> implementations, the expected number of references per node is two. Making
> them the same expected overhead as splay trees or doubly-linked lists.
> Given squeak header overhead, this means an expected 5 longwords/node (2
> header, 2 for navigation, one for the data).
>
> Given their extra size and complexity, they're probably not worth it
> unless you've got at least 20 nodes and a pretty high update rate.
>
> Though, may I suggest refactoring skiplists so that they subclass
> OrderedCollection, and implement the same interface as SortedCollection so
> that they are a drop-in replacement.
>
> SortedCollection is the right choice for what you're doing. Its not your
> fault that the implementation is not perfect. IE, don't fix your code, fix
> SortedCollection by making an alternate O(log n) implementation.
>
> Scott

	Or, perhaps, change sorted collection so it uses Skip Lists, etc, as backing 
stores when certain conditions are met ( Usually size of data stored ). With 
a little code profiling, one could tune it to change it's backing data rep at 
the appropiate times as the data stored grows.

	This is done in some Smalltalks.

	I've been reading too much on Smalltalk best practices, and refactoring...

	Daniel Joyce




More information about the Squeak-dev mailing list