vendredi 4 mars 2022

Which C++ random number distribution to use for the Java skip list generator?

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)
  }



Aucun commentaire:

Enregistrer un commentaire