Random.Next () - найти Nth .Next ()

Question

Учитывая последовательно посеянный случайный случай:

Random r = new Random(0);

Вызов r.Next() последовательно производит одну и ту же серию; так есть ли способ быстро обнаружить N -ое значение в этом ряду, не вызывая r.Next() N раз?

Мой сценарий - это огромный массив значений, созданных с помощью r.Next(). Приложение иногда читает значение из массива по произвольным индексам. Я хотел бы оптимизировать использование памяти за счет исключения массива и создания значений по требованию. Но грубое принуждение r.Next() 5 миллионов раз для симуляции 5-миллионного индекса массива обходится дороже, чем хранение массива. Можно ли сократить путь к значению Nth .Next () без / с меньшим циклом?

Answer 1

Я не знаю деталей PRNG, используемых в BCL, но я предполагаю, что вам будет чрезвычайно трудно / невозможно найти хорошее решение в закрытой форме для N -гостоимость серии.

Как насчет этого обходного пути:

Сделайте seed для генератора случайных чисел желаемого индекса, а затем выберите первое сгенерированное число.Это в равной степени «детерминистично» и дает вам широкий диапазон для игры в O (1) пространстве.

static int GetRandomNumber(int index)
{
    return new Random(index).Next();
} 

Answer 2

Теоретически, если вы знаете точный алгоритм и начальное состояние, вы сможете дублировать ряд, но конечный результат будет идентичен вызову r.next ().

В зависимости от того, как 'хорошо, вам нужны ваши случайные числа, чтобы вы могли подумать о создании собственного PRNG на основе линейного конгруэнтного генератора , для которого относительно легко / быстро генерировать числа.Если вы можете жить с «плохим» PRNG, вероятно, есть другие алгоритмы, которые лучше использовать для ваших целей.Будет ли это быстрее / лучше, чем просто хранить большой массив чисел из r.next () - это другой вопрос.

Answer 3

Нет, я не верю, что есть. Для некоторых алгоритмов ГСЧ (таких как линейные конгруэнтные генераторы) в принципе возможно получить n-е значение без итерации по n шагам, но класс Random не обеспечивает способ сделать это.

Я не уверен, что алгоритм, который он использует, делает это возможным в принципе - это вариант (детали не раскрыты в документации) субтрактивного ГСЧ Кнута, и кажется, что оригинальный ГСЧ Кнута должен быть эквивалентен некоторому виду полиномиально-арифметическая вещь, которая позволила бы получить доступ к n-му значению, но (1) я на самом деле не проверял это и (2) любые изменения, сделанные Microsoft, могли бы сломать это.

Если у вас достаточно хорошая «скремблирующая» функция f, то вы можете использовать f (0), f (1), f (2), ... в качестве последовательности случайных чисел вместо f (0), f (f (0)), f (f (f (0))) и т. д. (последний примерно , что делает большинство ГСЧ), а затем, конечно, тривиально запустить последовательность в любой точке Вы, пожалуйста. Но вам нужно будет выбрать хороший f, и он, вероятно, будет медленнее, чем стандартный RNG.

Answer 4

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

Random rnd = new Random(0);
Dictionary<int,int> randomNumbers = new Dictionary<int,int>();
int getRandomNumber(int index)
{
    if (!randomNumbers.ContainsKey(index))
        randomNumbers[index] = rnd.Next();
    return randomNumbers[index];
}