The Java ConcurrentSkipListMap
class contains a method randomLevel
that outputs the following, according to The Art of Multiprocessor Programming:
The
randomLevel()
method is designed based on empirical measurements to maintain the skiplist property. For example, in thejava.util.concurrent
package, for a maximal SkipList level of 31,randomLevel()
returns 0 with probability 3/4, i with probability 2^(−(i+2)) for i ∈ [1, 30], and 31 with probability 2^−32.
This looks like a geometric distribution, but not quite. Is there some way to neatly define this in terms of the provided random distributions, or do I have to do my own manipulation, as such:
inline unsigned randomLevel() {
auto randNum = distribution.operator()(engine); // distribution is std::uniform_int_distribution<>
unsigned two__30{0x4000'0000};
if (randNum == 0)
return 31; // p(level == 31) = 2**-31
else if (randNum >= two__30)
return 0; // p(level = 0) = 0.75
else
return 30 - static_cast<unsigned>(log2(randNum)); // p(level = i) = 2**-(i+2)
}
Aucun commentaire:
Enregistrer un commentaire