Skip to contentSkip to conversation

arca-vm-26

DISCUSSION Zlatko Calusic 2 participants 2 messages Jan 22, 1999 2 messages not in the archive

lore
Share & tools
lore

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]

#2 lore raw
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/
#3 lore raw
In reply to a message not in the archive
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/