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 the java.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)
  }

CodePudding user response：

This looks like a geometric distribution, but not quite.

You are right, but problem is only probability of 0. Note that you can use std::geometric_distribution, by merging first two values into one.

class RandomLevel
{
    std::geometric_distribution<unsigned> distribution;
    std::mt19937 gen{std::random_device{}()};
public:
    unsigned operator()() {
        auto result = distribution(gen);
        return result > 1u : result - 1u : 0u;
    }
}