Пакет java.util.random

Этот пакет содержит классы и интерфейсы, которые поддерживают универсальный API для генерации случайных чисел.

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

Основной интерфейс — RandomGenerator, который предоставляет методы для запроса отдельных значений типа int, long, float, double, или boolean, выбранных псевдослучайным образом из равномерного распределения; методы для запроса значений типа double , выбранных псевдослучайным образом из нормального или экспоненциального распределения; и методы для создания потоков значений типа int, long, или double, выбранных псевдослучайным образом из равномерного распределения (такие потоки основаны на spliterator, что позволяет параллельно обрабатывать их элементы). Также существуют статические фабричные методы для создания экземпляра алгоритма конкретного генератора случайных чисел, заданного его именем.

Основной поддерживающий класс — RandomGeneratorFactory. Его можно использовать для генерации нескольких генераторов случайных чисел для определенного алгоритма. RandomGeneratorFactory также предоставляет методы для выбора алгоритмов генерации случайных чисел. RandomGeneratorFactory регистрирует реализации интерфейса RandomGenerator с помощью API поставщиков услуг.

Важным вспомогательным интерфейсом является RandomGenerator.StreamableGenerator, который предоставляет методы для создания основанных на spliterator потоков объектов RandomGenerator, что позволяет параллельно обрабатывать эти объекты с помощью нескольких потоков. В отличие от Random, большинство реализаций интерфейса RandomGenerator не потокобезопасны. Цель состоит в том, чтобы экземпляры не разделялись между потоками; вместо этого каждый поток должен иметь свои собственные генераторы случайных чисел. Различные псевдослучайные алгоритмы, предоставляемые этим пакетом, разработаны таким образом, что несколько экземпляров (с очень высокой вероятностью) ведут себя так, как если бы они были статистически независимыми.

Для многих целей эти два интерфейса являются единственными, которые необходимы потребителю псевдослучайных значений. Также существуют некоторые более специализированные интерфейсы, описывающие более специализированные категории генераторов случайных чисел SplittableGenerator, JumpableGenerator, LeapableGenerator и ArbitrarilyJumpableGenerator, которые имеют определенные стратегии для создания статистически независимых экземпляров.

Использование интерфейсов генераторов случайных чисел

Для начала приложение должно сначала создать один экземпляр класса генератора. Предположим, что содержимое пакета java.util.random импортировано:

import java.util.random.*;

Затем можно выбрать конкретную реализацию, указав имя алгоритма генератора статическому методу RandomGenerator.of(java.lang.String), в этом случае используется конструктор без аргументов для этой реализации:

RandomGenerator g = RandomGenerator.of("L64X128MixRandom");

Для однопоточного приложения этого достаточно. Затем можно вызвать методы g, такие как nextLong(), nextInt(), nextFloat(), nextDouble() и nextBoolean() для генерации отдельных случайных значений. Также можно использовать методы ints(), longs() и doubles() для создания потоков случайных значений. Методы nextGaussian() и nextExponential() извлекают значения с плавающей запятой из неравномерных распределений.

Для многопоточного приложения можно повторить предыдущие шаги для создания дополнительных RandomGenerators, но часто предпочтительнее использовать методы одного единственного первоначального созданного генератора для создания других, подобных ему. (Одна из причин заключается в том, что некоторые алгоритмы генераторов, если их попросить создать новый набор генераторов сразу, могут приложить особые усилия, чтобы гарантировать, что новые генераторы статистически независимы). Если начальный генератор реализует интерфейс RandomGenerator.StreamableGenerator, то можно использовать метод rngs() для создания потока генераторов. Если это параллельный поток, то получить параллельное выполнение легко, используя метод map() на потоке.

Для многопоточного приложения, которое динамически порождает новые потоки, другой подход заключается в использовании начального генератора, реализующего интерфейс RandomGenerator.SplittableGenerator, который затем считается «принадлежащим» начальному потоку для его эксклюзивного использования; затем, когда любой поток нуждается в создании нового потока, он сначала использует метод split() своего собственного генератора для создания нового генератора, который затем передается новому созданному потоку для эксклюзивного использования этим новым потоком.

Выбор алгоритма генератора случайных чисел

Существует три группы алгоритмов генераторов случайных чисел, предоставляемых в Java: группа Legacy, группа LXM и группа Xoroshiro/Xoshiro.

Группа Legacy включает генераторы случайных чисел, существовавшие до JDK 17: Random, ThreadLocalRandom, SplittableRandom и SecureRandom. Random (LCG) — самый слабый из доступных алгоритмов, и пользователям рекомендуется перейти на более новые алгоритмы. Если приложению требуется алгоритм генератора случайных чисел, который является криптографически безопасным, то следует продолжать использовать экземпляр класса SecureRandom.

Алгоритмы в группе LXM похожи друг на друга. Параметры каждого алгоритма можно найти в имени алгоритма. Число после «L» указывает количество битов состояния для подгенератора LCG, а число после «X» — количество битов состояния для подгенератора XBG. «Mix» указывает, что алгоритм использует 8-операционную функцию битового смешивания; «StarStar» указывает использование 3-операционного битового смешивателя.

Алгоритмы в группе Xoroshiro/Xoshiro являются более традиционными алгоритмами (см. David Blackman и Sebastiano Vigna, «Scrambled Linear Pseudorandom Number Generators», ACM Transactions on Mathematical Software, 2021); число в имени указывает количество битов состояния.

Для приложений (таких как физическое моделирование, машинное обучение и игры), которые не требуют криптографически безопасного алгоритма, этот пакет предоставляет несколько реализаций интерфейса RandomGenerator, которые обеспечивают компромисс между скоростью, объёмом памяти, периодом, случайной корреляцией и свойствами равнораспределения.

Для приложений без особых требований, L64X128MixRandom имеет хороший баланс между скоростью, объёмом памяти и периодом и подходит для однопоточных и многопоточных приложений при правильном использовании (отдельный экземпляр для каждого потока).

Если приложение использует только один поток, то Xoroshiro128PlusPlus ещё меньше и быстрее, и, безусловно, имеет достаточно большой период.

Для приложения, работающего в 32-битной аппаратной среде и использующего только один поток или небольшое количество потоков, L32X64MixRandom может быть хорошим выбором.

Для приложения, которое использует множество потоков, распределенных в одной группе в начале вычислений, можно использовать либо «скачкообразный» генератор, такой как Xoroshiro128PlusPlus или Xoshiro256PlusPlus, либо «разделимый» генератор, такой как L64X128MixRandom или L64X256MixRandom.

Для приложения, которое создаёт множество потоков динамически, возможно, с помощью spliterator, рекомендуется использовать «разделимый» генератор, такой как L64X128MixRandom или L64X256MixRandom. Если количество создаваемых динамически генераторов может быть очень большим (миллионы или более), то использование генераторов, таких как L128X128MixRandom или L128X256MixRandom, которые используют 128-битный параметр вместо 64-битного параметра для своего подгенератора LCG, значительно снизит вероятность того, что два экземпляра используют один и тот же цикл состояния.

Для приложения, использующего наборы последовательно сгенерированных значений, может быть желательно использовать генератор, который является k-равномерно распределённым таким образом, что k не меньше длины генерируемых наборов. Генератор L64X256MixRandom доказательно 4-равномерно распределён, а L64X1024MixRandom доказательно 16-равномерно распределён.

Для приложений, генерирующих большие перестановки, может быть лучше использовать генератор, период которого намного больше общего числа возможных перестановок; в противном случае будет невозможно сгенерировать некоторые из предполагаемых перестановок. Например, если цель состоит в том, чтобы перетасовать колоду из 52 карт, количество возможных перестановок равно 52! (52 факториал), что больше 2²²⁵ (но меньше 2²²⁶), поэтому может быть лучше использовать генератор, период которого не менее 2²⁵⁶, например L64X256MixRandom или L64X1024MixRandom или L128X256MixRandom или L128X1024MixRandom. (Конечно, также необходимо предоставить достаточно много битов семян при инициализации генератора, иначе по-прежнему будет невозможно сгенерировать некоторые из предполагаемых перестановок).

Доступные алгоритмы генераторов случайных чисел

Эти алгоритмы [в таблице ниже] должны быть найдены с текущей версией Java SE. Конкретная реализация JDK может распознавать дополнительные алгоритмы; для получения подробностей см. документацию JDK. Набор алгоритмов, требуемых Java SE, может быть обновлен изменениями в спецификации Java SE. Со временем могут быть добавлены новые алгоритмы и удалены старые.

Кроме того, в качестве другой фазы жизненного цикла алгоритм может быть устаревшим. Устаревший алгоритм не рекомендуется использовать. Если необходимый алгоритм устарел, он может быть удален в будущих выпусках. Из-за достижений в разработке и анализе алгоритмов генератора случайных чисел алгоритм может быть устаревшим в течение срока действия конкретного выпуска Java SE. Изменение статуса устаревания алгоритма не является изменением спецификации.

Доступные алгоритмы

Алгоритм	Группа	Период	StateBits	Равномерность
L128X1024MixRandom	LXM	BigInteger.ONE.shiftLeft(1024).subtract(BigInteger.ONE).shiftLeft(128)	1152	1
L128X128MixRandom	LXM	BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(128)	256	1
L128X256MixRandom	LXM	BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(128)	384	1
L32X64MixRandom	LXM	BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE).shiftLeft(32)	96	1
L64X1024MixRandom	LXM	BigInteger.ONE.shiftLeft(1024).subtract(BigInteger.ONE).shiftLeft(64)	1088	16
L64X128MixRandom	LXM	BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(64)	192	2
L64X128StarStarRandom	LXM	BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(64)	192	2
L64X256MixRandom	LXM	BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(64)	320	4
Random	Legacy	BigInteger.ONE.shiftLeft(48)	48	0
SplittableRandom	Legacy	BigInteger.ONE.shiftLeft(64)	64	1
ThreadLocalRandom *	Legacy	BigInteger.ONE.shiftLeft(64)	64	1
Xoroshiro128PlusPlus	Xoroshiro	BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE)	128	1
Xoshiro256PlusPlus	Xoshiro	BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE)	256	3

^* ThreadLocalRandom можно получить только через ThreadLocalRandom.current().

Категории алгоритмов генераторов псевдослучайных чисел

Исторически большинство алгоритмов генераторов псевдослучайных чисел основаны на некотором типе конечного автомата с одним большим циклом состояний; когда необходимо, чтобы несколько потоков использовали один и тот же алгоритм одновременно, обычный метод заключается в организации для каждого потока прохождения различной области цикла состояний. Эти области могут быть распределены между потоками, начиная с одного начального состояния, а затем используя «функцию перехода», которая перемещается на большое расстояние по циклу (возможно, 2⁶⁴ шагов или более); функция перехода применяется многократно и последовательно, чтобы определить широко разнесенные состояния, которые затем распределяются, по одному на каждый поток, в качестве начального состояния для генератора, который будет использоваться этим потоком. Эта стратегия поддерживается интерфейсом RandomGenerator.JumpableGenerator. Иногда желательно поддерживать два уровня перехода (на большие расстояния и на очень большие расстояния); эта стратегия поддерживается интерфейсом RandomGenerator.LeapableGenerator. В этом пакете реализации этого интерфейса включают «Xoroshiro128PlusPlus» и «Xoshiro256PlusPlus». Также существует интерфейс RandomGenerator.ArbitrarilyJumpableGenerator для алгоритмов, которые позволяют переходить по циклу состояний на любое заданное пользователем расстояние; в настоящее время в этом пакете нет реализаций этого интерфейса.

Более новая категория «разделимых» алгоритмов генераторов псевдослучайных чисел использует большой набор циклов состояний и предпринимает некоторые попытки обеспечить, чтобы отдельные экземпляры использовали разные циклы состояний; но даже если два экземпляра «случайно» используют один и тот же цикл состояний, они, скорее всего, пройдут разные области этого общего цикла состояний. Эта стратегия поддерживается интерфейсом RandomGenerator.SplittableGenerator. В этом пакете реализации этого интерфейса включают «L32X64MixRandom», «L64X128StarStarRandom», «L64X128MixRandom», «L64X256MixRandom», «L64X1024MixRandom», «L128X128MixRandom», «L128X256MixRandom» и «L128X1024MixRandom»; обратите внимание, что класс SplittableRandom также реализует этот интерфейс.

Семейство алгоритмов генераторов псевдослучайных чисел LXM

Структура центрального метода nextLong (или nextInt) алгоритма LXM следует предложению Себастьяно Виньи от декабря 2017 года, что использование одного линейного конгруэнтного генератора (LCG) в качестве первого подгенератора и одного генератора на основе XOR (XBG) в качестве второго подгенератора (вместо использования двух подгенераторов LCG) обеспечит больший период, лучшую равномерность распределения, масштабируемость и более высокое качество. Каждая из конкретных реализаций здесь сочетает один из наиболее известных в настоящее время алгоритмов XBG (xoroshiro128 или xoshiro256, описанных Блэкменом и Виньей в «Scrambled Linear Pseudorandom Number Generators», «ACM Transactions on Mathematical Software», 2021) с LCG, который использует один из лучших известных в настоящее время множителей (найденных путем поиска лучших множителей в 2019 году Стилом и Виньей, описанных в «Computationally Easy, Spectrally Good Multipliers for Congruential Pseudorandom Number Generators», «Software: Practice and Experience» (2021), doi:10.1002/spe.3030), а затем применяет либо функцию смешивания, определенную Дугом Ли, либо простой скремблер, предложенный Блэкменом и Виньей. Тестирование подтвердило, что алгоритм LXM значительно превосходит алгоритм SplitMix (2014), используемый SplittableRandom (см. Стиля и Виньи, «LXM: Лучшие разделимые генераторы псевдослучайных чисел (и почти так же быстрые)», «Proc. 2021 ACM OOPSLA Conference»). Каждый класс с именем в формате LpXqSomethingRandom использует какой-либо конкретный член семейства алгоритмов генераторов случайных чисел LXM; «LXM» означает «LCG, XBG, Mixer». Каждый генератор LXM имеет два подгенератора; один — LCG (линейный конгруэнтный генератор), а другой — XBG (генератор на основе XOR). Каждый вывод генератора LXM — результат объединения состояния LCG и состояния XBG с использованием функции смешивания (а затем состояние LCG и состояние XBG обновляются).

Подгенератор LCG имеет шаг обновления в форме s = m*s + a, где s, m, и a — все двоичные целые числа одинакового размера, каждый из которых имеет p бит; s — изменяемое состояние, множитель m фиксирован (одинаков для всех экземпляров класса), а слагаемое a — параметр (постоянное поле экземпляра). Параметр a должен быть нечётным (это позволяет LCG иметь максимальный период, а именно 2^p); поэтому существует 2^p−1 различных вариантов параметра. (Когда размер s равен 128 битам, тогда мы используем имя «sh» ниже для обозначения старшей половины s, то есть старших 64 битов s.)

Подгенератор XBG принципиально может быть любым из множества алгоритмов XBG; в этом пакете он всегда либо xoroshiro128, либо xoshiro256, либо xoroshiro1024, в каждом случае без финального скремблера (такого как «+» или «**»), поскольку LXM использует отдельный смеситель позже в процессе. Состояние XBG состоит из некоторого фиксированного числа полей int или long в общем случае с именами x0, x1, и так далее, которые могут принимать любые значения при условии, что не все они равны нулю. Общий размер этих полей равен q битам; следовательно, период этого подгенератора равен 2^q−1.

Поскольку периоды 2^p и 2^q−1 двух подгенераторов взаимно просты, период любого отдельного экземпляра алгоритма LXM (длина последовательности сгенерированных значений до повторения) является произведением периодов подгенераторов, то есть 2^p(2^q−1), что немного меньше, чем 2^(p+q). Кроме того, если у двух различных экземпляров одного и того же алгоритма LXM разные a параметры, то их циклы производимых значений будут разными.

В общем случае, среди генераторов «LpXq» память, необходимая для экземпляра, составляет 2p+q бит. (Если q равен 1024 или больше, состояние XBG представляется в виде массива, поэтому для заголовка объекта массива требуются дополнительные биты, а еще 32 бита используются для индекса массива.)

Более крупные значения p подразумевают меньшую вероятность того, что два различных экземпляра пройдут по одному и тому же циклу состояний, а более крупные значения q подразумевают, что генератор равномерно распределен в большем количестве измерений (это доказано, когда p равно 64 и предполагается приблизительно верно, когда p равно 128). Класс с «Mix» в своем имени использует довольно сильную функцию смешивания с отличными характеристиками водопада; класс с «StarStar» в своем имени использует более слабую, но более быструю функцию смешивания.

Конкретные алгоритмы LXM, используемые в этом пакете, все выбраны таким образом, что 64-битные значения, производимые методом nextLong(), точно равномерно распределены (например, для любого конкретного экземпляра «L64X128MixRandom» в течение его цикла каждое из 2⁶⁴ возможных long значений будет произведено 2¹²⁸−1 раз). Значения, производимые методами nextInt(), nextFloat() и nextDouble(), также точно равномерно распределены. Некоторые алгоритмы обеспечивают дополнительную гарантию k-равномерности для некоторого k, большего 1, что означает, что последовательные неперекрывающиеся k-кортежи 64-битных значений, произведённых методом nextLong(), точно равномерно распределены (равновероятны).

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

Свойства алгоритма

Реализация	Период	Размер состояния	Размер параметра	nextLong() значения
"L32X64MixRandom"	232(264−1)	96 бит	32 бита
"L64X128StarStarRandom"	264(2128−1)	192 бита	64 бита	2-равномерно распределены и точно равномерно распределены
"L64X128MixRandom"	264(2128−1)	192 бита	64 бита	2-равномерно распределены и точно равномерно распределены
"L64X256MixRandom"	264(2256−1)	320 бит	64 бита	4-равномерно распределены и точно равномерно распределены
"L64X1024MixRandom"	264(21024−1)	1088 бит	64 бита	16-равномерно распределены и точно равномерно распределены
"L128X128MixRandom"	2128(2128−1)	256 бит	128 бит	точно равномерно распределены
"L128X256MixRandom"	2128(2256−1)	384 бита	128 бит	точно равномерно распределены
"L128X1024MixRandom"	2128(21024−1)	1152 бита	128 бит	точно равномерно распределены

Для алгоритмов, перечисленных выше, чьи имена начинаются с L32, 32-битные значения, производимые методом nextInt(), точно равномерно распределены, но 64-битные значения, производимые методом nextLong(), не точно равномерно распределены.

Для алгоритмов, перечисленных выше, чьи имена начинаются с L64 или L128, 64-битные значения, производимые методом nextLong(), точно равномерно распределены: каждый экземпляр в течение своего цикла будет производить каждое из 2⁶⁴ возможных long значений ровно одинаковое количество раз. Например, любой конкретный экземпляр «L64X256MixRandom» в течение своего цикла будет производить каждое из 2⁶⁴ возможных long значений 2²⁵⁶−1 раз. Значения, производимые методами nextInt(), nextFloat() и nextDouble(), также точно равномерно распределены.

Кроме того, для алгоритмов, перечисленных выше, чьи имена начинаются с L64, 64-битные значения, произведённые методом nextLong(), являются k-равномерно распределёнными (но не точно k-равномерно распределёнными). Для уточнения, взяв «L64X256MixRandom» в качестве примера: для любого конкретного экземпляра «L64X256MixRandom» рассмотрим (перекрывающиеся) подпоследовательности длиной 4 в цикле 64-битных значений, производимых nextLong() (предполагается, что другие методы не вызываются и не влияют на состояние). Существует 2⁶⁴(2²⁵⁶−1) таких подпоследовательностей, и каждая подпоследовательность, состоящая из 4 64-битных значений, может иметь одно из 2²⁵⁶ значений. Из этих 2²⁵⁶ значений подпоследовательностей почти все из них (2²⁵⁶−2⁶⁴) встречаются 2⁶⁴ раз в течение всего цикла, а остальные 2⁶⁴ значений подпоследовательностей встречаются только 2⁶⁴−1 раз. Таким образом, отношение вероятности получения любого конкретного из менее распространённых значений подпоследовательностей и вероятности получения любого конкретного из более распространённых значений подпоследовательностей равно 1−2^-64. (Обратите внимание, что набор из 2⁶⁴ менее распространённых значений подпоследовательностей будет отличаться от одного экземпляра «L64X256MixRandom» к другому, как функция аддитивного параметра LCG.) Значения, производимые методами nextInt(), nextFloat() и nextDouble(), также являются 4-равномерно распределёнными (но не точно 4-равномерно распределёнными).

Следующая таблица содержит значение множителя LCG, имя используемого конкретного алгоритма XBG, конкретные числовые параметры для этого алгоритма XBG и функцию смешивания для каждого из конкретных алгоритмов LXM, используемых в этом пакете. (Обратите внимание, что множитель, используемый для 128-битных случаев LCG, имеет ширину 65 бит, поэтому константа 0x1d605bbb58c8abbfdL в таблице фактически не может быть использована в коде; вместо этого в исходном коде представлены только 64 младших бита 0xd605bbb58c8abbfdL, а недостающие 1 бит обрабатываются через специальное кодирование алгоритма умножения-сложения, используемого в LCG.)

LXM Мультипликаторы

Реализация	Мультипликатор LCG m	Алгоритм XBG	Параметры XBG	Функция смешивания
"L32X64MixRandom"	0xadb4a92d	xoroshiro64, версия 1.0	(26, 9, 13)	mixLea32(s+x0)
"L64X128StarStarRandom"	0xd1342543de82ef95L	xoroshiro128, версия 1.0	(24, 16, 37)	Long.rotateLeft((s+x0)* 5, 7) * 9
"L64X128MixRandom"	0xd1342543de82ef95L	xoroshiro128, версия 1.0	(24, 16, 37)	mixLea64(s+x0)
"L64X256MixRandom"	0xd1342543de82ef95L	xoshiro256, версия 1.0	(17, 45)	mixLea64(s+x0)
"L64X1024MixRandom"	0xd1342543de82ef95L	xoroshiro1024, версия 1.0	(25, 27, 36)	mixLea64(s+x0)
"L128X128MixRandom"	0x1d605bbb58c8abbfdL	xoroshiro128, версия 1.0	(24, 16, 37)	mixLea64(sh+x0)
"L128X256MixRandom"	0x1d605bbb58c8abbfdL	xoshiro256, версия 1.0	(17, 45)	mixLea64(sh+x0)
"L128X1024MixRandom"	0x1d605bbb58c8abbfdL	xoroshiro1024, версия 1.0	(25, 27, 36)	mixLea64(sh+x0)