Пакет java.util.random

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

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

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

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

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

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

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

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

import java.util.random.*;

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

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

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

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

Для приложения, создающего множество потоков динамически, возможно, с помощью 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
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 следует предложению Sebastiano Vigna от декабря 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 (см. Steele и Vigna, «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 — параметр (поле только для чтения экземпляра). Параметр 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)