Forma recomendada para inicializar srand?

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

  •  11-07-2019
  •  | 
  •  

Pregunta

Necesito una "buena" manera de inicializar el generador de números pseudoaleatorios en C++.He encontrado un artículo que los estados:

Con el fin de generar al azar-como los números, srand generalmente es inicializado para algunos distintivos de valor, como los relacionados con el tiempo de ejecución.Para ejemplo, el valor devuelto por la la función de tiempo (declarado en el encabezado ctime) es diferente en cada segundo, que es distintivo suficiente para la mayoría de randoming necesidades.

Unixtime no es distintivo suficiente para mi aplicación.¿Qué es una mejor manera de inicializar esto?Los puntos de bonificación si es portable, pero el código será principalmente se ejecutan en los hosts Linux.

Yo estaba pensando en hacer algunos pid/unixtime matemáticas para obtener un int, o, posiblemente, la lectura de los datos de /dev/urandom.

Gracias!

EDITAR

Sí, de hecho, estoy empezando mi aplicación varias veces en un segundo y me he quedado en las colisiones.

¿Fue útil?

Solución

La mejor respuesta es la de utilizar el Impulso de números aleatorios cosas.O si usted tiene acceso a C++11 <random> encabezado.

Pero si estamos hablando de rand() y srand()
La mejor manera es usar time():

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

    ...
}

Asegúrese de hacer esto en el comienzo de su programa, y no cada vez que usted llame rand()!

Cada vez que se arranca, time() devolverá un valor único (a menos que usted inicie la aplicación varias veces por segundo).En sistemas de 32 bits, sólo repite cada 60 años o así.

Sé que usted no cree que el tiempo es único, pero me parece que resulta difícil de creer.Pero he conocido a estar equivocado.

Si usted está comenzando un montón de copias de su solicitud simultáneamente podría utilizar un temporizador con una resolución más fina.Pero entonces se corre el riesgo de un corto período de tiempo antes de que el valor se repite.

OK, así que si usted realmente piensa que usted está comenzando múltiples aplicaciones de un segundo.
A continuación, utilice un grano más fino en el temporizador.

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

Otros consejos

Esto es lo que he usado para pequeños programas de línea de comandos que se pueden ejecutar con frecuencia (varias veces por segundo): 

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

Donde está la mezcla: 

// 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 necesita un mejor generador de números aleatorios, no use libc rand. En su lugar, use algo como /dev/random o /dev/urandom directamente (lea en un int directamente de él o algo así).

El único beneficio real del libc rand es que, dada una semilla, es predecible lo que ayuda con la depuración.

En ventanas: 

srand(GetTickCount());

proporciona una semilla mejor que time() ya que está en milisegundos.

C ++ 11 random_device

Si necesita una calidad razonable, no debería usar rand () en primer lugar; debes usar la biblioteca <random>. Proporciona muchas funciones excelentes, como una variedad de motores para diferentes compensaciones de calidad / tamaño / rendimiento, reincorporación y distribuciones predefinidas para que no termines equivocándolos. Incluso puede proporcionar un fácil acceso a datos aleatorios no deterministas (por ejemplo, / dev / random), dependiendo de su implementación. 

#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 es una fuente de aleatoriedad, aquí una implementación incorporada de mersenne twister. Lo iniciamos usando random_device, que en cualquier implementación decente será un RNG no determinista, y seed_seq para combinar más de 32 bits de datos aleatorios. Por ejemplo, en libc ++ random_device accede / dev / urandom de forma predeterminada (aunque puede darle otro archivo para acceder).

A continuación, creamos una distribución tal que, dada una fuente de aleatoriedad, las llamadas repetidas a la distribución producirán una distribución uniforme de entradas de 1 a 100. Luego procedemos a usar la distribución repetidamente e imprimir los resultados.

La mejor manera es usar otro generador de números pseudoaleatorios. Mersenne Twister (y Wichmann-Hill) es mi recomendación.

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

sugiero que vea el archivo unix_random.c en el código de Mozilla. (supongo que es mozilla / security / freebl / ...) debería estar en la biblioteca freebl.

allí usa la información de llamada del sistema (como pwd, netstat ....) para generar ruido para el número aleatorio; está escrito para admitir la mayoría de las plataformas (lo que me puede dar un punto de bonificación: D).

La verdadera pregunta que debe hacerse es qué calidad de aleatoriedad necesita.

libc random es un LCG

La calidad de la aleatoriedad será baja, independientemente de la entrada que proporcione.

Si simplemente necesita asegurarse de que diferentes instancias tengan diferentes inicializaciones, puede mezclar la identificación del proceso (getpid), la identificación del hilo y un temporizador. Mezcle los resultados con xor. La entropía debería ser suficiente para la mayoría de las aplicaciones.

Ejemplo: 

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

Para una mejor calidad aleatoria, use / dev / urandom. Puede hacer que el código anterior sea portátil al usar boost :: thread y boost :: date_time.

La versión c++11 de la publicación más votada por 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 microsegundos. Esta debería ser una semilla aceptable.

Suponga que tiene una función con una firma como: 

int foo(char *p);

Una excelente fuente de entropía para una semilla aleatoria es un hash de lo siguiente:

  • Resultado completo de clock_gettime (segundos y nanosegundos) sin tirar los bits bajos: son los más valiosos.
  • El valor de p, emitido a uintptr_t.
  • La dirección de rand, emitida a srand.

Al menos el tercero, y posiblemente también el segundo, derivan entropía del ASLR del sistema, si está disponible (la dirección de pila inicial, y por lo tanto la dirección de pila actual, es algo aleatoria).

También evitaría usar <=> / <=> por completo, tanto por no tocar el estado global, como para que pueda tener más control sobre el PRNG que se usa. Pero el procedimiento anterior es una buena manera (y bastante portátil) de obtener una entropía decente sin mucho trabajo, independientemente de qué PRNG use.

Para aquellos que usan Visual Studio, aquí hay otra forma: 

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

}

Tal vez un poco exagerado pero funciona bien para intervalos rápidos. Función gettimeofday encontrada here .

Editar: tras una investigación más profunda, rand_s podría ser una buena alternativa para Visual Studio, no es solo un rand seguro (), es totalmente diferente y no utiliza la semilla de srand. Supuse que era casi idéntico a rand solo & Quot; más seguro & Quot ;.

Para usar rand_s simplemente no olvides #definir _CRT_RAND_S antes de incluir stdlib.h.

Siempre que su programa sólo se ejecuta en Linux (y su programa es un ejecutable ELF), se garantiza que el núcleo proporciona su proceso con una única semilla aleatoria en el DUENDE aux vector.El kernel te da 16 bytes aleatorios, diferente para cada proceso, que se puede obtener con getauxval(AT_RANDOM).El uso de estos para srand, utilizar solo una int de ellos, tales como:

#include <sys/auxv.h>

void initrand(void)
{
    unsigned int *seed;

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

Es posible que esto también se traduce a otros ELFOS de los sistemas basados en.No estoy seguro de lo aux valores que se implementan en otros sistemas Linux.

Incluya el encabezado en la parte superior de su programa y escriba: 

srand(time(NULL));

En su programa antes de declarar su número aleatorio. Aquí hay un ejemplo de un programa que imprime un número aleatorio entre uno y diez: 

#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;
}
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top