lkml.org 
[lkml]   [1999]   [Jan]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRandom number generator for skiplists
On the thread of Andrea's arca-26 conversation about switching from AVL
or RedBlack trees or hashes to something "better":

Here is (http://wannabe.guru.org/alg/node134.html ) a reference to what
looks like a pretty fast and pretty good random number generator that
would be useful for skiplists. This is NOT the one we use here, but it
is almost certainly superior to the one we use here. The Englishman who
is the king of skiplists here (David Clear) "can't be asked" to switch,
since our existing algorithm has been working fine for six months
already, but if you're starting from scratch it might be better to use a
better random number generator than we use. We have found that we tend
to skew slightly toward smaller height skiplist nodes, which slightly
hurts performance.

a



-
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/

\
 
 \ /
  Last update: 2005-03-22 13:49    [from the cache]
©2003-2011 Jasper Spaans