Méthode recommandée pour initialiser srand?

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

  •  11-07-2019
  •  | 
  •  

Question

J'ai besoin d'un "bon" moyen pour initialiser le générateur de nombres pseudo-aléatoires en C ++. J'ai trouvé un article :

  

Afin de générer de manière aléatoire   nombres, le srand est généralement initialisé   à une valeur distinctive, comme celles   en relation avec le temps d'exécution. Pour   Par exemple, la valeur renvoyée par le   temps de fonction (déclaré dans l'en-tête   ctime) est différent chaque seconde, ce qui   est assez distinctif pour la plupart   besoins aléatoires.

Unixtime n'est pas assez distinctif pour mon application. Quelle est la meilleure façon d'initialiser cela? Des points bonus s'il est portable, mais le code sera principalement exécuté sur des hôtes Linux.

Je pensais faire un calcul mathématique pid / unixtime pour obtenir un int, ou éventuellement lire les données de /dev/urandom.

Merci!

MODIFIER

Oui, je commence mon application plusieurs fois par seconde et j'ai eu des collisions.

Était-ce utile?

La solution

La meilleure solution consiste à utiliser le nombre aléatoire de Boost. Ou, si vous avez accès à C ++ 11, utilisez l’en-tête <random> .

Mais si nous parlons de rand() et srand()
Le meilleur moyen consiste simplement à utiliser time(): 

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

    ...
}

Assurez-vous de le faire au début de votre programme, et pas à chaque fois que vous appelez <=>!

A chaque démarrage, time () renverra une valeur unique (à moins que vous ne lanciez l'application plusieurs fois par seconde). Dans les systèmes 32 bits, cela ne se répète que tous les 60 ans environ.

Je sais que vous ne pensez pas que le temps est suffisamment unique, mais je trouve cela difficile à croire. Mais on me sait que je me trompe.

Si vous démarrez plusieurs copies de votre application simultanément, vous pouvez utiliser une minuterie avec une résolution plus fine. Mais vous risquez alors de perdre du temps avant que la valeur ne se répète.

OK, donc si vous pensez vraiment que vous démarrez plusieurs applications à la seconde.
Ensuite, utilisez un grain plus fin sur la minuterie. 

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

Autres conseils

C’est ce que j’ai utilisé pour les petits programmes en ligne de commande pouvant être exécutés fréquemment (plusieurs fois par seconde): 

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

Où mélange est: 

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

si vous avez besoin d’un meilleur générateur de nombres aléatoires, n’utilisez pas libc rand. Utilisez plutôt quelque chose comme /dev/random ou /dev/urandom directement (lisez-la dans un int directement de celui-ci ou quelque chose comme ça).

Le seul avantage réel du rand libc est qu’il est prévisible, ce qui facilite le débogage à partir d’une graine.

Sous Windows: 

srand(GetTickCount());

fournit une meilleure graine que time() depuis ses millisecondes.

C ++ 11 random_device

Si vous avez besoin d’une qualité raisonnable, vous ne devriez pas utiliser rand () en premier lieu; vous devriez utiliser la <random> bibliothèque. Il offre de nombreuses fonctionnalités intéressantes, comme une variété de moteurs pour différents compromis qualité / taille / performances, nouvelle entrée et distributions prédéfinies, afin que vous ne vous trompiez pas. Il peut même offrir un accès facile à des données aléatoires non déterministes (par exemple, / dev / random), en fonction de votre implémentation. 

#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 est une source d’aléatoire, ici une implémentation intégrée de mersenne twister. Nous le semons en utilisant random_device, qui, dans toute implémentation décente, sera un RNG non déterministe, et seed_seq pour combiner plus de 32 bits de données aléatoires. Par exemple, dans libc ++, random_device accède à / dev / urandom par défaut (vous pouvez cependant lui donner un autre fichier auquel accéder).

Nous créons ensuite une distribution telle que, dans le cas d’une source aléatoire, des appels répétés à la distribution produiront une distribution uniforme des ints de 1 à 100. Nous passons ensuite à l’utilisation répétée de la distribution et à l’impression des résultats.

La meilleure solution consiste à utiliser un autre générateur de nombres pseudo-aléatoires. Mister Twister (et Wichmann-Hill) est ma recommandation.

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

Je vous suggère de voir le fichier unix_random.c dans le code mozilla. (devinez que c'est mozilla / security / freebl / ...) cela devrait être dans la bibliothèque freebl.

il utilise les informations d’appel système (telles que pwd, netstat, etc.) pour générer du bruit pour le nombre aléatoire; il est écrit pour prendre en charge la plupart des plates-formes (qui peut me rapporter un point de bonus: D).

La vraie question que vous devez vous poser est de savoir quelle qualité aléatoire vous avez besoin.

libc random est un LCG

La qualité du caractère aléatoire sera faible quelle que soit l’entrée que vous fournissez à srand.

Si vous devez simplement vous assurer que les différentes instances auront des initialisations différentes, vous pouvez combiner un id de processus (getpid), un id de fil et un minuteur. Mélangez les résultats avec xor. L'entropie devrait suffire pour la plupart des applications.

Exemple: 

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

Pour une meilleure qualité aléatoire, utilisez / dev / urandom. Vous pouvez rendre le code ci-dessus portable en utilisant boost :: thread et boost :: date_time.

La c++11 version du message le plus voté de 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 est en microsecondes. Cela devrait être une graine acceptable.

Supposons que vous ayez une fonction avec une signature telle que: 

int foo(char *p);

Une excellente source d'entropie pour une graine aléatoire est un hachage de ce qui suit:

  • Résultat complet de clock_gettime (secondes et nanosecondes) sans perdre les bits les plus faibles - ce sont les plus précieux.
  • La valeur de p, convertie en uintptr_t.
  • L'adresse de rand, convertie en srand.

Au moins le troisième, et éventuellement le second, dérive l'entropie de l'ASLR du système, le cas échéant (l'adresse de pile initiale et donc l'adresse de pile actuelle sont quelque peu aléatoires).

J'éviterais également d'utiliser <=> / <=> entièrement, afin de ne pas toucher à l'état global, et vous pourrez ainsi mieux contrôler le PRNG utilisé. Mais la procédure ci-dessus est un bon moyen (et assez portable) d’obtenir une entropie décente sans trop de travail, quel que soit le type de PRNG que vous utilisez.

Pour ceux qui utilisent Visual Studio, voici un autre moyen: 

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

}

Peut-être un peu exagéré, mais fonctionne bien pour des intervalles rapides. La fonction gettimeofday a trouvé ici .

Edit: après une enquête plus approfondie, rand_s pourrait être une bonne alternative à Visual Studio. J'avais supposé qu'il était presque identique à rand, mais & "Plus sûr &";.

Pour utiliser rand_s, n'oubliez pas de #define _CRT_RAND_S avant que stdlib.h ne soit inclus.

Tant que votre programme ne fonctionne que sous Linux (et que ce programme est un exécutable ELF), vous êtes assuré que le noyau fournit à votre processus une graine aléatoire unique dans le vecteur ELF aux. Le noyau vous donne 16 octets aléatoires, différents pour chaque processus, que vous pouvez obtenir avec getauxval(AT_RANDOM). Pour les utiliser pour srand, utilisez-en simplement un int, en tant que tel: 

#include <sys/auxv.h>

void initrand(void)
{
    unsigned int *seed;

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

Il est possible que cela se traduise également par d'autres systèmes basés sur ELF. Je ne sais pas quelles valeurs aux sont implémentées sur des systèmes autres que Linux.

Incluez l'en-tête en haut de votre programme et écrivez: 

srand(time(NULL));

Dans votre programme avant de déclarer votre nombre aléatoire. Voici un exemple de programme qui imprime un nombre aléatoire compris entre un et dix: 

#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;
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top