Skip Lists?!
goran.hultgren at bluefish.se
goran.hultgren at bluefish.se
Wed Sep 26 09:51:55 UTC 2001
"Andreas Raab" <Andreas.Raab at gmx.de> 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
Well, I was also implementing them for fun and there are some nice pdfs
on the net somewhere (Google ought to find them for you) explaining them
in detail - including a revised concurrent version (which the
implementation in Squeak is not I assume). Note: there might be factual
errors here - I am no expert:
Basically it is a list with overlayed pointers that you can use to "skip
ahead" in the list. These pointers are created using randomness and thus
you end up with searchproperties etc much like a balanced binary tree -
but you don't have to worry about balancing etc. and
insertions/deletions and so forth are much easier implemented. It is a
damn clever and rather "obvious" solution, but who would even think of
using randomness in a datastructure? :-)
As far as I can tell it is a very good alternative to balanced binary
trees (much easier implementation being prime advantage I believe) -
performance wise they are much the same. I read somewhere that database
implementations still might prefer Btrees because of some property that
make them more efficient when it comes to distribution on secondary
memory - but I don't know the details on that.
So... seems like a good structure to have in Squeak - even if nobody
uses it yet! :-)
regards, Göran
> 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 ;-)
>
>
> Cheers,
> - Andreas
More information about the Squeak-dev
mailing list
|