Modo consigliato per inizializzare srand?

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

  •  11-07-2019
  •  | 
  •  

Domanda

Ho bisogno di un modo "buono" per inizializzare il generatore di numeri pseudo-casuali in C ++. Ho trovato un articolo che afferma:

  

Per generare un tipo casuale   numeri, di solito viene inizializzato   a un valore distintivo, come quelli   in relazione al tempo di esecuzione. Per   esempio, il valore restituito da   tempo di funzione (dichiarato nell'intestazione   ctime) è diverso ogni secondo, che   è abbastanza distintivo per la maggior parte   bisogni in crescita.

Unixtime non è abbastanza distintivo per la mia applicazione. Qual è il modo migliore per inizializzare questo? Punti bonus se è portatile, ma il codice verrà eseguito principalmente su host Linux.

Stavo pensando di fare un po 'di matematica pid / unixtime per ottenere un int o eventualmente leggere i dati da /dev/urandom.

Grazie!

Modifica

Sì, sto effettivamente avviando la mia applicazione più volte al secondo e ho riscontrato collisioni.

È stato utile?

Soluzione

La migliore risposta è usare il numero casuale Boost. Oppure, se hai accesso a C ++ 11, usa l'intestazione <random> .

Ma se stiamo parlando di rand() e srand()
Il modo migliore è usare time(): 

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

    ...
}

Assicurati di farlo all'inizio del programma e non tutte le volte che chiami <=>!

Ogni volta che si avvia, time () restituirà un valore univoco (a meno che non si avvia l'applicazione più volte al secondo). Nei sistemi a 32 bit, si ripeterà solo ogni 60 anni circa.

So che non pensi che il tempo sia abbastanza unico, ma lo trovo difficile da credere. Ma sono stato conosciuto per essere sbagliato.

Se stai avviando molte copie della tua applicazione contemporaneamente puoi usare un timer con una risoluzione più fine. Ma poi corri il rischio di un periodo di tempo più breve prima che il valore si ripeta.

OK, quindi se pensi davvero di avviare più applicazioni al secondo.
Quindi usa una grana più fine sul timer. 

 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.
 }

Altri suggerimenti

Questo è quello che ho usato per piccoli programmi da riga di comando che possono essere eseguiti frequentemente (più volte al secondo): 

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

Dove si trova il mix: 

// 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;
}

se hai bisogno di un miglior generatore di numeri casuali, non usare il libc rand. Invece usa semplicemente qualcosa come /dev/random o /dev/urandom direttamente (leggi in un int direttamente da esso o qualcosa del genere).

L'unico vero vantaggio del rand libc è che dato un seme, è prevedibile che aiuta con il debug.

Su Windows: 

srand(GetTickCount());

fornisce un seme migliore di time() poiché è espresso in millisecondi.

C ++ 11 random_device

Se hai bisogno di una qualità ragionevole, non dovresti usare rand () in primo luogo; dovresti usare la <random> libreria. Fornisce molte funzionalità eccezionali come una varietà di motori per diversi compromessi di qualità / dimensioni / prestazioni, re-immissione e distribuzioni predefinite in modo da non sbagliare. Può anche fornire un facile accesso a dati casuali non deterministici, (ad esempio, / dev / random), a seconda dell'implementazione. 

#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 è una fonte di casualità, qui un'implementazione integrata di mersenne twister. Lo seminiamo usando random_device, che in qualsiasi implementazione decente sarà un RNG non determinanistico, e seed_seq per combinare più di 32 bit di dati casuali. Ad esempio in libc ++ random_device accede / dev / urandom di default (anche se invece puoi dargli un altro file per accedervi).

Successivamente creiamo una distribuzione tale che, data una fonte di casualità, le chiamate ripetute alla distribuzione produrranno una distribuzione uniforme di ints da 1 a 100. Quindi procediamo a utilizzare ripetutamente la distribuzione e stampare i risultati.

Il modo migliore è usare un altro generatore di numeri pseudocasuali. Il mio tornado di Mersenne (e Wichmann-Hill) è la mia raccomandazione.

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

ti suggerisco di vedere il file unix_random.c nel codice mozilla. (immagino che sia mozilla / security / freebl / ...) dovrebbe essere nella libreria freebl.

lì usa le informazioni di chiamata del sistema (come pwd, netstat ....) per generare rumore per il numero casuale; è scritto per supportare la maggior parte delle piattaforme (che può ottenere punti bonus: D).

La vera domanda che devi porti è quale qualità di casualità hai bisogno.

libc random è un LCG

La qualità della casualità sarà bassa qualunque sia l'input fornito.

Se devi semplicemente assicurarti che istanze diverse abbiano inizializzazioni diverse, puoi mescolare id di processo (getpid), id di thread e un timer. Mescola i risultati con xor. L'entropia dovrebbe essere sufficiente per la maggior parte delle applicazioni.

Esempio: 

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

Per una migliore qualità casuale, utilizzare / dev / urandom. Puoi rendere portatile il codice precedente usando boost :: thread e boost :: date_time.

La c++11 versione del post più votato da 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 è in microsecondi. Questo dovrebbe essere un seme accettabile.

Supponi di avere una funzione con una firma come: 

int foo(char *p);

Un'eccellente fonte di entropia per un seme casuale è un hash di quanto segue:

  • Risultato completo di clock_gettime (secondi e nanosecondi) senza eliminare i bit bassi: sono i più preziosi.
  • Il valore di p, trasmesso a uintptr_t.
  • L'indirizzo di rand, trasmesso a srand.

Almeno il terzo, e forse anche il secondo, derivano entropia dall'ASLR del sistema, se disponibile (l'indirizzo di stack iniziale, e quindi l'indirizzo di stack corrente, è in qualche modo casuale).

Eviterei anche di utilizzare <=> / <=> interamente, sia per non toccare lo stato globale, sia per avere un maggiore controllo sul PRNG utilizzato. Ma la procedura di cui sopra è un buon (e abbastanza portatile) modo per ottenere un po 'di entropia decente senza molto lavoro, indipendentemente dal PRNG che usi.

Per coloro che usano Visual Studio ecco un altro modo: 

#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);

}

Forse un po 'eccessivo ma funziona bene per intervalli veloci. trovata la funzione gettimeofday here .

Modifica: dopo ulteriori indagini rand_s potrebbe essere una buona alternativa a Visual Studio, non è solo un rand sicuro (), è totalmente diverso e non usa il seme di srand. Avevo presunto che fosse quasi identico a Rand solo & Quot; più sicuro & Quot ;.

Per usare rand_s non dimenticare di #define _CRT_RAND_S prima di includere stdlib.h.

Finché il tuo programma è in esecuzione solo su Linux (e il tuo programma è un eseguibile ELF), sei sicuro che il kernel fornisce al tuo processo un seme casuale univoco nel vettore aux ELF. Il kernel ti dà 16 byte casuali, diversi per ogni processo, che puoi ottenere con getauxval(AT_RANDOM). Per usarli per srand, usane solo int, come tali: 

#include <sys/auxv.h>

void initrand(void)
{
    unsigned int *seed;

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

Potrebbe essere possibile che ciò si traduca anche in altri sistemi basati su ELF. Non sono sicuro di quali valori aux siano implementati su sistemi diversi da Linux.

Includi l'intestazione nella parte superiore del programma e scrivi: 

srand(time(NULL));

Nel tuo programma prima di dichiarare il tuo numero casuale. Ecco un esempio di un programma che stampa un numero casuale compreso tra uno e dieci: 

#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;
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top