Эффективный элемент Java 47: знайте и используйте свои библиотеки - пример метода случайных целочисленных ошибок

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

Метод из книги:

private static final Random rnd = new Random();

//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}
  • Он говорит, что если n - малая степень 2, последовательность генерируемых случайных чисел будет повторяться через короткий промежуток времени. Почему это так? Документация для Random.nextInt() говорится Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. Так не должно ли быть так, что если n - небольшое целое число, то последовательность повторится, почему это относится только к степеням 2?
  • Затем он говорит, что если n не является степенью 2, некоторые числа будут возвращаться в среднем чаще, чем другие. Почему это происходит, если Random.nextInt() генерирует случайные целые числа, которые равномерно распределены? (Он предоставляет фрагмент кода, который четко демонстрирует это, но я не понимаю, почему это так, и как это связано с тем, что n имеет степень 2).
Источник

2 ответа

Решение

Вопрос 1: если n- малая степень 2, последовательность генерируемых случайных чисел будет повторяться через короткий промежуток времени.

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

Еще одна проблема LCG состоит в том, что биты младшего разряда сгенерированной последовательности имеют намного более короткий период, чем последовательность в целом, если m установлен на степень 2. Как правило, n-й младший значащий разряд в базе b представление выходной последовательности, где b k = m для некоторого целого числа k, повторяется с максимальным периодом b n.

Это также отмечено в Javadoc:

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

Другая версия функции, Random.nextInt(int), работает вокруг этого, используя различные биты в этом случае (выделение мое):

Алгоритм специально обрабатывает случай, когда n- степень двух: он возвращает правильное количество старших бит из базового генератора псевдослучайных чисел.

Это хорошая причина, чтобы предпочесть Random.nextInt(int) над использованием Random.nextInt() и делать свое собственное преобразование диапазона.

Вопрос 2: Далее он говорит, что если n не является степенью 2, некоторые числа будут возвращаться в среднем чаще, чем другие.

Есть 2 32 различных номера, которые могут быть возвращены nextInt(), Если вы попытаетесь поместить их в n ведер, используя % n и n не является степенью 2, некоторые сегменты будут иметь больше чисел, чем другие. Это означает, что некоторые результаты будут происходить чаще, чем другие, даже если исходное распределение было однородным.

Давайте посмотрим на это с помощью небольших чисел. Скажем nextInt() вернул четыре равновероятных результата, 0, 1, 2 и 3. Посмотрим, что произойдет, если мы подадим заявку % 3 им:

0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0

Как видите, алгоритм будет возвращать 0 в два раза чаще, чем каждый из 1 и 2.

Этого не происходит, когда n является степенью двойки, так как одна степень двойки делится на другую. Рассматривать n=2:

0 maps to 0
1 maps to 1
2 maps to 0
3 maps to 1

Здесь 0 и 1 встречаются с одинаковой частотой.

Дополнительные ресурсы

Вот некоторые дополнительные - если только косвенно релевантные - ресурсы, связанные с LCG:

Источник

1) Когда n это степень 2, rnd % n эквивалентно выбору нескольких младших битов оригинала. Известно, что младшие биты чисел, генерируемые типом генераторов, используемых java, "менее случайны", чем старшие биты. Это просто свойство формулы, используемой для генерации чисел.

2) Представьте, что максимально возможное значение, возвращаемое random() 10, и n = 7, Сейчас занимаюсь n % 7 отображает числа 7, 8, 9 и 10 в 0, 1, 2, 3 соответственно. Поэтому, если исходное число распределено равномерно, результат будет сильно смещен в сторону более низких чисел, поскольку они будут появляться в два раза чаще, чем 4, 5 и 6. В этом случае это происходит независимо от того, n является степенью двойки или нет, но, если вместо 10 мы выбрали, скажем, 15 (что 2^4-1), то любой n, то есть степень двух приведет к равномерному распределению, потому что не будет "лишних" чисел, оставшихся в конце диапазона, чтобы вызвать смещение, потому что общее количество возможных значений будет точно делиться на число возможных остатки.

Источник
Другие вопросы по тегам