Effiziente Zufallszahlengenerierung mit C++ 11 <random>

Question

Ich versuche zu verstehen, wie die C++ 11 Zufallszahlengenerierungsfunktionen verwendet werden sollen. Mein Anliegen ist Leistung.

Angenommen, wir müssen eine Reihe von zufälligen Ganzzahlen zwischen 0..k, aber k ändert bei jedem Schritt. Was ist der beste Weg, um fortzufahren?

Beispiel:

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 
} 

Die Verteilungen, die die <random> Header bietet, sind sehr bequem. Aber sie sind für den Benutzer undurchsichtig, so dass ich nicht leicht vorhersagen kann, wie sie funktionieren werden. Es ist zum Beispiel nicht klar, wie viel (wenn überhaupt) Laufzeit-Overhead durch die obige Konstruktion von dist verursacht wird.

Stattdessen könnte ich so etwas wie

verwendet haben

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 
} 

, die in jeder Iteration ein neues Objekt vermeidet zu konstruieren.

Zufallszahlen werden oft in numerischen Simulationen verwendet, bei denen die Leistung wichtig ist. Was ist der beste Weg, um <random> in diesen Situationen zu verwenden?

---

Bitte antworten Sie nicht "Profil es". Profiling ist Teil einer effektiven Optimierung, aber auch ein gutes Verständnis davon, wie eine Bibliothek verwendet werden soll, und die Leistungsmerkmale dieser Bibliothek. Wenn die Antwort ist, dass es von der Standard-Bibliothek-Implementierung abhängt, oder dass der einzige Weg zu wissen ist, es zu profilieren, dann würde ich lieber nicht die Verteilungen von <random> überhaupt verwenden. Stattdessen kann ich meine eigene Implementierung verwenden, die für mich transparent ist und bei Bedarf viel einfacher zu optimieren ist.

Answer 1

Eine Sache, die Sie tun können, ist ein permanentes Verteilung Objekt haben, so dass Sie nur das param_type jedes Mal wie dieses Objekt erstellen:

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

Für die Maximierung der Leistung, vor allem berücksichtigt unterschiedliche PRNG, wie als xorshift128 +. Es wurde berichtet, mehr als doppelt so schnell wie mt19937 für 64-Bit-Zufallszahlen; siehe http://xorshift.di.unimi.it/. Und es kann mit ein paar Zeilen Code implementiert werden.

Außerdem, wenn Sie brauchen nicht „perfekt ausbalanciert“ gleichmäßige Verteilung und Ihre k ist viel geringer als 2^64 (was wahrscheinlich ist), würde ich einfach etwas schreiben vorschlagen:

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

Beachten Sie jedoch, dass ganzzahlige Division/Modulo-Operationen nicht billig sind. Auf einem Intel Haswell-Prozessor benötigen sie zum Beispiel 39-103 Prozessorzyklen für 64-Bit-Nummern, was wahrscheinlich viel länger ist als der Aufruf einer MT19937- oder Xorshift + -Maschine.