Wie rechenintensiv ist die Generierung einer Zufallszahl in C++?

Question

Die Methode, die ich überlege ist aus: https://stackoverflow.com/a/19728404/6571958

#include <random> 

std::random_device rd;  // only used once to initialise (seed) engine 
std::mt19937 rng(rd()); // random-number engine used (Mersenne-Twister in this case) 
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased 

auto random_integer = uni(rng); 

ich auch bereit bin mit srand(time(NULL)) den rand() Ansatz zu verwenden.

Meine Frage: Wie teuer sind diese Ansätze? Ist einer viel schneller als der andere?

Answer 1

Die Leistung hängt stark vom verwendeten Generator ab (was wiederum stark von der Qualität der benötigten Rufnummern abhängt).

Zum Beispiel std::mt19937 ist viel schneller als std::random_device aber produziert Pseudozufallszahlen. Dies ist für die meisten Zwecke in Ordnung, wenn Sie keine kryptographisch sicheren Zufallszahlen benötigen. Aber selbst wenn Sie das tun, kann random_device Roh-Entropie mit einer Rate von ca. 50MB/Sek. Auf meinem Rechner erzeugen - wie viel Zufälligkeit brauchen Sie wirklich? (mt19937 erzeugt bei Bedarf mehr Größenordnungen).

Vermeiden Sie rand(). Es hat nur sehr schlechte Eigenschaften und einen sehr niedrigen Zeitraum.

Siehe auch https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful

Answer 2

ich, dass die Leistung sowohl abhängig ist, auf Implementierung und Hardware schreiben könnte, aber es wäre als die richtige nutzlos. Ein Beispiel für die Leistung wäre nützlicher.

E7240 Laptop, Linux, g ++ 4.8.4, -O3 flag

#include <cstdlib> 
#include <iostream> 

int main(int argc, const char** argv) { 
    const bool bPlain = (argv[1][0] == '-'); 
    if (bPlain) 
     argv++; 
    int n = atoi(argv[1]); 
    int sum = 0; 
    if (bPlain) 
     for (int i=0; i<n; i++) 
      sum |= i; 
    else 
     for (int i=0; i<n; i++) 
      sum |= rand(); 
    // To prevent the compilier from optimizing away the loop 
    if (sum == 0) 
     std::cout << sum << std::endl; 
} 

[~/CPP] time ./randbm 1000000000 
9.049u 0.000s 0:09.05 99.8% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm 1000000000 
9.059u 0.000s 0:09.06 99.8% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm 1000000000 
9.040u 0.008s 0:09.05 99.8% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm - 1000000000 
0.192u 0.000s 0:00.20 95.0% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm - 1000000000 
0.172u 0.000s 0:00.18 94.4% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm - 1000000000 
0.185u 0.004s 0:00.20 90.0% 0+0k 0+0io 0pf+0w 

So, in diesem speziellen Fall ein Anruf an rand() dauert etwa 9 ns , während ein Schleifendurchlauf dauert etwa 0,2 Nanosekunden.

Die Verwendung von random ist langsamer. Hinzufügen #include <random> und ersetzt den entsprechenden Teil des Codes durch:

std::random_device rd;  // only used once to initialise (seed) engine 
std::mt19937 rng(rd()); // random-number engine used (Mersenne-Twister in this case) 
std::uniform_int_distribution<int> uni(0, 1048575); 

if (bPlain) 
    for (int i=0; i<n; i++) 
     sum |= i; 
else 
    for (int i=0; i<n; i++) 
     sum |= uni(rng); 

wir bekommen (merken wir tun 1E8 läuft, nicht 1e9):

[~/CPP] time ./randbm2 100000000 
2.478u 0.003s 0:02.49 99.1% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm2 100000000 
2.471u 0.004s 0:02.47 100.0% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm2 100000000 
2.445u 0.007s 0:02.48 98.3% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm2 100000000 
2.497u 0.004s 0:02.50 99.6% 0+0k 0+0io 0pf+0w 
[~/CPP] time ./randbm2 100000000 
2.482u 0.011s 0:02.49 100.0% 0+0k 0+0io 0pf+0w 

eine Zufallszahl auf diese Weise produzieren dauert etwa 25 ns. uni fügt jedoch im Gegensatz zu rand() die Nummer ebenfalls in das Intervall ein.

Ist diese zusätzliche Arbeit wichtig? Wenn Sie beispielsweise

sum |= (rand() % 1048576); 

tun, erhöht sich die Zeit von 9 auf 9,5 Nanosekunden. Wenn die Nummer keine Potenz von 2 ist, e. G.

sum |= (rand() % 1000000); 

Es dauert 10 Nanosekunden. Andere sinnvolle Methoden, die Zahl in das Intervall einzufügen, nehmen ungefähr die gleiche Zeit in Anspruch.

So, für eine bestimmte Konfiguration, rand() selbst dauert ungefähr 9 Nanosekunden; zusammen mit dem Einfügen der Zufallszahl in das Intervall dauert es ungefähr 9,5-10 Nanosekunden; std::mt19937 mit uniform_int_distribution<int> dauert ungefähr 25 Nanosekunden.

Ich hoffe, Sie sind keiner von denen, die Nanosekunden mit Mikrosekunden verwechseln!