Re: arca-vm-26

[Nimrod Zimerman <zimerman@deskmail.com>]

On Thu, Jan 21, 1999 at 08:56:12PM +0100, Andrea Arcangeli wrote:

> > I do not wish to start a religious war about data structures.  Have you considered
> > the relatively new data structure called a 'skip list'?  I have replaced several
> 
> Never heard about them.

Pretty nice beasts. When I learned about them, I didn't quite consider them
a better alternative to various trees, but I guess smarter people (smarter
people with more time) have studied them extensively enough to show that
they are indeed a better choice at times.

The implementation is indeed simple. Far simpler than any self-balancing
tree (tough one has to admit that writing a B+ tree implementation is an
endless source of fun). Analyzing the complexity, at least in the variant
I've learned, isn't all that straight forward, as the algorithm is
probabilistic.

Anyway, a reference 'on the web' is http://wannabe.guru.org/alg/node35.html
(it is a very extensive reference of various algorithms. A must keep in your
bookmark file if your bank account doesn't look all that good...). I just
saw that it has a reference to the original paper presenting the data
structure, and this might make an interesting reading.

                                                   Nimrod

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/