arca-vm-26
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 3 lines · Andrea Arcangeli
Sure, I _am_ interested. Please give me pointers (on the web, I don't have money for books ;).
I found something at http://www.csihq.com/CSI/pubs/skiplist.html but never had time to investigate it.
Enjoy!
Signature · 6 lines
Zlatko - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] Please read the FAQ at http://www.tux.org/lkml/
Quoted 4 lines · Andrea Arcangeli
Quoted 2 lines
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 [email protected]
Please read the FAQ at http://www.tux.org/lkml/