Пакет java.util.random

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

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

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

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

Важным вспомогательным интерфейсом является RandomGenerator.StreamableGenerator, который предоставляет методы для создания потоков spliterator-based потоков объектов 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 and 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. Также есть интерфейс RandomGenerator.ArbitrarilyJumpableGenerator для алгоритмов, которые позволяют переходить по циклу состояний на любое заданное пользователем расстояние. В этом пакете реализации этих интерфейсов включают «Xoroshiro128PlusPlus» и «Xoshiro256PlusPlus».

Более новая категория «разделимых» алгоритмов генерации псевдослучайных чисел использует большую совокупность циклов состояний и пытается гарантировать, что разные экземпляры используют разные циклы состояний; но даже если два экземпляра «случайно» используют один и тот же цикл состояния, они, скорее всего, пройдут по разным частям этого общего цикла состояния. Эта стратегия поддерживается интерфейсом 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, описанных Blackman и Vigna в «Scrambled Linear Pseudorandom Number Generators», ACM Transactions on Mathematical Software, 2021) с LCG, использующим один из лучших на данный момент известных множителей (найденных в результате поиска лучших множителей в 2019 году Steele и Vigna), а затем применяет либо функцию смешивания, предложенную Doug Lea, либо простой скремблер, предложенный Blackman и Vigna. Тестирование подтвердило, что алгоритм LXM значительно превосходит по качеству алгоритм SplitMix (2014), используемый SplittableRandom. Каждый класс с именем в формате 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)	mixLea32(s+x0)
"L64X256MixRandom"	0xd1342543de82ef95L	xoshiro256, версия 1.0	(17, 45)	mixLea32(s+x0)
"L64X1024MixRandom"	0xd1342543de82ef95L	xoroshiro1024, версия 1.0	(25, 27, 36)	mixLea32(s+x0)
"L128X128MixRandom"	0x1d605bbb58c8abbfdL	xoroshiro128, версия 1.0	(24, 16, 37)	mixLea32(sh+x0)
"L128X256MixRandom"	0x1d605bbb58c8abbfdL	xoshiro256, версия 1.0	(17, 45)	mixLea32(sh+x0)
"L128X1024MixRandom"	0x1d605bbb58c8abbfdL	xoroshiro1024, версия 1.0	(25, 27, 36)	mixLea32(sh+x0)