О генерации последовательности случайных чисел

Question

Я новичок в рандомизированных алгоритмах и изучаю сам, читая книги. Я читаю книгу «Структуры данных и анализ алгоритмов» Марка Аллена Вессиса .

Предположим, нам нужно всего лишь перевернуть монету; таким образом, мы должны генерировать 0 или 1 случайным образом. Один из способов сделать это - проверить системные часы. Часы могут записывать время как целое число, которое подсчитывает количество секунд с 1 января 1970 года (по крайней мере, в системе Unix). Тогда мы могли бы использовать младший бит . Проблема в том, что это не работает, если нужна последовательность случайных чисел. Одна секунда - долгое время, и часы могут вообще не меняться во время работы программы. Даже если время было записано в единицах микросекунды, если программа была запущена на , то последовательность чисел, которые были сгенерированы, будет далека от , так как время между вызовами генератора будет , по существу, идентичное на каждом вызов программы. Мы видим, что действительно нужна последовательность случайных чисел. Эти цифры должны отображаться независимо. Если монета переворачивается и появляются головки, следующий флип с монетами должен быть в равной степени вероятен, чтобы подняться на головы или хвостов.

Ниже приведены вопросы по фрагменту текста выше.

1. В выше фрагменте текста «для подсчета количества секунд, мы могли бы использовать младший бит», автор упоминает, что это не работает, как один второе долгое время, и часы не могут измениться на всех», мой вопрос в том, почему одна секунда - это долгое время, и часы меняются каждую секунду, и в каком контексте автор упоминает , что часы не меняются? Просьба помочь разобраться с простым примером.

2. Как автор упоминает, что даже для микросекунд мы не получаем последовательность случайных чисел?

Спасибо!

Answer 1

1. Компьютеры быстро. Я более упрощаю, но если ваша тактовая частота измеряется в ГГц, она может выполнять миллиарды операций за 1 секунду. Относительно говоря, 1 секунда - это вечность, поэтому возможно, что она не изменится.

2. Если ваша программа выполняет регулярную операцию, не гарантируется выборка часов в случайное время. Поэтому вы не получаете случайное число.

Answer 2

Не забывайте, что для компьютера одна секунда может быть «вечностью». Программы/алгоритмы часто выполняются в миллисекундах. (1000ths секунды.)

Следующий псевдокод:

for(int i = 0; i < 1000; i++) 
    n = rand(0, 1000) 

заполняет п тысячу раз со случайным числом между 0 и 1000. На типичной машине, этот сценарий выполняется почти немедленно.

В то время как вы обычно только инициализировать семена в начале:

Следующий псевдокод:

srand(time()); 
for(int i = 0; i < 1000; i++) 
    n = rand(0, 1000) 

инициализирует семя один раз, а затем выполняет код, создавая, казалось бы, случайный набор чисел. Проблема возникает тогда, когда вы выполняете код несколько раз. Допустим, что код исполняется за 3 миллисекунды. Затем код выполняется снова за 3 миллисекунды, но и в течение одной секунды. В результате получается тот же набор чисел.

Для второго пункта: автор probabaly предполагает компьютер FAST. Проблема выше ...

Answer 3

Программы, использующие случайные (или в данном случае псевдослучайные) числа, обычно нуждаются в большом количестве из них за короткое время. Это одна из причин, почему просто использование часов на самом деле не работает, потому что системные часы не обновляются так быстро, как ваш код запрашивает новые номера, поэтому вряд ли можно получить одинаковые результаты снова и снова до тех пор, пока часы изменения. Это, вероятно, более заметно в системах Unix, где обычный метод получения времени дает вам вторую точность. И даже микросекунды действительно помогают, поскольку компьютеры быстрее, чем сейчас.

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

Один из простейших типов генераторов псевдослучайных чисел, аналогичный вопрос имеет Linear Congruental Generator, хотя это не так легко увидеть с первого взгляда. Благодаря очень простой формуле

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

Answer 4

Он означает, что вы не можете контролировать, как быстро ваш компьютер или любой другой компьютер запускает ваш код.
Итак, если вы предлагаете 1 секунду для исполнения, что далеко от всего. Если вы попытаетесь запустить код самостоятельно, вы увидите, что это выполняется в миллисекундах, поэтому даже этого недостаточно, чтобы вы получили случайные числа!