Распределение случайных чисел

Question

у меня есть два варианта кода:

Вариант 1

int myFunc() { 
    return new Random().nextInt(); 
} 

Или:

Вариант 2

private static final Random random = new Random(); 

int myFunc() { 
    return random.nextInt(); 
} 

Я понимаю, что option 2 более идиоматичен. Я задаюсь вопросом о действительности option 1.

В option 1 Я буду использовать только первое число, генерируемое данным семенем. В option 2 я выбираю семя и генерирую цифры n, используя это семя. IIUC гарантируют случайность в этом случае использования.

Мой вопрос, поэтому, если я звоню option 1 много раз есть гарантии на равномерность распределения выходных данных?

Answer 1

Мой настоящий вопрос в том, является ли вариант 1 математически действительным.

Начнем с опцией 2. Генератор случайных чисел, используемый java.util.Random указан в Javadoc следующим образом:

Класс использует 48-битное семя, которое модифицирована с использованием линейной конгруэнтной формулу , (См. Дональд Кнут, «Искусство компьютерного программирования», том 2, раздел 3.2.1.)

и есть более конкретные детали в javadocs различных методов.

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

Теперь с опцией 1 вы используете другой экземпляр Random с новым семенем каждый раз и применяете один раунд формулы LC. Таким образом, вы получаете последовательность чисел, которые, вероятно, будут автокоррелированы с семенами. Однако семена генерируются по-разному, в зависимости от версии Java.

Java 6 делает это:

public Random() { this(++seedUniquifier + System.nanoTime()); } 
private static volatile long seedUniquifier = 8682522807148012L; 

... что не очень случайных вообще. Если вы создали Random экземпляров с постоянным интервалом, семена, вероятно, будут расположены близко друг к другу, и поэтому последовательность случайных чисел, созданных вашей опцией №1, может быть автоматически коррелирована.

В отличие от Java 7 и 8 это сделать:

public Random() { 
    this(seedUniquifier()^System.nanoTime()); 
} 

private static long seedUniquifier() { 
    // L'Ecuyer, "Tables of Linear Congruential Generators of 
    // Different Sizes and Good Lattice Structure", 1999 
    for (;;) { 
     long current = seedUniquifier.get(); 
     long next = current * 181783497276652981L; 
     if (seedUniquifier.compareAndSet(current, next)) 
      return next; 
    } 
} 

private static final AtomicLong seedUniquifier 
    = new AtomicLong(8682522807148012L); 

Последовательность семян, полученных выше, вероятно, будет гораздо лучшее приближение к истинному() случайности. Вероятно, ваш вариант №1 превосходит вариант №2.

Недостатком вашей опции № 1 в Java с 6 по 8 является то, что System.nanoTime(), вероятно, вызывает системный вызов. Это относительно дорого.

---

Поэтому короткий ответ, что это Java от версии, которая опция # 1 и # 2 варианта дает лучшие качества «случайным» числа ... с математической точки зрения.

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

Однако ни один из подходов не был бы подходящим как генератор случайных чисел криптосилы.

Answer 2

Java инициализирует случайное семя System.nanoTime() и последовательный счетчик. Это дает некоторую гарантию того, что семя будет отличаться для каждого вызова, хотя я бы воздержался от его криптографической защиты.

С точки зрения производительности - действительно ли вы ожидать блокировки на внутреннем состоянии Random в варианте 1, чтобы иметь больше производительности ударила, то все следующие:

• доступа и приращение летучих долго
• получать текущее системное время (which is quite expensive)
• динамическое распределение
• другой объект для сбора мусора

Мое предложение будет делать тесты вашего реального приложения, чтобы узнать, но я ожидаю, что вариант 1 будет самым медленным из всех трех.

Answer 3

Быстрый код:

// For occasional tasks that just need an average quality random number 
ExecutorService threadPool = Executors.newCachedThreadPool(); 
threadPool.execute(() -> { 
    ThreadLocalRandom.current().nextInt(); // Fast and unique! 
}); 


// For SecureRandom, high quality random number 
final Random r = new SecureRandom(); 
ExecutorService threadPool = Executors.newCachedThreadPool(); 
threadPool.execute(() -> { 
    r.nextInt(); // sun.security.provider.NativePRNG uses singleton. Can't dodge contention. 
}); 


// Apache Common Math - Mersenne Twister - decent and non-singleton 
int cpu = Runtime.getRuntime().availableProcessors(); 
ExecutorService executor = Executors.newFixedThreadPool(cpu); 
Map<Thread, RandomGenerator> random = new WeakHashMap<>(cpu, 1.0f); 

executor.execute(()-> { 
    RandomGenerator r; 
    synchronized (random) { // Get or create generator. 
     r = random.get(Thread.currentThread()); 
     if (r == null) random.put(Thread.currentThread(), r = new MersenneTwister()); 
    } 
    r.nextInt(1000); 
}); 

---

Пояснение:

1. Два Random того же семени даст те же числа.
   1. Таким образом, мы сосредоточимся на том, можем ли мы гарантировать различные семена.

2. В теории, new Random() в каждом потоке не гарантирует другое семя.

   1. новый случайный засевают на nanoTime и «уникальный» номер.
   2. Число не гарантировано уникальное, поскольку его расчет не синхронизирован.
   3. Что касается nanoTime, это гарантирует, что «по крайней мере хорошо, как currentTimeMillis»
   4. currentTimeMillis не гарантирует ничего, и может быть prettycoarse.
   5. В реальной жизни два раза одинаковы только на old linux systems and Win 98.

3. На практике new Random() в каждом потоке в основном всегда получают различные семена.

   1. Создание потока дорого. Шахта создает 1 на 50 000 нс. И это notslow.
   2. 50μs - это путь выше общих характеристик nanoTime до a few ten ns.
   3. Уникальный расчет числа (1.2) также очень быстрый, поэтому получение такого же числа очень редко.
   4. Используйте Executors, чтобы создать thread pool, чтобы избежать тяжелых новых потоков.

4. zapl suggestedThreadLocalRandom.current().nextInt(). Отличная идея.

   1. Это не создает новый Random, но это также linear congruential generator.
   2. Он генерирует новый случайный случай для каждого потока вызовов как семя этого потока.
   3. Он построен очень быстро в многопоточном режиме. (См. Примечания ниже.)
   4. Он статически посеяно SecureRandom, которые производят более качественные случайные числа.

5. "uniformally распределены" только одна небольшая часть randomnesstests.

   1. Random является somewhat uniform, и его результат может быть predicted дано только два значения.
   2. SecureRandom гарантии this won't happens. (т. е. криптографически сильный)
   3. В каждом потоке нет риска столкновения с семенами, если вы создаете новый SecureRandom.
   4. Но в настоящее время его источник single thread в любом случае, нет параллельного поколения.
   5. Для хорошего RNG, поддерживающего многопоточность, найдите external help, как Apache Common's MT.

Примечание: Детали реализации выведенные из Java 8 исходного кода. Будущая версия Java может измениться; например, ThreadLocalRandom использует sun.misc.Unsafe для хранения семян, , который may be removed в Java 9 заставляет ThreadLocalRandom найти новый способ работы без раздумий.

Answer 4

По моему опыту, лучший баланс между хорошим распределением и производительностью дается с помощью чего-то вроде генератора «Мессерн Твистер» (see in Apache Commons).Для решения с более высоким приоритетом см. this.

Answer 5

No.

Там нет никаких гарантий о свойствах распределения чисел, которые будут производиться с помощью опции 1. Как было четко указано в других ответах, реализация конструктора для java.util.Random зависит от системное время. Поэтому, чтобы обеспечить гарантию на свойства распределения чисел, которые вы получаете с помощью Варианта 1, вам нужно будет иметь возможность предоставлять гарантии о распределении номеров, создаваемых призывами вашей программы, чтобы получить системное время на любом где программа будет запущена.

С вариантом 2, однако, существуют математические гарантии, которые могут быть сделаны о распределении чисел, которые будут созданы во время одного выполнения программы. С линейным конгруэнтным генератором (алгоритмом генерации псевдослучайных чисел, используемым java.util.Random), некоторые из свойств случайности не так хороши, как с другими алгоритмами, но распределение гарантировано относительно однородно.

Это не обязательно означает, что вариант 1 не может служить вашим целям. Это зависит от того, что вы делаете.