Messages in this thread | | | Date | Fri, 22 Jan 1999 14:42:23 +0200 | From | Nimrod Zimerman <> | Subject | Re: arca-vm-26 |
| |
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/
| |