性能方面是什么是生成随机bool的最佳方法？

Question

我需要在性能关键路径上生成随机布尔值.

我为此写的代码是

std::random_device   rd;
std::uniform_int_distribution<> randomizer(0, 1);
const int val randomizer(std::mt19937(rd()));
const bool isDirectionChanged = static_cast<bool>(val);

但是不要认为这是我不喜欢做的最好的方法static_cast<bool>.

在网络上,我找到了一些解决方案

1. std::bernoulli_distribution

2. bool randbool = rand() & 1;记得srand()在开始时打电话.

Answer 1

出于性能目的,以比" 自由 "更少的价格std::mt19937_64,您可以使用Xorshift +生成64位数字,然后将这些数字的位用作伪随机布尔值.

引用维基百科:

这个生成器是通过BigCrush的最快的生成器之一

详情:http://xorshift.di.unimi.it/.页面中间有一个比较表,显示mt19937_64速度慢2倍并且是系统的.

下面是示例代码(真正的代码应该将它包装在一个类中):

#include <cstdint>
#include <random>
using namespace std;

random_device rd;
/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2] = { (uint64_t(rd()) << 32) ^ (rd()),
    (uint64_t(rd()) << 32) ^ (rd()) };
uint64_t curRand;
uint8_t bit = 63;

uint64_t xorshift128plus(void) {
    uint64_t x = s[0];
    uint64_t const y = s[1];
    s[0] = y;
    x ^= x << 23; // a
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
    return s[1] + y;
}

bool randBool()
{
    if(bit >= 63)
    {
        curRand = xorshift128plus();
        bit = 0;
        return curRand & 1;
    }
    else
    {
        bit++;
        return curRand & (1<<bit);
    }
}

Answer 2

一些快速基准测试(代码):

   647921509 RandomizerXorshiftPlus
   821202158 BoolGenerator2 (reusing the same buffer)
  1065582517 modified Randomizer
  1130958451 BoolGenerator2 (creating a new buffer as needed)
  1140139042 xorshift128plus
  2738780431 xorshift1024star
  4629217068 std::mt19937
  6613608092 rand()
  8606805191 std::bernoulli_distribution
 11454538279 BoolGenerator
 19288820587 std::uniform_int_distribution

对于那些想要使用现成代码的人,我提供XorShift128PlusBitShifterPseudoRandomBooleanGenerator了一个RandomizerXorshiftPlus来自上述链接的调整版本.在我的机器上,它与@ SergeRogatch的解决方案一样快,但是当循环计数高(≳100,000)时一直快10-20%,而循环计数越小,速度就越慢约30%.

class XorShift128PlusBitShifterPseudoRandomBooleanGenerator {
public:
  bool randBool() {
    if (counter == 0) {
      counter = sizeof(GeneratorType::result_type) * CHAR_BIT;
      random_integer = generator();
    }
    return (random_integer >> --counter) & 1;
  }

private:
  class XorShift128Plus {
  public:
    using result_type = uint64_t;

    XorShift128Plus() {
      std::random_device rd;
      state[0] = rd();
      state[1] = rd();
    }

    result_type operator()() {
      auto x = state[0];
      auto y = state[1];
      state[0] = y;
      x ^= x << 23;
      state[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
      return state[1] + y;
    }

  private:
    result_type state[2];
  };

  using GeneratorType = XorShift128Plus;

  GeneratorType generator;
  GeneratorType::result_type random_integer;
  int counter = 0;
};

Answer 3

一种方法是只unsigned long long为评论中所述的每64个随机调用生成一个.一个例子:

#include <random>
class Randomizer
{
public:
    Randomizer() : m_rand(0), counter(0), randomizer(0, std::numeric_limits<unsigned long long>::max()) {}

    bool RandomBool()
    {
        if (!counter)
        {
            m_rand = randomizer(std::mt19937(rd()));
            counter = sizeof(unsigned long long) * 8;

        }
        return (m_rand >> --counter) & 1;
    }
private:
    std::random_device  rd;
    std::uniform_int_distribution<unsigned long long> randomizer;
    unsigned long long m_rand;
    int counter;
};