Рекомендуемый способ инициализации srand?

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

  •  11-07-2019
  •  | 
  •  

Вопрос

Мне нужен "хороший" способ инициализации генератора псевдослучайных чисел на C ++.Я нашел статья это гласит:

Чтобы генерировать случайные числа, srand обычно инициализируется некоторым отличительным значением, подобным тем, которые связаны со временем выполнения.Например, значение, возвращаемое функцией time (объявленное в заголовке ctime), каждую секунду отличается, что достаточно характерно для большинства потребностей случайного выполнения.

Unixtime недостаточно отличителен для моего приложения.Какой лучший способ инициализировать это?Бонусные баллы, если он переносим, но код в основном будет работать на хостах Linux.

Я подумывал о том, чтобы выполнить некоторую математику pid / unixtime для получения int или, возможно, считывания данных из /dev/urandom.

Спасибо!

Редактировать

Да, я действительно запускаю свое приложение несколько раз в секунду и сталкиваюсь с конфликтами.

Это было полезно?

Решение

Лучший ответ — использовать функцию случайных чисел Boost.Или, если у вас есть доступ к C++11, используйте <random> заголовок.

Но если мы говорим о rand() и srand()
Лучший способ - просто использовать time():

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

    ...
}

Обязательно делайте это в начале вашей программы, а не каждый раз при вызове rand()!

Каждый раз при запуске time() возвращает уникальное значение (если только вы не запускаете приложение несколько раз в секунду).В 32-битных системах это будет повторяться каждые 60 лет или около того.

Я знаю, вы не думаете, что время достаточно уникально, но мне трудно в это поверить.Но я, как известно, ошибался.

Если вы одновременно запускаете много копий вашего приложения, вы можете использовать таймер с более высоким разрешением.Но тогда вы рискуете получить более короткий период времени, прежде чем значение повторится.

Хорошо, если вы действительно думаете, что запускаете несколько приложений в секунду.
Затем используйте более мелкое зерно на таймере.

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

Другие советы

Это то, что я использовал для небольших программ командной строки, которые можно запускать часто (несколько раз в секунду):

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

Где находится смесь:

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

если вам нужен лучший генератор случайных чисел, не используйте libc rand.Вместо этого просто используйте что-то вроде /dev/random или /dev/urandom напрямую (читайте в int прямо из него или что-то в этом роде).

Единственное реальное преимущество libc rand заключается в том, что, учитывая начальное значение, оно предсказуемо, что помогает при отладке.

На окнах:

srand(GetTickCount());

дает лучшее семя, чем time() так как это в миллисекундах.

С++11 random_device

Если вам нужно приемлемое качество, вам вообще не следует использовать rand();вам следует использовать <random> библиотека.Он предоставляет множество замечательных функций, таких как множество движков для различных компромиссов между качеством, размером и производительностью, повторный вход и предопределенные дистрибутивы, поэтому вы не ошибетесь.Он может даже обеспечить легкий доступ к недетерминированным случайным данным (например, /dev/random), в зависимости от вашей реализации.

#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 является источником случайности, здесь встроенная реализация твистера Мерсенна.Мы заполняем его, используя случайный_устройство, которое в любой приличной реализации будет недетерманистическим ГСЧ, и семян_seq для объединения более чем 32-битных случайных данных.Например, в libc++ random_device по умолчанию обращается к /dev/urandom (хотя вместо этого вы можете предоставить ему другой файл для доступа).

Затем мы создаем такое распределение, что, учитывая источник случайности, повторные вызовы распределения будут давать равномерное распределение целых чисел от 1 до 100.Затем приступаем к многократному использованию дистрибутива и печати результатов.

Лучший способ — использовать другой генератор псевдослучайных чисел.Твистер Мерсенна (и Вихманн-Хилл) — моя рекомендация.

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

Я предлагаю вам увидеть файл unix_random.c в коде Mozilla.(думаю, это mozilla/security/freebl/...) он должен быть в библиотеке freebl.

там он использует информацию о системном вызове (например, pwd, netstat....) для генерации шума для случайного числа; он написан для поддержки большинства платформ (что может принести мне бонусное очко :D).

Настоящий вопрос, который вы должны задать себе, заключается в том, какое качество случайности вам нужно.

libc случайный - это ЛКГ

Независимо от того, какие данные вы предоставите srand, качество случайности будет низким.

Если вам просто нужно убедиться, что разные экземпляры будут иметь разные инициализации, вы можете смешать идентификатор процесса (getpid), идентификатор потока и таймер.Смешайте результаты с помощью xor.Энтропии должно быть достаточно для большинства приложений.

Пример :

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

Для лучшего случайного качества используйте /dev/urandom.Вы можете сделать приведенный выше код переносимым, используя boost::thread и boost::date_time.

А c++11 версия поста Джонатана Райта, получившего наибольшее количество голосов:

#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 измеряется в микросекундах.Это должно быть приемлемое семя.

Предположим, у вас есть функция с сигнатурой типа:

int foo(char *p);

Отличным источником энтропии для случайного начального числа является хеш следующего:

  • Полный результат clock_gettime (секунды и наносекунды), не выбрасывая младшие биты — они наиболее ценны.
  • Значение p, приведите к uintptr_t.
  • Адрес p, приведите к uintptr_t.

По крайней мере, третий, а возможно и второй, получают энтропию из системного ASLR, если он доступен (начальный адрес стека и, следовательно, текущий адрес стека в некоторой степени случайны).

Я бы также воздержался от использования rand/srand полностью, как для того, чтобы не затрагивать глобальное состояние, так и для того, чтобы вы могли лучше контролировать используемый ГПСЧ.Но описанная выше процедура — хороший (и достаточно переносимый) способ получить приличную энтропию без особых усилий, независимо от того, какой ГПСЧ вы используете.

Для тех, кто использует Visual Studio, есть еще один способ:

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

}

Возможно, это немного излишество, но хорошо работает для коротких интервалов.Найдена функция gettimeofday здесь.

Редактировать:при дальнейшем исследовании rand_s может стать хорошей альтернативой для Visual Studio, это не просто безопасный метод rand(), он совершенно другой и не использует начальное значение из srand.Я предполагал, что это почти идентично rand, только «более безопасно».

Чтобы использовать rand_s, не забудьте #define _CRT_RAND_S перед включением stdlib.h.

Пока ваша программа работает только в Linux (и ваша программа является исполняемым файлом ELF), вам гарантируется, что ядро предоставляет вашему процессу уникальное случайное начальное значение во вспомогательном векторе ELF.Ядро выдает вам 16 случайных байт, разных для каждого процесса, которые вы можете получить с помощью getauxval(AT_RANDOM).Использовать их для srand, используйте только int из них, как таковых:

#include <sys/auxv.h>

void initrand(void)
{
    unsigned int *seed;

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

Вполне возможно, что это также распространяется на другие системы, основанные на ELF.Я не уверен, какие значения aux реализованы в системах, отличных от Linux.

Включите заголовок в начало вашей программы и напишите:

srand(time(NULL));

В вашей программе перед тем, как объявить свое случайное число.Вот пример программы, которая печатает случайное число от одного до десяти:

#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;
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top