Посев java.util.Random с последовательными номерами

Question

Я упростила обнаруженную ошибку до следующих строк кода:

    int[] vals = new int[8];
    for (int i = 0; i < 1500; i++)
        vals[new Random(i).nextInt(8)]++;
    System.out.println(Arrays.toString(vals));

Вывод: [0, 0, 0, 0, 0, 1310, 190, 0]

Является ли это просто артефактом выбора последовательных чисел для создания рандома и последующего использования nextInt со степенью 2? Если так, есть ли другие подводные камни, о которых я должен знать, и если нет, то что я делаю неправильно? (Я не ищу решения вышеупомянутой проблемы, просто некоторое понимание того, что еще может пойти не так)

---

Дан, хорошо написан анализ. Поскольку в javadoc довольно ясно говорится о том, как вычисляются числа, не секрет, почему это произошло так же, как если бы были другие подобные аномалии, за которыми нужно следить - я не видел никакой документации о последовательных семенах, и я Я надеюсь, что кто-то с некоторым опытом работы с java.util.Random может указать на другие распространенные ошибки.

Что касается кода, необходимо, чтобы несколько параллельных агентов имели повторяющееся случайное поведение, которые выбирают из перечисления 8 элементов до первого шага. Как только я обнаружил это поведение, все семена пришли из главного объекта Random, созданного из известного семени. В предыдущей (последовательно посеянной) версии программы все поведение быстро расходилось после первого вызова nextInt, поэтому мне потребовалось довольно много времени, чтобы сузить поведение программы до библиотеки RNG, и я бы хотел избежать эта ситуация в будущем.

Answer 1

Насколько это возможно, зерно для ГСЧ должно быть случайным. Семена, которые вы используете, будут различаться только на один или два бита.

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

Просто создайте один ГСЧ и используйте его повторно, тогда у вас не возникнет этой проблемы.

В ответ на комментарий от mmyers :

Вы случайно не знаете java.util.Random достаточно хорошо, чтобы объяснить, почему он выбирает 5 и 6 в этом случае?

Ответ находится в исходном коде для java.util.Random, который является линейным конгруэнтным ГСЧ . Когда вы задаете начальное число в конструкторе, им манипулируют следующим образом.

seed = (seed ^ 0x5DEECE66DL) & mask;

Там, где маска просто сохраняет младшие 48 бит и отбрасывает остальные.

При генерации фактических случайных битов это начальное число обрабатывается следующим образом:

randomBits = (seed * 0x5DEECE66DL + 0xBL) & mask;

Теперь, если вы считаете, что начальные числа, используемые Parker , были последовательными (0 -1499), и их использовали один раз, а затем отбрасывали, первые четыре начальных числа генерировали следующие четыре набора случайных битов:

101110110010000010110100011000000000101001110100
101110110001101011010101011100110010010000000111
101110110010110001110010001110011101011101001110
101110110010011010010011010011001111000011100001

Обратите внимание, что старшие 10 бит являются идентичными в каждом случае. Это проблема, потому что он хочет генерировать значения только в диапазоне 0-7 (для этого требуется всего несколько бит), и реализация RNG делает это, сдвигая старшие биты вправо и отбрасывая младшие биты. Это происходит потому, что в общем случае старшие биты являются более случайными, чем младшие биты. В этом случае они не потому, что исходные данные были плохими.

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

Умножение на 8 (значение n в этом примере) аналогично смещению влево на 3 позиции. Таким образом, общий эффект этой процедуры заключается в смещении 31 бита на 28 позиций вправо. В каждом из 4 приведенных выше примеров это оставляет битовую комбинацию 101 (или 5 в десятичном виде). ​​

Если бы мы не отбрасывали ГСЧ только после одного значения, мы бы увидели, что последовательности расходятся. Хотя все четыре последовательности начинаются с 5, вторыми значениями каждого являются 6, 0, 2 и 4 соответственно. Небольшие различия в исходных семенах начинают оказывать влияние.

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

Относительно того, почему вы получаете такие эффекты, java.util.Random не лучший RNG. Это просто, довольно быстро и, если вы не посмотрите слишком внимательно, достаточно случайно. Однако, если вы выполните несколько серьезных тестов на его выходе, вы увидите, что это некорректно. Вы можете видеть это визуально здесь .

Если вам нужен более случайный ГСЧ, вы можете использовать java.security.SecureRandom . Это немного медленнее, но работает правильно. Одна вещь, которая может быть проблемой для вас, это то, что это не повторяется. Два экземпляра SecureRandom с одинаковым начальным числом не будут давать одинаковый вывод Это по замыслу.

Так какие еще варианты есть? Здесь я подключаю свою собственную библиотеку . Он включает в себя 3 повторяющихся псевдо-RNG, которые работают быстрее, чем SecureRandom, и более случайны, чем java.util.Random. Я не изобрел их, я просто портировал их из оригинальных версий Си. Они все потокобезопасны.

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