Empfohlene Weise srand zu initialisieren?

StackOverflow https://stackoverflow.com/questions/322938

  •  11-07-2019
  •  | 
  •  

Frage

Ich brauche einen ‚guten‘ Weg, um den Pseudo-Zufallszahlengenerator in C ++ zu initialisieren. Ich habe einen Artikel , die besagt:

  

Um zufall wie zu erzeugen   Zahlen wird in der Regel srand initialisiert   bis zu einem gewissen Unterscheidungswert, wie die   mit der Ausführungszeit verwendet. Zum   Beispiel kehrte der Wert durch die   Funktion Zeit (deklariert in Kopf   Ctime) unterscheidet sich jede Sekunde, die   unverwechselbar genug ist für die meisten   randoming Bedürfnisse.

Unix-Zeit ist nicht unterscheidungskräftig genug für meine Anwendung. Was ist ein besserer Weg, dies zu initialisieren? Bonuspunkte, wenn es tragbar, aber der Code wird in erster Linie auf Linux-Hosts ausgeführt werden.

Ich dachte an etwas pid / Unix-Zeit Mathe tat einen int zu bekommen, oder möglicherweise Daten von /dev/urandom zu lesen.

Danke!

Bearbeiten

Ja, ich fange eigentlich meine Anwendung mehrere Male pro Sekunde, und ich habe in Kollisionen führen.

War es hilfreich?

Lösung

Die beste Antwort ist die Boost-Zufallszahl Sachen zu verwenden. Oder wenn Sie Zugriff auf C ++ 11 Verwendung der <random> Header.

Aber wenn wir sprechen über rand() und srand()
Der beste Weg ist nur time() zu verwenden: 

int main()
{
    srand(time(NULL));

    ...
}

Seien Sie sicher, dass dies am Anfang des Programms zu tun, und nicht jedes Mal, wenn Sie anrufen rand()!

Jedes Mal, wenn Sie starten, time () einen eindeutigen Wert zurück (es sei denn, Sie die Anwendung mehrere Male pro Sekunde gestartet werden). In 32-Bit-Systemen, wird es nur alle 60 Jahre wiederholen oder so.

Ich weiß, dass Sie nicht denken, Zeit einzigartig genug ist, aber ich finde, dass schwer zu glauben. Aber ich habe bekannt als falsch.

Wenn Sie eine Menge von Kopien Ihrer Anwendung gleichzeitig starten Sie einen Timer mit einer feineren Auflösung verwenden könnte. Aber dann laufen Sie Gefahr, von einer kürzeren Zeitspanne, bevor der Wert wiederholt.

OK, also, wenn Sie wirklich, dass Sie mehrere Anwendungen ein zweites beginnen.
Dann ein feineres Korn auf dem Timer verwendet werden. 

 int main()
 {
     struct timeval time; 
     gettimeofday(&time,NULL);

     // microsecond has 1 000 000
     // Assuming you did not need quite that accuracy
     // Also do not assume the system clock has that accuracy.
     srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

     // The trouble here is that the seed will repeat every
     // 24 days or so.

     // If you use 100 (rather than 1000) the seed repeats every 248 days.

     // Do not make the MISTAKE of using just the tv_usec
     // This will mean your seed repeats every second.
 }

Andere Tipps

Das ist, was ich für kleines Kommandozeilen-Programme verwendet, die häufig ausgeführt werden kann (mehrere Male pro Sekunde): 

unsigned long seed = mix(clock(), time(NULL), getpid());

Wo Mischung ist: 

// http://www.concentric.net/~Ttwang/tech/inthash.htm
unsigned long mix(unsigned long a, unsigned long b, unsigned long c)
{
    a=a-b;  a=a-c;  a=a^(c >> 13);
    b=b-c;  b=b-a;  b=b^(a << 8);
    c=c-a;  c=c-b;  c=c^(b >> 13);
    a=a-b;  a=a-c;  a=a^(c >> 12);
    b=b-c;  b=b-a;  b=b^(a << 16);
    c=c-a;  c=c-b;  c=c^(b >> 5);
    a=a-b;  a=a-c;  a=a^(c >> 3);
    b=b-c;  b=b-a;  b=b^(a << 10);
    c=c-a;  c=c-b;  c=c^(b >> 15);
    return c;
}

Wenn Sie einen besseren Zufallszahlengenerator benötigen, nicht den libc Rand verwenden. Statt nur direkt etwas wie /dev/random oder /dev/urandom verwenden (lesen Sie in einem int direkt von ihm oder so ähnlich).

Der einzige wirkliche Vorteil des libc rand, dass ein Samen gegeben ist, ist es vorhersehbar, welche mit Debugging hilft.

Unter Windows: 

srand(GetTickCount());

bietet eine bessere Samen als time() seit seinem in Millisekunden.

C ++ 11 random_device

Wenn Sie vernünftige Qualität benötigen, dann sollten Sie nicht rand werden () an erster Stelle; Sie sollten die <random> Bibliothek verwenden. Es bietet viele tolle Funktionen, wie eine Vielzahl von Motoren für unterschiedliche Qualität / Größe / Leistungskompromisse, Neueintritt und vordefinierte Verteilungen, so dass Sie am Ende nicht sie vertun. Es kann sogar einen einfachen Zugang zu nicht-deterministischen Zufallsdaten (beispielsweise / dev / random) liefern, abhängig von der jeweiligen Implementierung. 

#include <random>
#include <iostream>

int main() {
    std::random_device r;
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
    std::mt19937 eng(seed);

    std::uniform_int_distribution<> dist{1,100};

    for (int i=0; i<50; ++i)
        std::cout << dist(eng) << '\n';
}

eng ist eine Quelle der Zufälligkeit, hier eine eingebaute bei der Umsetzung von Mersenne-Twister-. Wir säen es random_device verwenden, die in jeder anständige Implementierung wird ein nicht-determanistic RNG sein und seed_seq auf mehr als 32-Bit Zufallsdaten zu kombinieren. Zum Beispiel in libc ++ random_device greift auf / dev / urandom standardmäßig (obwohl Sie ihm eine andere Datei geben können stattdessen zuzugreifen).

Als nächstes erstellen wir eine Verteilung so, dass bei einer Zufallsquelle, wiederholten Aufforderungen an die Verteilung wird eine gleichmäßige Verteilung von Ints von 1 bis 100. produzieren Dann gehen wir die Verteilung immer wieder zu verwenden und das Drucken der Ergebnisse.

Der beste Weg ist, eine andere Pseudo-Zufallszahlengenerator zu verwenden. Mersenne-Twister (und Wichmann-Hill) ist meine Empfehlung.

http://en.wikipedia.org/wiki/Mersenne_twister

Ich schlage vor, Sie unix_random.c Datei in mozilla Code. (Denke, es ist mozilla / Sicherheit / freebl / ...) es in freebl Bibliothek sein sollte.

dort verwendet es Systemaufruf info (wie pwd, netstat ....) Rauschen für die Zufallszahl zu erzeugen; es steht geschrieben: die meisten der Plattformen zu unterstützen (was mir Bonuspunkt gewinnen kann: D)

Die eigentliche Frage, die Sie sich stellen müssen ist, was Zufälligkeit Qualität, die Sie benötigen.

libc zufällig ist ein LCG

Die Qualität der Zufälligkeit wird niedrig sein, was Eingang Sie bieten srand mit.

Wenn Sie einfach sicher vornehmen müssen, dass verschiedene Instanzen verschiedene Initialisierungen haben, können Sie Prozess-ID (getpid), Thread-ID und einen Timer mischen. Mischen Sie die Ergebnisse mit xor. Entropy sollte für die meisten Anwendungen ausreichend sein.

Beispiel: 

struct timeb tp;
ftime(&tp);   
srand(static_cast<unsigned int>(getpid()) ^ 
static_cast<unsigned int>(pthread_self()) ^ 
static_cast<unsigned int >(tp.millitm));

Für eine bessere Zufalls Qualität, / dev / urandom. Sie können den obigen Code tragbar machen Sie sich mit der boost :: thread und boost :: date_time.

Die c++11 Version der oben gestimmt Beitrag von Jonathan Wright: 

#include <ctime>
#include <random>
#include <thread>

...

const auto time_seed = static_cast<size_t>(std::time(0));
const auto clock_seed = static_cast<size_t>(std::clock());
const size_t pid_seed =
      std::hash<std::thread::id>()(std::this_thread::get_id());

std::seed_seq seed_value { time_seed, clock_seed, pid_seed };

...
// E.g seeding an engine with the above seed.
std::mt19937 gen;
gen.seed(seed_value);

#include <stdio.h>
#include <sys/time.h>
main()
{
     struct timeval tv;
     gettimeofday(&tv,NULL);
     printf("%d\n",  tv.tv_usec);
     return 0;
}

tv.tv_usec ist in Mikrosekunden. Dies sollte akzeptabel Samen sein.

Angenommen, Sie haben eine Funktion, mit einer Signatur wie: 

int foo(char *p);

Eine ausgezeichnete Quelle der Entropie für einen Zufallskeim ist ein Hash der folgenden:

  • Voll Ergebnis clock_gettime (Sekunden und Nanosekunden), ohne dass die Low-Bits Wegwerfen -. Sie die wertvollsten sind
  • Der Wert von p, gieße uintptr_t.
  • Die Adresse p, gieße uintptr_t.

zumindest die dritte und möglicherweise auch die zweite Ableitung der Entropie von ASLR des Systems, falls verfügbar (der Anfangsstapeladresse und somit aktuelle Stapeladresse, etwas zufällig ist).

Ich möchte vermeiden, auch ganz rand / srand verwenden, sowohl im Interesse der nicht globalen Zustand zu berühren, und so können Sie mehr Kontrolle über die PRNG haben, die verwendet wird. Aber das obige Verfahren ist eine gute (und ziemlich tragbar) Art und Weise ein paar anständige Entropie ohne viel Arbeit zu bekommen, unabhängig davon, welche PRNG Sie verwenden.

Für diejenigen, die mit Visual Studio hier ist noch eine weitere Möglichkeit: 

#include "stdafx.h"
#include <time.h>
#include <windows.h> 

const __int64 DELTA_EPOCH_IN_MICROSECS= 11644473600000000;

struct timezone2 
{
  __int32  tz_minuteswest; /* minutes W of Greenwich */
  bool  tz_dsttime;     /* type of dst correction */
};

struct timeval2 {
__int32    tv_sec;         /* seconds */
__int32    tv_usec;        /* microseconds */
};

int gettimeofday(struct timeval2 *tv/*in*/, struct timezone2 *tz/*in*/)
{
  FILETIME ft;
  __int64 tmpres = 0;
  TIME_ZONE_INFORMATION tz_winapi;
  int rez = 0;

  ZeroMemory(&ft, sizeof(ft));
  ZeroMemory(&tz_winapi, sizeof(tz_winapi));

  GetSystemTimeAsFileTime(&ft);

  tmpres = ft.dwHighDateTime;
  tmpres <<= 32;
  tmpres |= ft.dwLowDateTime;

  /*converting file time to unix epoch*/
  tmpres /= 10;  /*convert into microseconds*/
  tmpres -= DELTA_EPOCH_IN_MICROSECS; 
  tv->tv_sec = (__int32)(tmpres * 0.000001);
  tv->tv_usec = (tmpres % 1000000);


  //_tzset(),don't work properly, so we use GetTimeZoneInformation
  rez = GetTimeZoneInformation(&tz_winapi);
  tz->tz_dsttime = (rez == 2) ? true : false;
  tz->tz_minuteswest = tz_winapi.Bias + ((rez == 2) ? tz_winapi.DaylightBias : 0);

  return 0;
}


int main(int argc, char** argv) {

  struct timeval2 tv;
  struct timezone2 tz;

  ZeroMemory(&tv, sizeof(tv));
  ZeroMemory(&tz, sizeof(tz));

  gettimeofday(&tv, &tz);

  unsigned long seed = tv.tv_sec ^ (tv.tv_usec << 12);

  srand(seed);

}

Vielleicht ein bisschen übertrieben, aber funktioniert gut für den schnellen Intervallen. gettimeofday Funktion gefunden here .

Edit: bei einer weiteren Untersuchung rand_s könnte eine gute Alternative für Visual Studio sein, es ist nicht nur ein sicherer rand (), es ist ganz anders und verwendet nicht den Samen von srand. Ich hatte angenommen, sie rand fast identisch waren nur „sicherer“.

rand_s nutzen zu können, nur nicht vergessen, _CRT_RAND_S #define vor stdlib.h enthalten ist.

Solange Ihr Programm nur unter Linux (und Ihr Programm ist ein ELF ausführbare), werden Sie garantiert, dass der Kernel Ihren Prozess mit einem eindeutigen zufälligen Samen im ELF-aux-Vektor zur Verfügung stellt. Der Kernel gibt Ihnen 16 zufälliges Bytes, unterschiedlich für jeden Prozess, die Sie mit getauxval(AT_RANDOM) bekommen. Um diese zu nutzen für srand, benutzen Sie einfach eine int von ihnen, wie zum Beispiel: 

#include <sys/auxv.h>

void initrand(void)
{
    unsigned int *seed;

    seed = (unsigned int *)getauxval(AT_RANDOM);
    srand(*seed);
}

Es kann möglich sein, dass dies führt auch zu anderen ELF-basierten Systemen. Ich bin mir nicht sicher, was aux Werte auf Systemen implementiert sind andere als Linux.

Fügen Sie den Header an der Spitze des Programms, und schreibt: 

srand(time(NULL));

In Ihrem Programm, bevor Sie Ihre Zufallszahl erklären. Hier ist ein Beispiel für ein Programm, das druckt eine Zufallszahl zwischen eins und zehn: 

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
   //Initialize srand
   srand(time(NULL));

   //Create random number
   int n = rand() % 10 + 1;

   //Print the number
   cout << n << endl; //End the line

   //The main function is an int, so it must return a value
   return 0;
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top