Пакет java.util.random

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

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

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

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

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

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

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

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

import java.util.random.*;

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

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

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

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

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

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

Алгоритмы генераторов случайных чисел сгруппированы, как описано ниже.

Группа 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.

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

Для приложения, использующего кортежи последовательно генерируемых значений, может быть желательно использовать генератор, который является 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. Изменение статуса устаревания алгоритма не является изменением спецификации.

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

Алгоритм	Группа	Период	Биты состояния	Равномерность распределения
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
SecureRandom	Legacy	BigInteger.ZERO	Integer.MAX_VALUE	Integer.MAX_VALUE
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: Better Splittable Pseudorandom Number Generators (and Almost as Fast)», 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 является параметром (final-полем экземпляра). Параметр a должен быть нечетным (это позволяет LCG иметь максимальный период, равный 2^p); следовательно, существует 2^p−1 различных вариантов параметра. (Если размер s составляет 128 бит, далее для обозначения старшей половины s, то есть старших 64 бит s, используется название «sh».)

Подгенератор XBG теоретически может использовать любой из множества разнообразных алгоритмов XBG; в этом пакете он всегда использует xoroshiro128, xoshiro256 или xoroshiro1024, в каждом случае без заключительного скремблера (например, «+» или «**»), поскольку LXM применяет отдельный Mixer на более позднем этапе. Состояние 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)