Требуется ли прогрев std :: mt19937?
Я читал, что многим генераторам псевдослучайных чисел требуется много выборок, чтобы их «подогреть». Это тот случай, когда используется std :: random_device для заполнения std :: mt19937, или мы можем ожидать, что он готов после сборки? Код в вопросе:
#include <random>
std::random_device rd;
std::mt19937 gen(rd());
Решение
Mersenne Twister — это pRNG на основе сдвигового регистра (генератор псевдослучайных чисел), и поэтому он подвержен ошибочным начальным значениям с длинными прогонами 0 или 1, которые приводят к относительно предсказуемым результатам, пока внутреннее состояние не будет достаточно перемешано.
Однако конструктор, который принимает одно значение, использует сложную функцию для этого начального значения, которая предназначена для минимизации вероятности создания таких «плохих» состояний. Есть второй способ инициализации mt19937 где вы непосредственно устанавливаете внутреннее состояние через объект, соответствующий концепции SeedSequence. Это второй метод инициализации, когда вам может понадобиться выбрать «хорошее» состояние или выполнить разминку.
Стандарт включает в себя объект, соответствующий концепции SeedSequence, называемый seed_seq, seed_seq принимает произвольное количество входных начальных значений, а затем выполняет определенные операции над этими значениями, чтобы создать последовательность различных значений, подходящих для непосредственной установки внутреннего состояния pRNG.
Вот пример загрузки начальной последовательности с достаточным количеством случайных данных, чтобы заполнить весь std::mt19937 государство:
std::array<int, 624> seed_data;
std::random_device r;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
std::mt19937 eng(seq);
Это гарантирует, что все состояние рандомизировано. Кроме того, каждый механизм определяет, сколько данных он читает из seed_sequence, поэтому вы можете прочитать документы, чтобы найти эту информацию для любого используемого вами механизма.
Хотя здесь я загружаю seed_seq полностью из std::random_device, seed_seq определяется так, что только несколько чисел, которые не являются особенно случайными, должны хорошо работать. Например:
std::seed_seq seq{1, 2, 3, 4, 5};
std::mt19937 eng(seq);
В комментариях ниже Cubbi указывает, что seed_seq работает, выполняя последовательность разминки для вас.
Вот что должно быть вашим «по умолчанию» для посева:
std::random_device r;
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
std::mt19937 rng(seed);
Другие решения
Я полагаю, что существуют ситуации, когда МТ можно засевать «плохо», что приводит к неоптимальным последовательностям. Если я правильно помню, засев со всеми нулями является одним из таких случаев. Я бы порекомендовал вам попробовать использовать генераторы WELL, если это серьезная проблема для вас. Я считаю, что они более гибкие — качество семян не так важно. (Возможно, чтобы ответить на ваш вопрос более прямо: возможно, более эффективно сосредоточиться на посеве хорошо, а не на посеве плохо, а затем попытаться сгенерировать кучу образцов, чтобы привести генератор в оптимальное состояние.)
Если вы начнете с одного 32-битного значения, все, что вы когда-либо получите, это одна из тех же 2 ^ 32 траекторий в пространстве состояний. Если вы используете PRNG с государственными KiB, то вам, вероятно, следует заполнить все это. Как описано в комментариях к ответу @ bames63, используя std::seed_seq вероятно, не очень хорошая идея, если вы хотите инициализировать все состояние случайными числами. К сожалению, std::random_device не соответствует SeedSequence концепции, но вы можете написать обертку, которая делает:
#include <random>
#include <iostream>
#include <algorithm>
#include <functional>
class random_device_wrapper {
std::random_device *m_dev;
public:
using result_type = std::random_device::result_type;
explicit random_device_wrapper(std::random_device &dev) : m_dev(&dev) {}
template <typename RandomAccessIterator>
void generate(RandomAccessIterator first, RandomAccessIterator last) {
std::generate(first, last, std::ref(*m_dev));
}
};
int main() {
auto rd = std::random_device{};
auto seedseq = random_device_wrapper{rd};
auto mt = std::mt19937{seedseq};
for (auto i = 100; i; --i)
std::cout << mt() << std::endl;
}
Это работает по крайней мере, пока вы не включите концепции. В зависимости от того, знает ли ваш компилятор о SeedSequence как C ++ 20 concept, это может не сработать, потому что мы поставляем только недостающие generate() метод, больше ничего. Тем не менее, при программировании на основе утиных шаблонов этого кода достаточно, потому что PRNG не хранит начальный объект последовательности.