Рекомендуемый способ инициализации srand? - PullRequest
Новая
       47

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

60 голосов
/ 27 ноября 2008

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

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

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

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

Спасибо!

EDIT

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

Ответы [ 14 ]

62 голосов
/ 27 ноября 2008

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

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;
}
52 голосов
/ 27 ноября 2008

Лучший ответ - использовать материал 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.
 }
15 голосов
/ 27 ноября 2008

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

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

8 голосов
/ 22 октября 2012

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

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

8 голосов
/ 27 ноября 2008

На окнах: 

srand(GetTickCount());

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

7 голосов
/ 27 ноября 2008

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

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

7 голосов
/ 27 ноября 2008

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

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

6 голосов
/ 27 ноября 2008

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

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.

3 голосов
/ 22 марта 2015

Джонатан Райт 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);
2 голосов
/ 27 ноября 2008 
#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 в микросекундах. Это должно быть приемлемое семя.

Страница:
...