Заполнение RNG Java

Мой вопрос касается Java RNG; используйте следующий код:

for (int s = 0; s < 600; s++) {
   Random r = new Random(s);
   System.out.println(r.nextDouble());
   System.out.println(r.nextDouble() + "\n-----");
}

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

Второй сгенерированный дубль на самом деле выглядит так, как будто он действительно случайный, можно ли так предположить? Можно ли сначала сгенерировать неиспользуемое случайное число, а после этого начать использовать его по той причине, по которой оно было создано?

заранее спасибо

РЕДАКТИРОВАТЬ:

Позвольте мне уточнить:

int possibleRoutes = 7;
void handlePacket(Packet p) {

    int chosenRoute = p.hash % possibleRoutes;
    // ...Other code...

}

vs.

int possibleRoutes = 7;
void handlePacket(Packet p) {

    Random r = new Random(p.hash);
    int chosenRoute = r.nextInt() % possibleRoutes;
    // ...Other code...
}

}

vs.

int possibleRoutes = 7;
void handlePacket(Packet p) {

    Random r = new Random(p.hash);
    r.nextInt();
    int chosenRoute = r.nextInt() % possibleRoutes;
    // ...Other code...

}

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


person Is Niska    schedule 15.01.2017    source источник
comment
Я не понимаю этого использования. У PRNG есть состояние. Просто создайте один (снаружи; если вам нужно, в зависимости от времени) и семплируйте внутри цикла. Второй вызов будет основан на другом состоянии, чем первый. Пересев не требуется. (повторное заполнение цикла - плохая практика почти во всех случаях использования). Отбрасывание RNG-чисел также выполняется только в некоторых очень сложных настройках, и здесь это не подход.   -  person sascha    schedule 15.01.2017
comment
На всякий случай: расскажите нам, зачем вам нужен новый PRNG-объект в каждом цикле (если вы этого хотите) или вам нужны только новые числа при каждом вызове программы.   -  person sascha    schedule 15.01.2017
comment
Как вы думаете, ПОЧЕМУ вам нужен новый генератор случайных чисел на каждой итерации? Подобные утверждения часто отражают глубокое непонимание PRNG.   -  person pjs    schedule 15.01.2017
comment
Я добавил псевдокод реального случая к исходному вопросу   -  person Is Niska    schedule 16.01.2017
comment
Второй пример выглядит хорошо для меня (при условии некоторого качества PRNG). Третий — просто выбрасывать вещи (потому что вы думаете, что первый — плохой). Придерживайтесь 2. Предупреждение: 2 и 3 подходят только в том случае, если возвращаемые хэши удовлетворяют предположениям ГПСЧ о начальном значении. (пример, не связанный с java: PRNG требует 32-битного начального числа, ваш хэш 16-битный = проблема) Также должна быть возможность повторно заполнить базовый PRNG без создания нового объекта (лучше!). Задача-предположение: два одинаковых пакета (по хешу) должны идти по одному маршруту; но выбор маршрута должен быть случайным. Вот это я понимаю.   -  person sascha    schedule 16.01.2017
comment
@sascha А, повторная раздача может быть быстрее, да. Второй не подходит, потому что nextInt() почти всегда будет одним из результатов из-за линейного отношения, о котором говорилось в другом разделе комментариев (сначала он выдаст много 0000000, прежде чем достигнет линейного порога для далее и далее производить партию 1111111 и т.д.).   -  person Is Niska    schedule 16.01.2017
comment
Вы не должны наблюдать что-то подобное во втором примере (это драматично/легко). Похоже, какая-то другая проблема в вашем коде. Так что проверяйте хеширование. И если вы действительно думаете, что здесь проблема с LCG, просто используйте что-то другое. Использование остается прежним.   -  person sascha    schedule 16.01.2017
comment
По сути, PRNG пересчитывает исходный последовательный хэш. Если вы запустите исходный пример кода, первое число, которое он выводит, будет очень последовательно коррелировано.   -  person Is Niska    schedule 16.01.2017
comment
И более простой/альтернативный подход: случайным образом перетасовывать маршруты (через функцию lib). И просто используйте хэш для индексации этого перетасованного контейнера.   -  person sascha    schedule 16.01.2017
comment
Если ваш код так плохо работает, похоже, что проблема в хеше. Ну, вы можете показать некоторые полные результаты. Проблемы, упомянутые pjs, должны полностью уменьшиться с учетом хэша, поскольку полное заполнение/состояние = все необходимые биты, хотя теперь возникает вопрос, нужны ли PRNG (см. Подход с перемешиванием)! . На самом деле это очень важно Как вы хешируете? Сначала проанализируйте это!   -  person sascha    schedule 16.01.2017
comment
Вы правы, оглядываясь назад, хэш - настоящая проблема; способен ли PRNG преобразовывать последовательный хэш в хеш с однородным отображением? должен был быть вопрос. Перетасовка маршрутов и сохранение этого состояния слишком много (~ 1-10 млн пар src-dst, например, 100 маршрутов, приведут к ~ 1-10 ГБ основной памяти). Спасибо за попытку ответить и обсудить со мной   -  person Is Niska    schedule 16.01.2017
comment
Еще немного непонятно. Почему пары src-dst. Похоже, вы индексируете маршруты. Вероятно, существует менее 2 ^ 32 маршрутов, или ваш код выше не имеет особого смысла. Но хорошо... вы знаете, что опасности известны. Если ваши маршруты индексируются (например, выберите один из [0, 100000), одним из лучших подходов будет использование очень хорошего хэша (не встроенного простого, который может делать что-то вроде объединения целых хэшей для массивов), например SHA- 256 (да, вы потеряете производительность) и используйте его для индексации. Поскольку вы получите 256 бит, вы можете усечь (должно быть в порядке) или использовать что-то более сильное для сопоставления с вашими показателями.   -  person sascha    schedule 16.01.2017
comment
Дополнительное примечание: при наличии хорошо работающего хэша, который затем сопоставляется с вашим диапазоном индексов маршрутов, перетасовка также не требуется, но будет минимально более устойчивой к некоторым потенциальным дефектам.   -  person sascha    schedule 16.01.2017
comment
Предположим, что у вас есть два узла, пакет прибывает на узел A, у A есть K соседей, которым он может его отправить (которые находятся на кратчайшем пути к месту назначения), он использует package.hash % K для выбора пути, а затем передает его узлу B (тоже K соседям), который также делает package.hash % K для определения пути. Это означает, что они всегда будут выбирать один и тот же индекс, если у них есть одинаковое количество K соседей для выбора. Таким образом, им нужно будет локально адаптировать package.hash таким образом, чтобы этой причинно-следственной связи больше не существовало, чтобы пакеты могли иметь K * K возможностей для перехода на Vs. только К.   -  person Is Niska    schedule 16.01.2017
comment
Непростая задача, ну... я думаю, что пока достаточно объяснила (и надеюсь, вы сможете решить свою проблему). Еще одно замечание: ваше объяснение звучит так, будто вам нужно принимать множество случайных решений, основываясь на одном стартовом семени. Таким образом, основной подход таков: возьмите пакет; хешируйте его чем-нибудь хорошим (сначала нужно создать строку/массив байтов, а затем, например, использовать SHA-256). Подготовьте хэш для заполнения вашего PRNG (вам нужно 48 бит; у вас есть 256; усечение легко, попробуйте сначала; другие подходы лучше) и используйте этот одноразовый PRNG для всех ваших решений на основе соседей (без повторного хэширования/ пересев).   -  person sascha    schedule 16.01.2017
comment
Спасибо за дискуссию, мне приятно   -  person Is Niska    schedule 16.01.2017


Ответы (3)


почему вы даете специальный номер в качестве семени? просто оставьте его пустым, чтобы конструктор Random выбрал для вас начальное число.

for (int s = 0; s < 600; s++) {
     Random r = new Random();
     System.out.println(r.nextDouble());
     System.out.println(r.nextDouble() + "\n-----");
   }

см. Роль начального числа в генерации случайных чисел

person sLy    schedule 15.01.2017
comment
Он должен снова быть детерминистически работоспособным - person Is Niska; 16.01.2017

Вызовите конструктор по умолчанию, который использует nanoTime в качестве начального значения. Таким образом, вам не нужно будет генерировать новое семя для создания вашего объекта на каждой итерации.

//loop through number of numbers needed
for(int i = 0; i < 100; i +)
    //Calls default constructor
    Random r = new Random();
    System.out.println(r.nextDouble()*.5);
person Ryan    schedule 15.01.2017
comment
Так почему бы не использовать Random-объект повторно? (= создание вне цикла). Это выглядит очень неэффективно (особенно для MersenneTwister или всего, что использует огромное состояние). - person sascha; 15.01.2017
comment
Насколько я понимаю, этот пользователь хочет выполнить повторное заполнение для каждого сгенерированного числа (в чем я согласен с вами, я бы никогда не выполнял повторное заполнение внутри цикла или даже так часто). Я исхожу из этой цитаты. Мне каждый раз требуется новый генератор случайных чисел в моем актуальный проект - person Ryan; 15.01.2017
comment
Справедливо. Я не знаю, упускает ли он какие-то основы или есть недопонимание. - person sascha; 15.01.2017
comment
@sascha Реализация Java по умолчанию Random - это не Mersenne Twister, это 48-битный линейный конгруэнтный генератор. - person pjs; 15.01.2017
comment
@pjs Интересно. Спасибо за совет! - person sascha; 15.01.2017
comment
@sascha Вероятно, поэтому OP спрашивает об использовании второго вывода, первые результаты последовательно засеянных значений LCG будут линейно связаны, за исключением небольшого количества циклов из-за операции по модулю. - person pjs; 15.01.2017
comment
@pjs Это звучит как комбинация ужасной инициализации, основанной на семени и внутреннем пространстве состояний. Но я помню, что у MT также были некоторые проблемы с раздачей/состоянием. То есть вы говорите, что LCG-поведение в этом отношении настолько плохое, что оно прямо наблюдается в таком простом коде? (например, всегда растет в 2 раза...) Это интересно. Всегда интересно наблюдать за PRNG по умолчанию в разных средах программирования и проблемами с их изменением, чтобы они были более современными (например, прилипание numpy к MT, что уже не так хорошо). К счастью, при необходимости всегда можно использовать внешние библиотеки. - person sascha; 15.01.2017
comment
@sascha Так что, даже если первоначальные результаты связаны линейно, любые последующие результаты будут псевдослучайного качества? - person Is Niska; 16.01.2017
comment
@IsNiska Сначала поработайте над своим пониманием основного использования PRNG, прежде чем делать что-либо еще. Как сказал я и другие: представленное использование выглядит очень неправильно! Следующий вопрос сложный. Анализировать случайность PRNG сложно. Похоже, что java использует один из самых старых (и, возможно, лучше всего проанализированных) методов с некоторыми недостатками в отношении случайности. Хотя современные ГПСЧ лучше, трудно рассуждать о том, являются ли эти недостатки проблемой для вас. В общем: да, рандом java разработан, чтобы давать вам случайные числа. Поскольку я никогда не использую LCG, я не могу оценить проблему здесь. - person sascha; 16.01.2017
comment
@sascha В этом случае мне действительно нужна функция, которая хэширует входные данные с линейной подачей таким образом, чтобы результат был однородным среди возможностей - я использую PRNG, поскольку это казалось довольно логичным для выполнения требования. - person Is Niska; 16.01.2017
comment
@IsNiska Ваша задача все еще не ясна. Если речь идет о пакетных хэшах, использование семени — правильный путь. Если пакеты прибывают в одном и том же порядке (и два пакета с одинаковым хешем могут идти по разным маршрутам), повторное заполнение не требуется. Помните, что есть состояние. - person sascha; 16.01.2017
comment
@sascha Да, но два пакета с равным хешем не могут идти по разным маршрутам из-за механизмов управления перегрузкой, которые полагаются на один маршрут через сеть. - person Is Niska; 16.01.2017
comment
@IsNiska Тогда, может быть, хоть раз проясните это. Насколько сложно точно описать настройку (в исходном посте!!!)? Не заставляйте нас гадать. - person sascha; 16.01.2017

Альтернативой является использование основного случайного числа для заполнения всех дополнительных случайных чисел в цикле:

Random masterRand = new Random();
for (int s = 0; s < 600; s++) {
  Random r = new Random(masterRand.nextLong());
  System.out.println(r.nextDouble());
  System.out.println(r.nextDouble() + "\n-----");
}
person rossum    schedule 15.01.2017
comment
Почему это лучше, чем использовать один Random вне цикла? Оба полностью предсказуемы, но этот более запутанный и дорогой. - person pjs; 16.01.2017
comment
Я предположил, что спрашивающему нужно несколько копий Random. Иногда заполнение на основе времени может дать идентичные начальные значения/последовательности, если цикл обрабатывается достаточно быстро. Этот метод позволяет этого избежать. Кроме того, этот метод обеспечивает повторяемость: если вы укажете явное начальное число для masterRand, вы можете повторить точно такой же набор начальных значений, если хотите. Это может быть полезно для отладки и других целей. - person rossum; 16.01.2017
comment
Да, но вы избегаете повторного заполнения и повторяемости, просто используя masterRand для своих nextDouble(), без ненужных затрат на создание набора одноразовых Random. Все еще жду, чтобы услышать, почему OP думает, что им нужен новый генератор каждый раз ... - person pjs; 16.01.2017
comment
Я добавил псевдокод реального случая к исходному вопросу - person Is Niska; 16.01.2017