* Re: arca-vm-26
[not found] ` <Pine.LNX.3.96.990121205408.1387G-100000@laser.bogus>
1999-01-22 9:17 ` arca-vm-26 Zlatko Calusic
@ 1999-01-22 12:42 ` Nimrod Zimerman
1 sibling, 0 replies; 2+ messages in thread
From: Nimrod Zimerman @ 1999-01-22 12:42 UTC (permalink / raw)
To: Linux Kernel mailing list
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/
^ permalink raw reply [flat|nested] 2+ messages in thread