Алгоритм random_shuffle - идентичны ли результаты без функции генератора случайных чисел?

Question

Если функция генератора случайных чисел не предоставлена ​​алгоритму random_shuffle в стандартной библиотеке, будут ли последовательные запуски программы генерировать одну и ту же случайную последовательность при наличии одинаковых данных?

Например, если

std::random_shuffle(filenames.begin(), filenames.end());

выполняется для одного и того же списка имен файлов из каталога при последовательных запусках программы. Произошла ли случайная последовательность так же, как в предыдущем прогоне?

Answer 1

Если вы используете тот же генератор случайных чисел, с тем же начальным и тем же начальным последовательность, результаты будут одинаковыми. В конце концов, компьютер - это детерминированный в своем поведении (по модулю потоков и некоторые другие шансы и конец).

Если вы не укажете генератор, генератор по умолчанию будет реализация определена. Я думаю, что большинство реализаций используют std::rand() (что может вызвать проблемы, особенно когда число элементы в последовательности больше, чем RAND_MAX). Я бы посоветовал получить генератор с известным качеством и использовать его.

Если вы неправильно заполнили используемый генератор (другой причина не использовать значение по умолчанию, так как от того, как вы его посеете, будет зависеть реализации), тогда вы получите то, что вы получите. В случае std::rand(), по умолчанию всегда используется одно и то же начальное число. Как вы семя зависит от используемого генератора. То, что вы используете для посева, должно быть разным от одного забега к другому; для многих приложений time(NULL) достаточно; на платформе Unix я бы рекомендовал читать сколько угодно байтов это берет от /dev/random. В противном случае хеширование другой информации (IP адрес машины, идентификатор процесса и т. д.) также может улучшить ситуацию --- это означает, что два пользователя запускают программу в одно и то же все равно получит разные последовательности. (Но это действительно только актуально если вы работаете в сетевом окружении.)

Answer 2

25.2.11 просто говорит, что элементы перемешаны с равномерным распределением.Он не дает никаких гарантий относительно того, какой ГСЧ используется за кулисами (если только вы не пропустите его), поэтому вы не можете полагаться на такое поведение.

Для того, чтобы гарантировать тот же результат случайного воспроизведения, который вам потребуетсяпредоставить свой собственный ГСЧ, обеспечивающий эти гарантии, но я подозреваю, что даже тогда, если вы обновите стандартную библиотеку, сам алгоритм random_shuffle может изменить эффекты.

Answer 3

Вы можете выдавать идентичный результат при каждом запуске программы.Вы можете добавить пользовательский генератор случайных чисел (который можно посеять из внешнего источника) в качестве дополнительного аргумента для std::random_shuffle, если это является проблемой.Функция будет третьим аргументом.Некоторые люди рекомендуют звонить srand(unsigned(time(NULL))); до random_shuffle, но результаты часто определяются реализацией (а ненадежно ).