random_shuffle-Algorithmus - werden ohne Zufallsgeneratorfunktion identische Ergebnisse erzielt?

Question

Wenn dem random_shuffle-Algorithmus in der Standardbibliothek keine Zufallsgeneratorfunktion zur Verfügung gestellt wird, werden dann aufeinanderfolgende Durchläufe des Programms die gleiche Zufallsfolge erzeugen, wenn sie mit den gleichen Daten versorgt werden?

Zum Beispiel, wenn

std::random_shuffle(filenames.begin(), filenames.end());

auf dieselbe Liste von Dateinamen eines Verzeichnisses in aufeinanderfolgenden Programmläufen angewendet wird, ist dann die erzeugte Zufallsfolge dieselbe wie im vorherigen Lauf?

Answer 1

Wenn Sie denselben Zufallsgenerator mit demselben Seed und demselben Startwert verwenden Sequenz, werden die Ergebnisse die gleichen sein. Ein Computer ist nun einmal, deterministisch in seinem Verhalten (abgesehen von Threading-Problemen und ein paar anderen Unwägbarkeiten).

Wenn Sie keinen Generator angeben, ist der Standardgenerator Implementierung definiert. Die meisten Implementierungen verwenden, glaube ich, die std::rand() (was zu Problemen führen kann, insbesondere wenn die Anzahl der Elemente in der Sequenz größer ist als RAND_MAX ). Ich würde empfehlen einen Generator mit bekannter Qualität zu kaufen und ihn zu verwenden.

Wenn Sie den verwendeten Generator nicht korrekt seeden (eine weitere Grund, nicht die Standardeinstellung zu verwenden, da die Art des Seeds von der Implementierung abhängt), dann bekommen Sie, was Sie bekommen. Im Fall von std::rand() verwendet die Standardeinstellung immer denselben Seed. Wie Sie den Seed hängt von dem verwendeten Generator ab. Was Sie zum Seeden verwenden, sollte sich von einem Lauf zum anderen variieren; für viele Anwendungen, time(NULL) ist ausreichend; auf einer Unix-Plattform würde ich empfehlen, so viele Bytes zu lesen, wie es zu lesen, die es von /dev/random . Andernfalls wird das Hashing anderer Informationen (IP Adresse des Rechners, Prozess-ID usw.) kann die Dinge auch verbessern - es bedeutet, dass zwei Benutzer, die das Programm in genau der gleichen Sekunde starten starten, trotzdem unterschiedliche Sequenzen erhalten werden. (Aber das ist wirklich nur relevant wenn Sie in einer vernetzten Umgebung arbeiten.)

Answer 2

25.2.11 besagt lediglich, dass die Elemente mit einer Gleichverteilung gemischt werden. Es wird nicht garantiert, welcher RNG hinter den Kulissen verwendet wird (es sei denn, Sie geben einen an), sodass Sie sich nicht auf ein solches Verhalten verlassen können.

Um das gleiche Shuffle-Ergebnis zu garantieren, müssen Sie Ihren eigenen RNG bereitstellen, der diese Garantien bietet, aber ich vermute, dass selbst dann, wenn Sie Ihre Standardbibliothek aktualisieren, der random_shuffle-Algorithmus selbst die Auswirkungen ändern könnte.

Answer 3

Sie können bei jedem Durchlauf des Programms ein identisches Ergebnis erzielen. Sie können einen benutzerdefinierten Zufallszahlengenerator (der von einer externen Quelle gespeist werden kann) als zusätzliches Argument zu std::random_shuffle wenn dies ein Problem ist. Die Funktion wäre das dritte Argument. Einige Leute empfehlen aufrufen srand(unsigned(time(NULL))); vor random_shuffle aber die Ergebnisse sind oft von der Umsetzung abhängig (und unzuverlässig ).