Ich arbeite gerade an einem C / C ++ Projekt, wo ich einen Zufallszahlengenerator verwende ( gsl ) oder Boost ). Die ganze Idee kann zu einem nicht-trivialen stochastischen Prozess vereinfacht werden, der einen Seed erhält und Ergebnisse liefert. Ich berechne Durchschnittswerte über verschiedene Realisierungen des Prozesses.
Der Samen ist also wichtig: Die Prozesse müssen mit verschiedenen Samen sein oder die Durchschnittswerte beeinflussen.
Bisher verwende ich time(NULL) , um einen Seed zu geben. Wenn jedoch zwei Prozesse in derselben Sekunde beginnen, ist der Seed identisch. Das passiert, weil ich die Parallelisierung verwende (mit openMP ).
Meine Frage ist also: Wie implementiert man einen "Seed Geber" auf C / C ++, der unabhängige Seeds liefert?
Ich benutzte zum Beispiel die Thread-Nummer ( thread_num ), seed = time(NULL)*thread_num . Dies bedeutet jedoch, dass die Samen korreliert sind: Sie sind mehrere von einander. Stellt das "Pseudozufalls" ein Problem dar oder ist es so gut wie sequenzielle Seeds?
Die Voraussetzungen sind, dass es sowohl auf Mac OS (mein PC) als auch auf Linux-Distribution ähnlich wie OS Cent (der Cluster) funktionieren muss (und natürlich unabhängige Realisierungen geben).
Wir hatten ein ähnliches Problem in einem Beowulf-Computing-Grid. Die Lösung, die wir verwendeten, bestand darin, das pid des Prozesses in den RNG-Seed zu integrieren:
%Vor%Natürlich könnten Sie einfach aus / dev / urandom oder / dev / random in eine ganze Zahl lesen.
Ein häufig verwendetes Schema hierfür ist ein "Master" -RNG, der zum Erzeugen von Seeds für jeden prozessspezifischen RNG verwendet wird.
Der Vorteil eines solchen Schemas ist, dass die gesamte Berechnung nur von einem Seed bestimmt wird, den Sie irgendwo aufzeichnen können, um eine Simulation wiederzugeben (dies könnte nützlich sein, um böse Bugs zu debuggen).
Wenn ich mit diesem Problem konfrontiert werde, benutze ich oft seed_rng von Boost .Uuid. Es verwendet time , clock und zufällige Daten von /dev/urandom , um einen Seed zu berechnen. Sie können es wie
Beachten Sie, dass seed_rng von einem detail -Namespace kommt, so dass es ohne weitere Benachrichtigung entfernt werden kann. In diesem Fall sollte es nicht zu schwer sein, eine eigene Implementierung basierend auf seed_rng zu schreiben.
Mac OS ist auch Unix, also hat es wahrscheinlich /dev/random . Wenn ja, das ist das
beste Lösung für den Erhalt der Samen. Andernfalls falls der Generator ist
Gut, nehmen Sie time( NULL ) einmal, und erhöhen Sie es dann für den Samen
von jedem Generator, sollte ziemlich gute Ergebnisse geben.
Wenn wir zwei unendliche Zeitfolgen vergleichen, die von demselben Pseudozufallszahlengenerator mit verschiedenen Seeds erzeugt werden, können wir sehen, dass sie um einige Zeit tau gleich verzögert sind. Normalerweise ist diese Zeitskala viel größer als Ihr Problem, um sicherzustellen, dass die beiden zufälligen Wanderungen nicht korreliert sind.
Wenn Ihr stochastischer Prozess in einem hochdimensionalen Phasenraum ist, denke ich, dass ein guter Vorschlag sein könnte:
%Vor%Beachten Sie, dass Sie mit dem Schema nicht garantieren, dass die Zeit tau groß ist!
Wenn Sie etwas über Ihre Systemzeitskala wissen, können Sie Ihren Zufallszahlengenerator eine beliebige Anzahl mal aufrufen, um Samen zu erzeugen, die um ein Zeitintervall äquidistant sind.
Vielleicht könntest du std :: chrono high resolution clock von C ++ 11 ausprobieren:
Klasse std :: chrono :: high_resolution_clock repräsentiert die Uhr mit dem kleinste Tick-Periode, die auf dem System verfügbar ist. Es kann ein Alias von sein std :: chrono :: system_clock oder std :: chrono :: steady_clock, oder ein drittes, unabhängige Uhr.
ABER tbh Ich bin mir nicht sicher, ob irgendwas mit srand falsch ist (0); Srand (1), Srand (2) .... aber mein Wissen über Rand ist sehr, sehr einfach. : /
Für verrückte Sicherheit beachten Sie dies:
Beachten Sie, dass alle unten beschriebenen Pseudozufallszahlengeneratoren sind CopyConstructible und Zuweisbar. Kopieren oder Zuweisen eines Generators kopiert seinen gesamten internen Zustand, also das Original und die Kopie erzeuge die identische Folge von Zufallszahlen.
Da die meisten Generatoren verrückte lange Zyklen haben, könnten Sie einen erzeugen, als ersten Generator kopieren, X-Nummern mit Original erzeugen, als zweiten kopieren, X-Nummern mit Original erzeugen, als dritten kopieren ... Wenn Ihre Benutzer weniger als X Mal ihren eigenen Generator anrufen, werden sie sich nicht überschneiden.
So, wie ich Ihre Frage verstanden habe, haben Sie mehrere Prozesse, die denselben Pseudozufallszahlengenerierungsalgorithmus verwenden, und Sie möchten, dass jeder "Strom" von Zufallszahlen (in jedem Prozess) unabhängig voneinander ist. Habe ich Recht?
In diesem Fall haben Sie recht, wenn Sie den Verdacht haben, dass die Vergabe anderer (korrelierter) Samen Ihnen nichts garantiert, es sei denn, der Rng-Algorithmus sagt dies. Sie haben grundsätzlich zwei Lösungen:
Verwenden Sie eine einzelne Quelle von Zufallszahlen mit einem einzelnen Seed. Fädeln Sie dann für jeden Prozess Zufallszahlen in einer Round-Robin-Art ein.
Diese Lösung ist langsam, bietet aber eine gewisse Garantie, dass die Anzahl, die Sie Ihren Prozessen geben, in Ordnung ist.
Sie können dasselbe tun, aber alle Zufallszahlen, die Sie benötigen, gleichzeitig erzeugen und diese Menge in so viele Schichten aufteilen, wie Sie Prozesse haben.
In Papieren und im Internet finden Sie verschiedene Algorithmen, die speziell entwickelt wurden, um unabhängige Ströme von Zufallszahlen aus einem einzigen Ausgangszustand zu erzeugen. Sie sind kompliziert, aber die meisten stellen Quellcode zur Verfügung. Die Idee ist allgemein, den RNG-Raum (Werte, die man aus dem Anfangszustand erhalten kann) in verschiedene Teile wie oben zu "teilen". Sie sind nur schneller, weil der verwendete Algorithmus es ermöglicht, leicht zu berechnen, was der Zustand des RNG wäre, wenn Sie eine bestimmte Anzahl von Werten überspringen würden.
Diese Generatoren werden allgemein als "parallele Zufallszahlengeneratoren" bezeichnet. Die beliebtesten sind wahrscheinlich diese beiden:
Überprüfen Sie ihre Handbücher, um zu verstehen, was sie tun, wie sie es tun und ob es wirklich das ist, was Sie brauchen.
Sie könnten std::random_device verwenden, um nicht-deterministische Zufallszahlen zu erzeugen.
Tags und Links c c++ random parallel-processing