什么是性能明智的产生随机布尔最好的方法？
我需要在性能关键path上生成随机布尔值。
我为此编写的代码是
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> 。
在网上我发现了一些更多的解决scheme
1. std::bernoulli_distribution
2. bool randbool = rand() & 1; 记得在开始时调用srand() 。
为了性能的目的，在比“ 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); } }
一些快速的基准（ 代码 ）：
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的解决scheme差不多，但是当循环数很高（≈100,000）时，速度一般要快10-20％，而在循环次数较less时速度要慢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; };
一种方法是仅仅为每64个随机调用生成一个unsigned long long整数，如注释中所述。 一个例子：
#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; };
我会预先填充（足够长）64位随机值的（循环）缓冲区，然后在需要布尔随机值的时候快速取一个位
#include <stdint.h> class BoolGenerator { private: const int BUFFER_SIZE = 65536; uint64_t randomBuffer[BUFFER_SIZE]; uint64_t mask; int counter; void advanceCounter { counter++; if (counter == BUFFER_SIZE) { counter = 0; } } public: BoolGenerator() { //HERE FILL YOUR BUFFER WITH A RANDOM GENERATOR mask = 1; counter = 0; } bool generate() { mask <<= 1; if (!mask) { //After 64 shifts the mask becomes zero mask = 1;//reset mask advanceCounter();//get the next value in the buffer } return randomBuffer[counter] & mask; } }
当然，这个类可以做成通用的缓冲区大小，随机生成器，基types（不一定是uint64_t）等。
每64次调用只访问一次缓冲区：
#include <stdint.h> //...and much more class BoolGenerator { private: static const int BUFFER_SIZE = 65536; uint64_t randomBuffer[BUFFER_SIZE]; uint64_t currValue; int bufferCounter; int bitCounter; void advanceBufferCounter() { bufferCounter++; if (bufferCounter == BUFFER_SIZE) { bufferCounter = 0; } } void getNextValue() { currValue = randomBuffer[bufferCounter]; bitCounter = sizeof(uint64_t) * 8; advanceBufferCounter(); } //HERE FILL YOUR BUFFER WITH A RANDOM GENERATOR void initializeBuffer() { //Anything will do, taken from here: http://stackoverflow.com/a/19728404/2436175 std::random_device rd; std::mt19937 rng(rd()); std::uniform_int_distribution<uint64_t> uni(0,std::numeric_limits<uint64_t>::max()); for (int i = 0; i < BUFFER_SIZE; i++ ) { randomBuffer[i] = uni(rng); } } public: BoolGenerator() { initializeBuffer(); bufferCounter = 0; getNextValue(); } bool generate() { if (!bitCounter) { getNextValue(); } //A variation of other methods seen around bitCounter--; bool retVal = currValue & 0x01; currValue >>= 1; return retVal; } };
除非你需要进一步限制随机性，否则生成随机布尔的最快方法是：
bool RandomBool() { return false; }
更具体的说，有数以千计的方法来生成随机布尔数字，所有这些都满足不同的约束条件，其中许多方法不提供“真正的”随机数（包括迄今为止所有其他答案）。 单词“随机”本身并没有告诉任何人你真正需要的属性。
如果性能很重要，那么生成一个32位的随机数并使用它的每一个单独的位是个好主意，例如：
bool getRandBool() { static uint32_t randomnumber; static int i=0; if (i==0) { randomnumber = <whatever your favorite randonnumbergenerator is>; i=32; } return (randomnumber & 1<<--i); }
这种方式只影响每32次电话
我认为最好的方法是使用预先计算的随机数组：
uint8_t g_rand[UINT16_MAX]; bool InitRand() { for (size_t i = 0, n = UINT16_MAX; i < n; ++i) g_rand[i] = ::rand() & 1; return true; } bool g_inited = InitRand(); inline const uint8_t * Rand() { return g_rand + (::rand()&INT16_MAX); }
它用来填充一些数组dst [size]：
const size_t size = 10000; bool dst[size]; for (size_t i = 0; i < size; i += INT16_MAX) memcpy(dst + i, Rand(), std::min<size_t>(INT16_MAX, size - col));
当然，您可以使用另一个随机函数初始化预先计算的数组。
如果performance是你唯一的标准，那么答案是：
bool get_random() { return true; // chosen by fair coin flip. // guaranteed to be random. }
不幸的是，这个随机数的熵是零，但是性能相当快。
因为我怀疑这个随机数发生器对你不是很有用，所以你需要量化你想要的布尔值是多么的随意 。 2048的周期长度如何？ 一百万？ 2 ^ 19937-1？ 直到宇宙结束？
我怀疑，既然你明确地表示，性能是你最关心的，那么一个好的老式线性同余发生器可能是“足够好”的。 根据这篇文章 ，我猜测这个发生器的周期大约是32 *（（2 ^ 31）-5），或者大约68万亿次迭代。 如果这不够“好”，那么可以放入任何你喜欢的C ++ 11兼容的生成器而不是minstd_rand。
为了获得额外的信用和小的性能，请修改下面的代码，以使用偏置硬币algorithm来消除发生器中的偏差。
#include <iostream> #include <random> bool get_random() { typedef std::minstd_rand generator_type; typedef generator_type::result_type result_type; static generator_type generator; static unsigned int bits_remaining = 0; static result_type random_bits; if ( bits_remaining == 0 ) { random_bits = generator(); bits_remaining = sizeof( result_type ) * CHAR_BIT - 1; } return ( ( random_bits & ( 1 << bits_remaining-- ) ) != 0 ); } int main() { for ( unsigned int i = 0; i < 1000; i++ ) { std::cout << " Choice " << i << ": "; if ( get_random() ) std::cout << "true"; else std::cout << "false"; std::cout << std::endl; } }
显然我必须添加另一个答案。 刚刚发现，从Ivy Bridge架构开始，Intel增加了RdRand CPU指令，而AMD在2015年6月晚些时候添加了它。所以，如果您的目标是足够新的处理器并且不介意使用（内联）汇编，最快的方法随机bool应该在调用RdRand CPU指令来获得一个64位的随机数，如这里所描述的（滚动到大约页面中间的代码示例）（在这个链接还有一个代码示例，用于检查当前的CPU支持RdRand指令，另请参阅维基百科，了解如何使用CPUID指令进行此操作），然后使用该数字的位作为基于Xorshit +的答案中所述的布尔值。
