Случайные ИНТ поведение функции в Java

У меня есть следующий фрагмент кода:Случайные ИНТ поведение функции в Java

public class Main { 
private static final Random rnd = new Random(); 

private static int getRand(int n) { 
    return (Math.abs(rnd.nextInt())%n); 
} 

public static void main(String[] args) { 
    int count=0, n = 2 * (Integer.MAX_VALUE/3); 
    for(int i=0; i<1000000; i++) { 
     if(getRand(n) < n/2) { 
      count++; 
     } 
    } 
    System.out.print(count); 
} 
}

Это всегда дает мне номер близко к 666,666. Значение двух третей генерируемых чисел ниже нижней половины n. Не то, чтобы это было получено, когда n = 2/3 * Integer.MAX_VALUE. 4/7 - еще одна фракция, которая дает мне аналогичный спрэд (~ 5714285). Тем не менее, я получаю равномерное распространение, если n = Integer.MAX_VALUE или если n = Integer.MAX_VALUE/2. Как это поведение отличается от используемой фракции. Может кто-то пролить свет на него.

PS: Я получил эту проблему из книги «Эффективная Ява» Джошуа Блоха.

источник

2014-12-25 n3o

Дайте [rand() считается вредным] (http://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful), чтобы реализовать некоторые из проблем в коде. –

Проблема заключается в операторе modulo (%), что приводит к неравномерному распределению чисел.

Например, предположим, что MAX_INT равно 10 и n = 7, оператор mod отобразит значения 8, 9 и 10 в 1, 2 и 3 соответственно. Это приведет к тому, что числа 1, 2 и 3 удвоят вероятность всех остальных чисел.

Один из способов решить эту проблему, проверив вывод rnd.nextInt() и попробовать еще раз, пока это больше, чем N.

источник

2014-12-25 01:10:14

Да, если мы запустим код без '% n',' count' будет 1/3 числа циклов (именно то, что мы ожидаем: '1/3 * 1/2 * Integer.MAX_VALUE') – xdola

Awesome. Это был ответ, который я искал. В то время как каждый быстро указывал, что% является виновником, этот ответ точно описывает, почему его виновник. Это объясняет, почему доля 2/3 дает 2/3 чисел в нижней половине n. – n3o

Вы получите 50-50, если вы сохранили только значения Math.abs (rnd.nextInt()) в диапазоне от [0..2/3 (Integer.MAX_VALUE)]. Для остальных номеров 1/3 * Integer.MAX_VALUE из-за модуляции вы получите меньшее число в диапазоне от [0..1/3 Integer.MAX_VALUE].

В общем, цифры в диапазоне от [0..1/3 Integer.MAX_VALUE] имеют двойную возможность появления.

источник

2014-12-25 01:04:10

Класс Random предназначен для генерации псевдослучайных чисел. Это означает, что они являются элементами определенной последовательности, которые имеют равномерное распределение. Если вы не знаете последовательность, они кажутся случайными.

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

источник

2014-12-25 01:07:51 Paul92

Тот факт, что это псевдо-случайный, на самом деле не очень уместен; потому что он имеет равномерное распределение, статистика, такая как это всегда будет проверяться, если вы, например. напрямую используйте 'nextInt (n)' – Vitruvius

Как было отмечено выше, getRand делает не генерировать равномерно распределенных случайных чисел в диапазоне [0, п ].

В общем, предположим, что п = а * Integer.MAX_VALUE/В, где А/B> 0,5

Для простоты написания, пусть М = целое.MAX_VALUE

Функция плотности вероятности (PDF) от getRand (п) определяется по формуле:

PDF (х) = 2/М при 0 < х < (ба) M/B

= 1/M for (b-a)M/b < x < aM/b

n/2 соответствует средней точке диапазона [0, aM/b] = aM/2b

Интеграция PDF в диапазоне «первая половина» [0, n/2], мы находим, что вероятность (P), что getRand (n) меньше n/2, определяется по формуле:

P = A/B

Примеры:

а = 2, Ь = 3. P = 2/3 = 2/3 = 0,66666 ... как подсчитано опросником.

a = 4, b = 7. P = 4/7 = 0,5714 ... близко к вычислительному результату собеседника.

источник

2014-12-26 02:59:02 Andrew

Случайные ИНТ поведение функции в Java

ответ

Смежные вопросы