Benötigen Sie einen schnellen Zufallsgenerator für C++

Question

Ich versuche, opt-3 Swapping auf meinem TSP-Generator für euklidische Entfernungen zu tun, und da ich in vielen Fällen mehr als ~ 500 Knoten habe, muss ich nach dem Zufallsprinzip wählen mindestens 1 der 3 Knoten, die ich tauschen möchte.

Also im Grunde brauche ich eine Zufallszahl-Funktion, die schnell ist. (Der normale Rand() ist viel zu langsam) Es muss nicht großartig sein, nur gut genug.

EDIT: Ich habe vergessen zu erwähnen, ich bin in einer Umgebung sitzen, wo ich keine Bibliotheken außer der Standard Language Library (wie STL, Iostream usw.) hinzufügen kann. Also keine boost =/

Answer 1

Der andere Thread erwähnt Marsaglias Xorshf-Generator, aber niemand hat den Code veröffentlicht.

static unsigned long x=123456789, y=362436069, z=521288629; 

unsigned long xorshf96(void) {   //period 2^96-1 
unsigned long t; 
    x ^= x << 16; 
    x ^= x >> 5; 
    x ^= x << 1; 

    t = x; 
    x = y; 
    y = z; 
    z = t^x^y; 

    return z; 
} 

Ich habe diese überall verwendet. Der einzige Ort, an dem es scheiterte, war, wenn ich versuchte, zufällige Binärmatrizen zu erzeugen. Nach etwa 95x95 Matrizen beginnt es, zu wenige oder zu viele singuläre Matrizen zu erzeugen (ich vergesse das). Es wurde gezeigt, dass dieser Generator einem linearen Rückkopplungsregister entspricht. Aber es sei denn, Sie tun Kryptographie oder ernsthafte Monte Carlo Arbeit, dieser Generator rockt.

Answer 2

können Sie eine Reihe von zufälligen Bits vor der Zeit vorgenerieren und sie 2 auf einmal abziehen (da Sie nur eine Zufallszahl zwischen 1 und 3 benötigen)?

Answer 3

Boost-Bibliothek verfügt über eine Reihe von Zufallsgeneratoren. Leistungsdiagramm könnte here gefunden werden.

EDIT: Diese Antwort war hier vor der Bearbeitung der ursprünglichen Frage. Aber ich hoffe, es könnte noch hilfreich sein, also lasse ich es hier.

Answer 4

Die Mersenne Twister hat einige schnelle Implementierungen.

Answer 5

rand() ist wirklich verdammt schnell, und ich glaube nicht, dass Sie viel schneller finden werden.

Wenn es in der Tat verlangsamt Sie (was ich irgendwie bezweifle), dann brauchen Sie eine Architekturänderung.

Ich empfehle, eine lange Liste mit Zufallszahlen vorzufüllen, und wenn Sie eine benötigen, nehmen Sie einfach eine aus der Liste, anstatt eine zu erstellen. Möglicherweise können Sie die Liste erneut mit einem Hintergrundthread füllen.

Answer 6

Siehe these generators von Zufallsgenerator Generator George Marsaglia. Sie sind als C-Makros implementiert, und sie sind blitzschnell, nur ein paar Operationen pro Nummer generiert.

Answer 7

Zwei gute Alternativen von Intel-Website:

1) fastrand - es ist 2.01 X schneller als der std rand(). Die Routine gibt einen ganzzahligen ähnlichen Ausgabewertbereich wie C lib zurück.

inline int fastrand() { 
    g_seed = (214013*g_seed+2531011); 
    return (g_seed>>16)&0x7FFF; 
} 

2) eine SSE-Version (siehe Link unten) ist etwa 5,5 X so schnell wie std ränder() aber es erzeugt 4 Zufallswerte zu einem Zeitpunkt, erfordert eine processer mit sse (fast alle tun), und ist komplizierter.

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

Answer 8

Ich denke WELL ist ziemlich gut, und WELL512a ist ziemlich kurz. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a ist zu der Zeit auch komplex. WELL erzeugt jedoch eine Zahl zwischen 0 und 1.

Answer 9

Sogar dieser Beitrag ist Jahre alt, es zeigte sich, als ich nach einer ähnlichen Antwort suchte, und die Antwort, die ich mit der Verwendung, nicht sogar darin bin. Also füge ich den hinzu, den ich gefunden habe;

#include <random> msdn entry

Dieser Ansatz wird ein in sich geschlossenes Zufallsgenerator bauen, und ich fand es viel mehr zufällig als rand()%x zu sein; über ein paar hunderttausend Iterationen. rand()% würde nie 16+ Köpfe/Schwänze in Folge werfen, wenn es alle anderen 65k Versuche versuchen sollte. Das macht nicht nur das, aber es macht es in einem Viertel der Zeit.

Dies ist, wie ich mich #include <random> implementieren:

//create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice); 
std::random_device rd; //seed 
std::mt19937 gen(rd()); //seed for rd(merzenne twister) 
std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range 
std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range 

rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast 
rng_dice(gen); //will apply rng2 range, returns int. 

//will output 1000 cointosses to console 
for (int i=0;i<1000;++i)std::cout<<rng_coin(gen)<<"\n"; 
//will generate 1000 dice throws 
for (int i=0;i<1000;++i)rng_dice(gen); 

Answer 10

mit Ivy Bridge Architektur Ab Intel hinzugefügt RdRand CPU-Befehl und AMD es später im Juni 2015 hinzugefügt Also, wenn Sie einen Prozessor-Targeting, die neu genug und don ist Wenn Sie (Inline-) Assembly verwenden, sollte der schnellste Weg zum Generieren von Zufallszahlen in dem Aufruf RdRand CPU-Anweisung sein, eine 16- oder 32- oder 64-Bit-Zufallszahl wie beschrieben here zu erhalten. Scrollen Sie ungefähr zur Mitte der Seite, um Codebeispiele zu erhalten. An dieser Verbindung gibt es auch ein Codebeispiel zum Überprüfen der aktuellen CPU auf Unterstützung der RdRand-Anweisung, und siehe auch die Wikipedia für eine Erläuterung, wie dies mit der CPUID-Anweisung zu tun ist.

Verwandte Frage: Making use of sandy bridge's hardware true random number generator? (obwohl Wikipedia nach, RdRand Anweisung zuerst in Ivy Bridge erschien, aber nicht Sandy-Bridge-Architektur, wie diese Frage sagt)

Beispiel C-Code ++ basierend auf _rdrand64_step():

#include <immintrin.h> 

uint64_t randVal; 
if(!_rdrand64_step(&randVal)) { 
    // Report an error here: random number generation has failed! 
} 
// If no error occured, randVal contains a random 64-bit number