共计 11358 个字符,预计需要花费 29 分钟才能阅读完成。
本系列将 Java 17 之前的随机数 API 以及 Java 17 之后的对立 API 都做了比拟具体的阐明,并且将随机数的个性以及实现思路也做了一些简略的剖析,帮忙大家明确为何会有这么多的随机数算法,以及他们的设计思路是什么。
本系列会分为两篇,第一篇讲述 Java 随机数算法的演变思路以及底层原理与考量,之后介绍 Java 17 之前的随机算法 API 以及测试性能,第二篇详细分析 Java 17 之后的随机数生成器算法以及 API 和底层实现类以及他们的属性,性能以及应用场景,如何抉择随机算法等等,并对 Java 的随机数对于 Java 的一些将来个性的实用进行瞻望
这是第二篇
Java 17 之后的变动
之前的 API 的毛病
- 没有对立的接口:之前的
Random
还有SplittableRandom
没有对立的继承类,以及对立的形象接口,尽管 他们外部办法基本一致,相互替换的麻烦并不多,然而这样咱们要想实现本人的随机算法也比拟麻烦,因为没有对立的接口。 - ThreadLocalRandom 与将来的 Project Loom 的虚构线程相性比拟差。虚构线程是能够一直创立的资源,在大量虚构线程中如果还是用 ThreadLocalRandom 一一对应的话,会有随机性削弱的问题。所以,咱们须要寻找新的实现办法,并且从当初开始为 Project Loom 铺路。
新的 API 定义
在 Java 17 中的 JEP 356: Enhanced Pseudo-Random Number Generators 中,对立了随机数生成器的接口,即 RandomGenerator
:
其中,针对咱们后面提到的 可跳跃性(能够通过简略计算,跳过序列环中的很多元素)形象了对应的接口 JumpableGenerator
,如果跳跃的步长心愿更大一些的话,对应的就是 LeapableGenerator
。
针对咱们后面提到的 可拆分性(能够通过简略计算,拆分出生成齐全不同序列的随机数生成器)也形象了接口 SplitableGenerator
后面提到的算法,与对应的实现类是:
对立形象后,咱们就能够这样创立不同实现类型的随机数字生成器:
RandomGenerator random = RandomGeneratorFactory.of("Random").create();
RandomGenerator secureRandom = RandomGeneratorFactory.of("SecureRandom").create();
RandomGenerator splittableRandom = RandomGeneratorFactory.of("SplittableRandom").create();
RandomGenerator xoroshiro128PlusPlus = RandomGeneratorFactory.of("Xoroshiro128PlusPlus").create();
RandomGenerator xoshiro256PlusPlus = RandomGeneratorFactory.of("Xoshiro256PlusPlus").create();
RandomGenerator l64X256MixRandom = RandomGeneratorFactory.of("L64X256MixRandom").create();
RandomGenerator l64X128StarStarRandom = RandomGeneratorFactory.of("L64X128StarStarRandom").create();
RandomGenerator l64X128MixRandom = RandomGeneratorFactory.of("L64X128MixRandom").create();
RandomGenerator l64X1024MixRandom = RandomGeneratorFactory.of("L64X1024MixRandom").create();
RandomGenerator l32X64MixRandom = RandomGeneratorFactory.of("L32X64MixRandom").create();
RandomGenerator l128X256MixRandom = RandomGeneratorFactory.of("L128X256MixRandom").create();
RandomGenerator l128X128MixRandom = RandomGeneratorFactory.of("L128X128MixRandom").create();
RandomGenerator l128X1024MixRandom = RandomGeneratorFactory.of("L128X1024MixRandom").create();
每种算法实现的随机数生成器类的属性
1.Random
:底层是基于 线性同余算法生成的是一个 48 位的数字 ,抉择的参数保障了每个数字都能随机进去,所以 Period 为 2^48
。nextInt 和 nextLong 都 不能做到齐全平均随机散布 ,因为生成的数字是 48 位的数字,nextInt 即取其中的 32 位,nextLong 是取两次组合在一起。之前的算法剖析咱们提到过,这种算法 不能跳跃,不能宰割。
2.SplittableRandom
: 底层基于 SplitMix 算法 生成的一个 64 位的数字,通过 MurMurhash 保障了区间内每个数字都会呈现(所以 Period 是 2^64
),并且是 齐全均匀分布的 。对于 nextInt 是一个 Period 内每个后果都会呈现两次,对于 nextLong 是一个 Period 内每个后果都会呈现一次。之前的算法剖析咱们提到过,这种算法 不能跳跃,能够宰割。
3.Xoroshiro128PlusPlus
:底层基于 Xoroshiro128++
算法,应用两个 64 位数字记录状态,这 两个数字不会同时为 0,这两个数字通过计算组合成为一个 64 位随机数。因为是两个 64 位数字组合而成,那么就有 2^64 * 2^64 = 2^128
种不同组合,两个数字不会同时为 0,那么就少了一种状况,所以一共是 2^128 - 1
种状况,所以 Period 是 2^128 - 1
。之前的算法剖析咱们提到过,这种算法 能够跳跃,不能宰割。
4.Xoshiro256PlusPlus
:底层基于 Xoshiro256++
算法,应用四个 64 位数字记录状态,这 四个数字不会同时为 0,这四个数字通过计算组合成为一个 64 位随机数。因为是四个 64 位数字组合而成,那么就有 2^64 * 2^64 * 2^64 * 2^64 = 2^256
种不同组合,两个数字不会同时为 0,那么就少了一种状况,所以一共是 2^256 - 1
种状况,所以 Period 是 2^256 - 1
。之前的算法剖析咱们提到过,这种算法 能够跳跃,不能宰割。
5. L64X256MixRandom
:底层基于 LXM 算法,应用一个 64 位数字保留线性同余的后果,4 个 64 位数字记录 Xoshiro
组合,线性同余有 2^64
种不同组合,Xoshiro
有 2^256 - 1
种组合,一共 2^64(2^256 - 1)
种组合,所以 Period 是 2^64(2^256 - 1)
。之前的算法剖析咱们提到过,这种算法 能够宰割,不能跳跃。
其余的 LXM 实现类是相似的。
其实能够从每个算法的实现类的 “ 注解上,看出他们的这些属性:
@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.TYPE)
public @interface RandomGeneratorProperties {
/**
* 算法名称
*/
String name();
/**
* 算法类别
*/
String group() default "Legacy";
/**
* period 大小,由 i, j, k 三个数字形容,即:* period = (2^i - j) * 2^k
*/
int i() default 0;
int j() default 0;
int k() default 0;
/**
* 均匀分布性,0 或者最大值则不是均匀分布,这个值形容在一个 Period 内每个数字呈现多少次,然而不是那么精准的,会疏忽一些小的偏差,例如 Xoroshiro128++ 认为每个数字呈现 2^64 次而不是 2^64 - 1 次。*/
int equidistribution() default Integer.MAX_VALUE;
/**
* 是否是基于零碎 Entropy(参考后面的 SEED 起源章节)的算法
*/
boolean isStochastic() default false;
/**
* 是否是硬件辅助的算法
*/
boolean isHardware() default false;}
咱们还能够通过上面的代码,查看每种实现的属性,同样的,也能够通过这些 API 对算法进行过滤,找到适宜咱们业务的实现类:
RandomGeneratorFactory.all()
.map(fac -> fac.group()+":"+fac.name()
+ "{"
+ (fac.isSplittable()?"splitable":"")
+ (fac.isStreamable()?"streamable":"")
+ (fac.isJumpable()?"jumpable":"")
+ (fac.isLeapable()?"leapable":"")
+ (fac.isHardware()?"hardware":"")
+ (fac.isStatistical()?"statistical":"")
+ (fac.isStochastic()?"stochastic":"")
+ "stateBits:"+fac.stateBits()
+ "}"
)
.sorted().forEach(System.out::println);
输入是:
LXM:L128X1024MixRandom {splitable streamable statistical stateBits: 1152}
LXM:L128X128MixRandom {splitable streamable statistical stateBits: 256}
LXM:L128X256MixRandom {splitable streamable statistical stateBits: 384}
LXM:L32X64MixRandom {splitable streamable statistical stateBits: 96}
LXM:L64X1024MixRandom {splitable streamable statistical stateBits: 1088}
LXM:L64X128MixRandom {splitable streamable statistical stateBits: 192}
LXM:L64X128StarStarRandom {splitable streamable statistical stateBits: 192}
LXM:L64X256MixRandom {splitable streamable statistical stateBits: 320}
Legacy:Random {statistical stateBits: 48}
Legacy:SecureRandom {stochastic stateBits: 2147483647}
Legacy:SplittableRandom {splitable streamable statistical stateBits: 64}
Xoroshiro:Xoroshiro128PlusPlus {streamable jumpable leapable statistical stateBits: 128}
Xoshiro:Xoshiro256PlusPlus {streamable jumpable leapable statistical stateBits: 256}
哪种算法最快(不必测也很显著)
这个依据之前的剖析,应该还是 SplittableRandom 在单线程环境下最快,多线程环境下应用 ThreadLocalRandom 最快。新增的随机算法实现类,Period 约大须要的计算越多,LXM 的实现须要更多计算,退出这些算法是为了适应更多的随机利用,而不是为了更快。不过为了满足大家的好奇心,还是写了如下的代码进行测试,从上面的代码也能够看出,新的 RandomGenerator API 应用更加简便:
package prng;
import java.util.random.RandomGenerator;
import java.util.random.RandomGeneratorFactory;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Threads;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
// 测试指标为吞吐量
@BenchmarkMode(Mode.Throughput)
// 须要预热,排除 jit 即时编译以及 JVM 采集各种指标带来的影响,因为咱们单次循环很屡次,所以预热一次就行
@Warmup(iterations = 1)
// 线程个数
@Threads(10)
@Fork(1)
// 测试次数,咱们测试 50 次
@Measurement(iterations = 50)
// 定义了一个类实例的生命周期,所有测试线程共享一个实例
@State(value = Scope.Benchmark)
public class TestRandomGenerator {
@Param({
"Random", "SecureRandom", "SplittableRandom", "Xoroshiro128PlusPlus", "Xoshiro256PlusPlus", "L64X256MixRandom",
"L64X128StarStarRandom", "L64X128MixRandom", "L64X1024MixRandom", "L32X64MixRandom", "L128X256MixRandom",
"L128X128MixRandom", "L128X1024MixRandom"
})
private String name;
ThreadLocal<RandomGenerator> randomGenerator;
@Setup
public void setup() {
final String finalName = this.name;
randomGenerator = ThreadLocal.withInitial(() -> RandomGeneratorFactory.of(finalName).create());
}
@Benchmark
public void testRandomInt(Blackhole blackhole) throws Exception {blackhole.consume(randomGenerator.get().nextInt());
}
@Benchmark
public void testRandomIntWithBound(Blackhole blackhole) throws Exception {
// 留神不取 2^n 这种数字,因为这种数字个别不会作为理论利用的范畴,然而底层针对这种数字有优化
blackhole.consume(randomGenerator.get().nextInt(1, 100));
}
public static void main(String[] args) throws RunnerException {Options opt = new OptionsBuilder().include(TestRandomGenerator.class.getSimpleName()).build();
new Runner(opt).run();}
}
测试后果:
Benchmark (name) Mode Cnt Score Error Units
TestRandomGenerator.testRandomInt Random thrpt 50 276250026.985 ± 240164319.588 ops/s
TestRandomGenerator.testRandomInt SecureRandom thrpt 50 2362066.269 ± 1277699.965 ops/s
TestRandomGenerator.testRandomInt SplittableRandom thrpt 50 365417656.247 ± 377568150.497 ops/s
TestRandomGenerator.testRandomInt Xoroshiro128PlusPlus thrpt 50 341640250.941 ± 287261684.079 ops/s
TestRandomGenerator.testRandomInt Xoshiro256PlusPlus thrpt 50 343279172.542 ± 247888916.092 ops/s
TestRandomGenerator.testRandomInt L64X256MixRandom thrpt 50 317749688.838 ± 245196331.079 ops/s
TestRandomGenerator.testRandomInt L64X128StarStarRandom thrpt 50 294727346.284 ± 283056025.396 ops/s
TestRandomGenerator.testRandomInt L64X128MixRandom thrpt 50 314790625.909 ± 257860657.824 ops/s
TestRandomGenerator.testRandomInt L64X1024MixRandom thrpt 50 315040504.948 ± 101354716.147 ops/s
TestRandomGenerator.testRandomInt L32X64MixRandom thrpt 50 311507435.009 ± 315893651.601 ops/s
TestRandomGenerator.testRandomInt L128X256MixRandom thrpt 50 187922591.311 ± 137220695.866 ops/s
TestRandomGenerator.testRandomInt L128X128MixRandom thrpt 50 218433110.870 ± 164229361.010 ops/s
TestRandomGenerator.testRandomInt L128X1024MixRandom thrpt 50 220855813.894 ± 47531327.692 ops/s
TestRandomGenerator.testRandomIntWithBound Random thrpt 50 248088572.243 ± 206899706.862 ops/s
TestRandomGenerator.testRandomIntWithBound SecureRandom thrpt 50 1926592.946 ± 2060477.065 ops/s
TestRandomGenerator.testRandomIntWithBound SplittableRandom thrpt 50 334863388.450 ± 92778213.010 ops/s
TestRandomGenerator.testRandomIntWithBound Xoroshiro128PlusPlus thrpt 50 252787781.866 ± 200544008.824 ops/s
TestRandomGenerator.testRandomIntWithBound Xoshiro256PlusPlus thrpt 50 247673155.126 ± 164068511.968 ops/s
TestRandomGenerator.testRandomIntWithBound L64X256MixRandom thrpt 50 273735605.410 ± 87195037.181 ops/s
TestRandomGenerator.testRandomIntWithBound L64X128StarStarRandom thrpt 50 291151383.164 ± 192343348.429 ops/s
TestRandomGenerator.testRandomIntWithBound L64X128MixRandom thrpt 50 217051928.549 ± 177462405.951 ops/s
TestRandomGenerator.testRandomIntWithBound L64X1024MixRandom thrpt 50 222495366.798 ± 180718625.063 ops/s
TestRandomGenerator.testRandomIntWithBound L32X64MixRandom thrpt 50 305716905.710 ± 51030948.739 ops/s
TestRandomGenerator.testRandomIntWithBound L128X256MixRandom thrpt 50 174719656.589 ± 148285151.049 ops/s
TestRandomGenerator.testRandomIntWithBound L128X128MixRandom thrpt 50 176431895.622 ± 143002504.266 ops/s
TestRandomGenerator.testRandomIntWithBound L128X1024MixRandom thrpt 50 198282642.786 ± 24204852.619 ops/s
在之前的后果验证中,咱们曾经晓得了 SplittableRandom 的在单线程中的性能最好,多线程环境下体现最好的是算法与它相似然而做了多线程优化的 ThreadLocalRandom.
如何抉择随机算法
准则是,看你的业务场景,所有的随机组合到底有多少个,在什么范畴内。而后找大于这个范畴的 Period 中,性能最好的算法。例如,业务场景是一副扑克除了大小王 52 张牌,通过随机数决定发牌程序:
- 第一张牌:
randomGenerator.nextInt(0, 52)
,从残余的 52 张牌选 - 第二张牌:
randomGenerator.nextInt(0, 51)
,从残余的 51 张牌选 - 以此类推
那么一共有 52! 这么多后果,范畴在 2^225 ~ 2^226 之间。如果咱们应用的随机数生成器的 Period 小于这个后果集,那么某些牌的程序,咱们可能永远生成不了。所以,咱们须要抉择一个 Period > 54! 的随机数生成器。
将来瞻望
Project Loom 中的随机数生成器
如果 Project Loom 中没有针对 ThreadLocal 的优化,那么 ThreadLocalRandom 的随机性体现也会变差,因为虚构线程是一个能够一直生成回收的相似于对象的货色,ThreadLocalRandom 并不能有限枚举上来。这时候咱们可能须要应用固定的多个随机数生成器给所有的虚构线程应用,而不是应用 ThreadLocalRandom:
ExecutorService vte = Executors.newVirtualThreadExecutor();
SplittableGenerator source = RandomGeneratorFactory.<SplittableGenerator>of("L128X1024MixRandom").create();
// 宰割出 128 个不同的随机数生成器
List<RandomGenerator> rngs = source.splits(128);
AtomicInteger i = new AtomicInteger(0);
vte.submit(() -> {long random = rngs.get(Math.abs(i.incrementAndGet() & 127)).nextLong();
...
});
Scoped Local 个性下的随机数生成器
Scoped Local 是一种更通用的域变量(例如 ThreadLocal 即以后线程域本地,Scoped Local 能够反对不同的域,包含虚构线程,线程,办法域,包域等等),目前还没颁布哪个版本会打算开发,不过按当初的爆料来看,咱们能够应用上面这种形式更好的给每个线程调配随机数生成器:
private final static ScopeLocal<SplittableGenerator> rng_scope =
ScopeLocal.inheritableForType(SplittableGenerator.class);
public static void main(String[] args) throws InterruptedException {
SplittableGenerator rng1 =
RandomGeneratorFactory.<SplittableGenerator>of("L128X1024MixRandom").create();
SplittableGenerator rng2 =
RandomGeneratorFactory.<SplittableGenerator>of("L32X64MixRandom").create();
try (ExecutorService vte = Executors.newVirtualThreadExecutor()) {for (int i = 0; i < 5; i++) {ScopeLocal.where(rng_scope, rng1.split(), () -> { vte.submit(new Task()); });
}
for (int i = 0; i < 5; i++) {ScopeLocal.where(rng_scope, rng2.split(), () -> { vte.submit(new Task()); });
}
}
}
private static class Task implements Runnable {@Override public void run() {SplittableGenerator rng = rng_scope.get();
System.out.println(rng);
}
}
微信搜寻“我的编程喵”关注公众号,每日一刷,轻松晋升技术,斩获各种 offer: