Когда math.random () начинает повторяться?

У меня есть этот простой тест в nodejs, я оставил его на ночь и не смог заставить Math.random () повторить. Я понимаю, что рано или поздно значения (или даже вся последовательность) повторится, но есть ли разумные ожидания относительно того, когда это произойдет?

let v = {};
for (let i = 0;; i++) {
  let r = Math.random();
  if (r in v) break;
  v[r] = r;
}
console.log(i);

Вот это, вероятно, ответ: hackernoon.com/…

dwjohnston 26.10.2018 07:35

Одна проблема с вашим кодом заключается в том, что Math.random () засевается в текущее время, поэтому даже если / когда он в конечном итоге обнаружит дубликат, ваши результаты не будут воспроизводиться.

Ryan Leach 26.10.2018 07:36

Я имею в виду ... это является предназначено быть случайным, а не повторяющейся последовательностью, казалось бы, случайных чисел. Я бы не ожидал, что это начнет повторяться ... Если я что-то не понимаю ...

Alexander Nied 26.10.2018 07:36
rawgit.com/lordpoint/xorshift-sandbox-and-visualizer/master/‌… для живой версии по ссылке в конце статьи
Ryan Leach 26.10.2018 07:40

@AlexanderNied «не криптографически безопасные» генераторы случайных чисел редко бывают случайными. и вероятностно даже генераторы действительно случайных чисел могут повторяться для нетривиальных секций, в зависимости от диапазона полученных значений. Если бы они не были, они не были бы случайными.

Ryan Leach 26.10.2018 07:41

@RyanTheLeach, дубликат в порядке, если он не встречается чаще, чем, скажем, раз в несколько миллисекунд, поскольку я комбинирую это значение с new Date().valueOf(), чтобы сделать его более уникальным.

avo 26.10.2018 07:42

Тогда у вас проблема X Y. используйте UUID или значение часов, которое всегда увеличивается, которое сбрасывается, когда Date (). valueOf () возвращает другое значение. У UUID есть схема, включающая «идентификатор машины» - источник местного времени, который может давать вам уникальные значения в течение очень-очень долгого времени.

Ryan Leach 26.10.2018 07:44

@RyanTheLeach - теперь я понимаю. Я не внимательно изучал ваш код и думал, что вы ищете последовательные повторения, а не просто одно повторяющееся значение. Впечатляюще он сделал это за ночь без поиска дубликата, хотя к концу вечера мне интересно, сколько времени займет одна проверка, чтобы перебрать каждое значение, которое вы записали в v - возможно, он значительно замедлился ...

Alexander Nied 26.10.2018 07:45
8
8
721
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Это зависит от браузера:

https://www.ecma-international.org/ecma-262/6.0/#sec-math.random

20.2.2.27 Math.random ( ) Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Each Math.random function created for distinct code Realms must produce a distinct sequence of values from successive calls.

Требование здесь просто псевдослучайное с равномерным распределением.

Вот сообщение в блоге от V8 (Javascript Engine Chrome и NodeJs).

https://v8.dev/blog/math-random

Где они говорят, что используют xorshift128 +, который имеет максимальный период 2^128 -1.

2^128 звучит более вероятно
Mat 26.10.2018 07:48

Интересно. Можно ли предположить, что что-то вроде Math.random() + "_" + new Date().valueOf() будет генерировать уникальные строки (для определенного контекста), пока не будет остановлено?

avo 26.10.2018 07:48

Нет никакой гарантии, что вы не получите 2 числа подряд, которые являются дубликатами, дело в том, что это псевдослучайно. Если вам нужна уникальность, избегайте случайных. Если вы по-прежнему хотите использовать случайное число как часть идентификатора, используйте хорошо протестированную схему, например UUID.

Ryan Leach 26.10.2018 07:50

См. stackoverflow.com/questions/23164474/… Использование UUID ясно, недвусмысленно и хорошо задокументировано в отношении вероятности их столкновения. катание самостоятельно потребует значительных затрат на обслуживание.

Ryan Leach 26.10.2018 07:53

Похожее (на другом сайте): Можно ли полагаться на то, что случайные целые числа уникальны?

Также очень похожий: Сколько двойных чисел между 0,0 и 1,0?

Математически существует бесконечное количество действительных чисел от 0 до 1. Однако Math.Random может генерировать только конечное количество возможных значений (поскольку компьютеры имеют только конечное количество битов для представления чисел). Допустим, есть возможные значения N, которые он может генерировать. Тогда, с помощью Принцип голубятни, есть 100% шанс получить хотя бы одно повторяющееся значение, если вы сгенерируете точно значения N + 1.

На этом этапе Парадокс дня рождения демонстрирует, что вы должны начать видеть дубликаты на удивление быстро. Согласно этому «парадоксу» (который не является настоящим парадоксом, а просто противоречит здравому смыслу), учитывая, что в комнате всего 23 человека, вероятность того, что двое из них имеют одинаковый день рождения, превышает 50%.

Возвращаясь к нашему примеру, эмпирическое правило для расчета этого (см. Связанную статью в Википедии) предполагает, что Math.Random достигает 50% вероятности дублирования, если вы генерируете приблизительно числа sqrt(N).

Из связанного вопроса о переполнении стека, если мы предположим, что существует 7 036 874 417 766 чисел между 0 и 1, как говорится в принятом ответе (и, пожалуйста, прочитайте связанный вопрос для более подробного объяснения того, сколько существует на самом деле), тогда sqrt (7036874417766) будет чуть более 2,652 миллиона, что на самом деле не так уж и много. Если вы генерируете 10 000 случайных чисел в секунду, вы достигнете 50% вероятности примерно за 737 часов, что составляет чуть менее 31 дня. Менее удачно, что даже при 10 000 в секунду потребуется приблизительно 195 468 часов (что составляет приблизительно 22,3 года), чтобы достичь 100% вероятности.

Некоторые другие ответы дают гораздо более высокие цифры количества цифр, так что выбирайте сами.

@avo Спасибо, рад, что смог помочь.

EJoshuaS - Reinstate Monica 21.11.2018 22:53

Другие вопросы по теме