Generazione di numeri casuali efficiente con C++ 11 <random>

Question

Sto cercando di capire come devono essere utilizzate le funzionalità di generazione casuale del numero C++ 11. La mia preoccupazione è la prestazione.

Supponiamo di dover generare una serie di numeri interi casuali tra 0..k, ma k modifiche ad ogni passaggio. Qual è il modo migliore di procedere?

Esempio:

for (int i=0; i < n; ++i) { 
    int k = i; // of course this is more complicated in practice 
    std::uniform_int_distribution<> dist(0, k); 
    int random_number = dist(engine); 
    // do something with random number 
} 

Le distribuzioni che l'intestazione <random> fornisce sono molto convenienti. Ma sono opachi per l'utente, quindi non posso facilmente prevedere come si esibiranno. Ad esempio, non è chiaro quanto (eventuale) sovraccarico di runtime sia causato dalla costruzione di dist precedente.

Invece ho potuto usare qualcosa di simile

std::uniform_real_distribution<> dist(0.0, 1.0); 
for (int i=0; i < n; ++i) { 
    int k = i; // of course this is more complicated in practice 
    int random_number = std::floor((k+1)*dist(engine)); 
    // do something with random number 
} 

che evita la costruzione di un nuovo oggetto in ogni iterazione.

I numeri casuali vengono spesso utilizzati in simulazioni numeriche in cui le prestazioni sono importanti. Qual è il modo migliore per utilizzare <random> in queste situazioni?

---

Si prega di non rispondere "profilo". La profilatura è parte dell'ottimizzazione efficace, ma lo è anche una buona comprensione di come una libreria è destinata a essere utilizzata e le caratteristiche delle prestazioni di tale libreria. Se la risposta è che dipende dall'implementazione della libreria standard, o che l'unico modo per sapere è profilarlo, allora preferirei non usare affatto le distribuzioni da <random>. Invece posso usare la mia implementazione che sarà trasparente per me e molto più facile da ottimizzare se/quando necessario.

Answer 1

Una cosa che potete fare è di avere un permanente distribuzione oggetto in modo che si crea solo l'oggetto param_type ogni momento come questo:

template<typename Integral> 
Integral randint(Integral min, Integral max) 
{ 
    using param_type = 
     typename std::uniform_int_distribution<Integral>::param_type; 

    // only create these once (per thread) 
    thread_local static std::mt19937 eng {std::random_device{}()}; 
    thread_local static std::uniform_int_distribution<Integral> dist; 

    // presumably a param_type is cheaper than a uniform_int_distribution 
    return dist(eng, param_type{min, max}); 
} 

Answer 2

Per massimizzare le prestazioni, prima di tutto considerare diverse PRNG, come ad come xorshift128 +. È stato segnalato essere più di due volte più veloce di mt19937 per numeri casuali a 64 bit; vedi http://xorshift.di.unimi.it/. E può essere implementato con poche righe di codice.

Inoltre, se non hai bisogno di distribuzione divisa "perfettamente bilanciata" e il k è molto minore di 2^64 (che probabilmente è), vorrei suggerire di scrivere semplicemente qualcosa come:

uint64_t temp = engine_64(); // generates 0 <= temp < 2^64 
int random_number = temp % (k + 1); // crop temp to 0,...,k 

Si noti, tuttavia, che le operazioni su divisione/modulo intero non sono economiche. Ad esempio, su un processore Intel Haswell, richiedono 39-103 cicli del processore per i numeri a 64 bit, che è probabilmente molto più lungo rispetto a un motore MT19937 o xorshift +.