Рекомендуемый способ инициализации srand?
Мне нужен "хороший" способ инициализации генератора псевдослучайных чисел в C++. Я нашел статью, в которой говорится:
Чтобы генерировать случайные числа, srand обычно инициализируется некоторым отличительным значением, например, связанным со временем выполнения. Например, значение, возвращаемое функцией time (объявленной в заголовке ctime), каждую секунду отличается, что достаточно для большинства случайных задач.
Unixtime не является достаточно отличительным для моего приложения. Какой лучший способ инициализировать это? Бонусные баллы, если он переносимый, но код будет в основном выполняться на хостах Linux.
Я думал о выполнении математики pid / unixtime, чтобы получить int, или, возможно, чтения данных из /dev/urandom,
Спасибо!
РЕДАКТИРОВАТЬ
Да, я на самом деле запускаю свое приложение несколько раз в секунду, и я столкнулся с коллизиями.
14 ответов
Наилучший ответ - использовать 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() так как в миллисекундах.
C++11random_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 является источником случайности, здесь встроенная реализация мерсенна твистера. Мы запустили его, используя random_device, который в любой достойной реализации будет недетерминированным GNG и seed_seq для объединения более 32-битных случайных данных. Например, в libC++ random_device по умолчанию обращается к /dev/urandom (хотя вы можете вместо этого дать ему другой файл для доступа).
Затем мы создаем распределение таким образом, чтобы при наличии источника случайности повторные обращения к распределению приводили к равномерному распределению целых чисел от 1 до 100. Затем мы переходим к повторному использованию распределения и печати результатов.
Лучший способ - использовать другой генератор псевдослучайных чисел. Твистер Мерсенна (и Вихманн-Хилл) - моя рекомендация.
Я предлагаю вам увидеть файл unix_random.c в коде Mozilla. (думаю, это mozilla / security / freebl /...) оно должно быть в библиотеке freebl.
там он использует информацию о системных вызовах (например, pwd, netstat....) для генерации шума для случайного числа, он написан для поддержки большинства платформ (что может принести мне бонусный балл:D).
Реальный вопрос, который вы должны задать себе - какое качество случайности вам нужно.
libc random - это LCG
Качество случайности будет низким независимо от того, что вы предоставляете.
Если вам просто нужно убедиться, что разные экземпляры будут иметь разные инициализации, вы можете смешать идентификатор процесса (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);
Пока ваша программа работает только в 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.
#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 в микросекундах. Это должно быть приемлемым семенем.
Предполагая, что случайности srand() + rand() достаточно для ваших целей, хитрость заключается в выборе лучшего начального числа для srand. time(NULL) - хорошая отправная точка, но вы столкнетесь с проблемами, если запустите более одного экземпляра программы в течение одной секунды. Добавление pid (идентификатора процесса) - это улучшение, так как разные экземпляры будут получать разные pid. Я бы умножил pid на коэффициент, чтобы расширить их.
Но предположим, что вы используете это для какого-то встроенного устройства, и у вас есть несколько в одной сети. Если все они запитаны одновременно, и вы автоматически запускаете несколько экземпляров своей программы во время загрузки, они все равно могут получать одинаковое время и pid, и все устройства будут генерировать одну и ту же последовательность "случайных" чисел. В этом случае вы можете добавить уникальный идентификатор каждого устройства (например, серийный номер процессора).
Предлагаемая инициализация будет следующей:
srand(time(NULL) + 1000 * getpid() + (uint) getCpuSerialNumber());
На машине с Linux (по крайней мере, на Raspberry Pi, где я это тестировал) вы можете реализовать следующую функцию для получения серийного номера процессора:
// Gets the CPU Serial Number asa 64 bit unsigned int. Returns 0 if not found.
uint64_t getCpuSerialNumber() {
FILE *f = fopen("/proc/cpuinfo", "r");
if (!f) {
return 0;
}
char line[256];
uint64_t serial = 0;
while (fgets(line, 256, f)) {
if (strncmp(line, "Serial", 6) == 0) {
serial = strtoull(strchr(line, ':') + 2, NULL, 16);
}
}
fclose(f);
return serial;
}
Для тех, кто использует 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_s, просто не забудьте #define _CRT_RAND_S до включения stdlib.h.
Предположим, у вас есть функция с такой подписью:
int foo(char *p);
Отличным источником энтропии для случайного семени является хеш-код следующего:
- Полный результат
clock_gettime(секунды и наносекунды) без отбрасывания младших битов - они наиболее ценные. - Значение
pв роляхuintptr_t, - Адрес
pв роляхuintptr_t,
По меньшей мере, третий и, возможно, также второй выводят энтропию из ASLR системы, если он доступен (начальный адрес стека и, следовательно, текущий адрес стека несколько случайный).
Я бы также избегал использования rand/srand целиком и полностью, чтобы не касаться глобального состояния, и поэтому вы можете лучше контролировать используемый PRNG. Но описанная выше процедура является хорошим (и достаточно переносимым) способом получить некоторую приличную энтропию без особого труда, независимо от того, какой PRNG вы используете.
Включите заголовок вверху вашей программы и напишите:
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;
}