Skip Lists
James Aspnes
opposed to other balanced tree data structures with less catchy names
(red-black trees, splay trees, etc.)? I've gotten the impression that
skip lists' only real selling point is that you don't have to
understand tree rotations to implement them, but I would been
interested in hearing from people who've actually compared performance
in typical applications.
Stephen Adams
Skip lists and balanced trees are both O(log N) for
operations like add-an-element. Skip lists are easier to
code up in you favourite language if you are used to writing
linked list code.
One point of comparison that I have not seen pointed out is
that skip lists are an inherently *imperative* data
stucture, whereas trees are not. What I mean by this is
that you always add something *to* a skip list, altering its
value. If you want to keep the old value then you have to
make a copy of the entire skip list.
Trees are often implemented like this but they need not be.
They can be implemented so that adding an element results in
a new tree, leaving the old tree in tact. This is a
*functional* implementation of the data structure. The two
trees share some subtrees (most subtrees in fact), and
generating the new tree takes time O(log N) and O(log N)
extra storage for the `trail' through the tree from the root
to the inserted element (none of the old nodes are updated,
so new ones must be allocated).
The advantage of implementing trees in a functional style is
that you can then use them as first class objects without
worrying about them changing behind your back (this is
called referential transparency). A functional
implementation of trees could be used to implement, say,
sparse matrixes, with less worry than an imperative
implementation. Consider the following code:
v1 := five
v2 := add(five,one)
If five and one were integers (or matrixes) you would be
horrified if the add operation changed the value stored in
v1. Why should you be any less horrified when v1 changes in
that case that `five' is a database (say a pointer to a
tree) and one is a new thing to put in the database?
I think that the distinction between imperative and
functional when applied to algorithms and data structures is
interesting. It is much more interesting that the
distinction between functional programming languages and
imperative programming languages. You can write spagetti
fortran in any language. You can also write something
better in any language.
--
Stephen Adams Email: S.R....@ecs.soton.ac.uk
Electronics and Computer Science Tel: 0703 593649
University of Southampton Fax: 0703 593045
Southampton SO9 5NH, UK
Kent Williams
> In article <1992Mar22.0...@cs.cmu.edu> as...@cs.cmu.edu (James Aspnes) writes:
>
> > Does anybody have any practical experience with using skip lists as
> > opposed to other balanced tree data structures with less catchy names
> > (red-black trees, splay trees, etc.)? I've gotten the impression that
> > skip lists' only real selling point is that you don't have to
> > understand tree rotations to implement them, but I would been
> > interested in hearing from people who've actually compared performance
> > in typical applications.
>
I ran a small benchmark for a particular problem -- depthsorting
polygons. We've experimented with a variety of methods, and ended
with qsort'ing an array of Z values. So when I got the skiplist code,
I wrote a benchmark that tested JUST insertion cost of building a skip
list of random floats, and compared it with sorting an array of
randome floats. These were generated by calling rand with the same
seed, so they are comparisons against the same data sets.
The resulting program runs exactly the same speed for both qsort and
skiplists. But after profiling the skiplist implmentation, I found it
spends about 1/4 of it's time inside malloc; this means to me that I
could speed it up by nearly a quarter with a special purpose allocater.
>
> One point of comparison that I have not seen pointed out is
> that skip lists are an inherently *imperative* data
> stucture, whereas trees are not. What I mean by this is
> that you always add something *to* a skip list, altering its
> value. If you want to keep the old value then you have to
> make a copy of the entire skip list.
>
As presently implemented. BUT, keep in mind that they're one way
lists, so you could have more than one list pointing at common tails.
--
Kent Williams | "Do you see your cerebellum as a lightbulb or a cog? I
will...@cs.uiowa.edu | saw mine as gristle so I fed it to the dog. But it
Quote: Bevis Frond | taste so bad, that she left it in the bowl ..."
Joseph D. Reger
I have used skip lists for a physics problem (computer simulation of very large
DNA chains in electrophoresis ( J.M. Deutsch and J.D. Reger, J. Chem. Phys 95,
2065 (1991) ), relevant to some extent to the human genome project.
I used my own implementation with distributed keys, because the nature of the
problem required that. This particular modification was VERY easy to make in
the skip list code. By contrast, it was difficult (for me) to use trees
(we were trying AVL-trees).
The point I would like to make: the skip list code, once compiled, is very
small, fits into the code cache on many machines, which makes it fly.
For a physicist, having a stochastic algorithm is very natural and easy
to understand in contrast to tree balancing. In fact, I have come to the
skip list idea by thinking about the usual trick when using quick sort:
to avoid the worst case, one can always use a randomization (shuffling) in N
steps prior to sorting. It is then very natural to call upon chance to keep
the tree balanced only ON AVERAGE.
I think skip lists are a great idea. Although I figured it out myself,
all the credit goes to W. Pugh, Commun. ACM 33, 668 (1990).
====================================
Joseph
===========================================================================
Joseph D. Reger | E-mail : re...@magellan.physik.uni-mainz.de
Institut fuer Physik | E-mail : re...@vipmzk.physik.uni-mainz.de
Universitaet Mainz | Phone : +49 (0)6131 39 3642
Staudingerweg 7 | Message : +49 (0)6131 39 3680
D-6500 MAINZ | Fax : +49 (0)6131 39 2991
Germany |
===========================================================================