Каков наилучший способ генерации случайных bools?

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

я считаю, что лучший способ это использование расчетном случайного массива:

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 [размер]:

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

Конечно, вы можете инициализировать предварительно вычисленный массив с использованием другой случайной функции.

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

Answer 4

если производительность важна, возможно, это хорошая идея, чтобы сгенерировать 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-й вызов

Answer 5

Я бы с предварительным заполнением (достаточно долго) (круговой) буфером 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; 
    } 
} 

Конечно, класс может быть сделан общим для размера буфера, случайного генератора, базового типа (необязательно должен быть 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; 
    } 
}; 

Answer 6

Некоторые быстрые тесты (code):

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 по вышеуказанной ссылке. На моей машине это примерно так же быстро, как и решение @RussorRogatch, но последовательно на 10-20% быстрее, когда число циклов велико (≳100,000) и до ~ 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 7

Если у вас есть дополнительные ограничения на хаотичности вам нужно, самый быстрый способ генерации случайного BOOL является:

bool RandomBool() { return false; } 

Чтобы быть более конкретным, есть тысячи способов генерации случайных логических чисел , все из которых удовлетворяют различным ограничениям, и многие из них не дают «по-настоящему» случайных чисел (включая все остальные ответы до сих пор). Слово «случайный» само по себе никому не говорит о том, какие свойства вам действительно нужны.

Answer 8

Если производительность ваш единственный критерий, то answer является:

bool get_random() 
{ 
    return true; // chosen by fair coin flip. 
       // guaranteed to be random. 
} 

К сожалению, энтропия этого случайного числа равна нулю, но производительность довольно быстро.

Поскольку я подозреваю, что этот генератор случайных чисел не очень полезен для вас, вам необходимо определить , насколько случайным вы хотите, чтобы ваши булевы были. Как насчет длины цикла 2048? Один миллион? 2^19937-1? До конца Вселенной?

Я подозреваю, что, поскольку вы прямо заявили, что производительность является вашей главной заботой, тогда хороший старомодный линейный конгруэнтный генератор может быть «достаточно хорошим». Основываясь на this article, я предполагаю, что период этого генератора составляет около 32 * ((2^31) -5) или около 68 триллионов итераций. Если это не «достаточно хорошо», вы можете добавить любой генератор, совместимый с C++ 11, который вам нравится вместо minstd_rand.

Для дополнительного кредита и небольшого удара производительности, используйте приведенный ниже код, чтобы использовать biased coin 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; 
    } 
} 

Answer 9

Видимо, я должен добавить еще один ответ. Просто выяснилось, что начиная с Ivy Bridge архитектуры Intel добавлено RdRand Инструкции по процессору и AMD добавлены позднее в июне 2015 года. Поэтому, если вы нацеливаете процессор, который является достаточно новым и не против использования (встроенной) сборки, самый быстрый способ генерации случайных bool s должен вызывать RdRand инструкцию CPU для получения 64-разрядного случайного числа, как описано here (прокрутите примерно до середины страницы для примеров кода) (на этой ссылке есть также пример кода для проверки текущего процессора для поддержки инструкции RdRand, а также см. также Википедию для объяснения, как это сделать с инструкцией CPUID), а затем используйте биты этого числа для булевых, как описано в моем Xorshit+ based answer.