文档章节

Java Random分析

ksfzhaohui
 ksfzhaohui
发布于 2017/01/10 22:12
字数 1955
阅读 80
收藏 1

前言
最近测试经常反应游戏中出现随机的地方,比如:开宝箱,装备的掉落以及属性的随机等,表现的不尽如意;所以开始怀疑我们的随机算法,而我们使用的就是JDK自带的Random类,跟他们解释他们也不太明白,没办法只能以一种更加直观的方式展示给他们看更具有说服力,刚好也可以更加深入的了解一下Random类。

简介
打开Random类的源代码,在类注释中可以看到如下说明:
此类的实例用于生成伪随机数流。此类使用48位的种子,使用线性同余公式 (linear congruential form) 对其进行了修改(请参阅 Donald Knuth 的The Art of Computer Programming, Volume 3,第 3.2.1 节)。
如果用相同的种子创建两个Random实例,则对每个实例进行相同的方法调用序列,它们将生成并返回相同的数字序列。为了保证此属性的实现,为类Random指定了特定的算法。为了Java代码的完全可移植性,Java实现必须让类Random使用此处所示的所有算法。但是允许Random类的子类使用其他算法,只要其符合所有方法的常规协定即可。
Random类实现的算法使用一个protected实用工具方法,每次调用它最多可提供32个伪随机生成的位。

里面提到了线性同余公式,是个产生伪随机数的方法,下面会进行介绍,先看一下Random提供了哪些方法:

Random方法介绍
int next(int bits):生成下一个伪随机数。
boolean nextBoolean():返回下一个伪随机数,它是取自此随机数生成器序列的均匀分布的boolean值。
void nextBytes(byte[] bytes):生成随机字节并将其置于用户提供的 byte 数组中。
double nextDouble():返回下一个伪随机数,它是取自此随机数生成器序列的、在0.0和1.0之间均匀分布的 double值。
float nextFloat():返回下一个伪随机数,它是取自此随机数生成器序列的、在0.0和1.0之间均匀分布float值。
double nextGaussian():返回下一个伪随机数,它是取自此随机数生成器序列的、呈高斯(“正态”)分布的double值,其平均值是0.0标准差是1.0。
int nextInt():返回下一个伪随机数,它是此随机数生成器的序列中均匀分布的 int 值。
int nextInt(int n):返回一个伪随机数,它是取自此随机数生成器序列的、在(包括和指定值(不包括)之间均匀分布的int值。
long nextLong():返回下一个伪随机数,它是取自此随机数生成器序列的均匀分布的 long 值。
void setSeed(long seed):使用单个 long 种子设置此随机数生成器的种子。

通过上面的介绍,大致可以对Random做如下总结:
1.Random是伪随机,既随机是有规则的,
2.相同的种子创建两个Random实例,则对每个实例进行相同的方法调用序列,它们将生成并返回相同的数字序列,
3.Random类中的各方法生成的随机数字都是均匀分布的。

下面通过实例进行简单的验证:

实例验证
1.Random是伪随机,既随机是有规则的

public class RandomTest {
 
    public static void main(String[] args) {
        Random r = new Random(10);
        for (int i = 0; i < 10; i++) {
            System.out.println("rv = " + r.nextInt(100));
        }
    }
}

多次运行RandomTest ,发现每次输出的结果都是一样的,说明随机是有规则的

2.相同的种子创建两个Random实例,则对每个实例进行相同的方法调用序列,它们将生成并返回相同的数字序列

public class RandomTest {
 
    public static void main(String[] args) {
        Random r1 = new Random(10);
        for (int i = 0; i < 10; i++) {
            System.out.println("rv1 = " + r1.nextInt(100));
        }
        System.out.println("========分割线==========");
        Random r2 = new Random(10);
        for (int i = 0; i < 10; i++) {
            System.out.println("rv2 = " + r2.nextInt(100));
        }
    }
}

分别设置了相同的种子,r1和r2运行的结果是一样的

3.Random类中的各方法生成的随机数字都是均匀分布的

public class TestRandom extends ApplicationFrame {
 
    private static final long serialVersionUID = 1L;
 
    private static final int COUNT = 500000;
 
    public TestRandom(final String title) {
        super(title);
        float[][] data = initData();
        NumberAxis domainAxis = new NumberAxis("X");
        domainAxis.setAutoRangeIncludesZero(false);
        NumberAxis rangeAxis = new NumberAxis("Y");
        rangeAxis.setAutoRangeIncludesZero(false);
 
        FastScatterPlot plot = new FastScatterPlot(data, domainAxis, rangeAxis);
        JFreeChart chart = new JFreeChart("Test Random", plot);
        chart.getRenderingHints().put(RenderingHints.KEY_ANTIALIASING,
                RenderingHints.VALUE_ANTIALIAS_ON);
 
        ChartPanel panel = new ChartPanel(chart, true);
        panel.setPreferredSize(new Dimension(800, 500));
        panel.setMinimumDrawHeight(10);
        panel.setMaximumDrawHeight(2000);
        panel.setMinimumDrawWidth(20);
        panel.setMaximumDrawWidth(2000);
 
        setContentPane(panel);
    }
 
    private float[][] initData() {
        float[][] data = new float[2][COUNT];
        Random random = new Random();
        for (int i = 0; i < COUNT; i++) {
            data[0][i] = i + 100000;
            data[1][i] = 100000 + random.nextInt(500000);
        }
        return data;
    }
 
    public static void main(final String[] args) {
        TestRandom demo = new TestRandom("Test Random");
        demo.pack();
        RefineryUtilities.centerFrameOnScreen(demo);
        demo.setVisible(true);
    }
 
}

上面的类依赖于第三方库JFreeChart,用来生成图表的,生成的图片如下图所示:

从图片中可以看到,随机生成的点还是挺均匀的,可以丢给测试去看了。

线性同余公式
线性同余公式LCG(linear congruential generator)是个产生伪随机数的方法,它的优点是:速度快,内存消耗少。
LCG 算法数学上基于公式(来源wiki):
N(j+1) = (A * N(j) + B)(mod M)
其中N(j)是序列的第j个数,N(j+1)是序列的第j+1个数,变量A,B,M是常数,A是乘数,B是增量,M是模,初始值为N(0)。
LCG的周期最大为M,但大部分情况都会少于M,M一般都设置的很大,在选择常数时需要注意,以保证能找到最大的周期;要令LCG达到最大周期,应符合以下条件:
1.B,M互质;
2.M的所有质因数都能整除A-1;
3.若M是4的倍数,A-1也是;
4.A,B,N(0)都比M小;
5.A,B是正整数。

Random类中实现的线性同余算法
1.Random的两种构造方法:
public Random()
public Random(long seed)

第一个构造方法没有指定种子,则系统默认使用和系统时间相关的种子,如下所示:

public Random() {
      this(seedUniquifier() ^ System.nanoTime());
}
 
private static long seedUniquifier() {
      for (;;) {
          long current = seedUniquifier.get();
          long next = current * 181783497276652981L;
          if (seedUniquifier.compareAndSet(current, next))
              return next;
     }
}
 
private static final AtomicLong seedUniquifier
        = new AtomicLong(8682522807148012L);

seedUniquifier这个方法有没有似曾相识,和AtomicLong里面的incrementAndGet一样:

public final long incrementAndGet() {
      for (;;) {
          long current = get();
          long next = current + 1;
          if (compareAndSet(current, next))
              return next;
      }
}

其实就是以原子的方式对seedUniquifier乘以181783497276652981L,然后和System.nanoTime()进行异或运算,得到最终的种子,保证了默认种子的随机性。至于为什么有8682522807148012L和181783497276652981L这两个数值,可以参考这个What’s with 181783497276652981 and 8682522807148012 in Random (Java 7)?

第二个构造方法由用户自己指定一个种子,伪随机数都是基于一个种子数的,然后每需要一个随机数,都是对当前种子进行一些数学运算,得到一个数,基于这个数得到需要的随机数和新的种子。

2.有了种子数之后,其他数是怎么生成的,看最核心的方法next(int bits),代码如下:

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

最重要的一段代码就是:
nextseed = (oldseed * multiplier + addend) & mask;
简单来讲就是用旧的种子(oldseed)乘以一个数(multiplier),加上一个数addend,然后取低48位作为结果(mask相与)。这段代码其实就是上面介绍的线性同余公式,用来帮我们产生伪随机数。

总结
总结一句话就是:Random以线性同余公式为核心算法,基于一个种子数,产生伪随机数。

© 著作权归作者所有

ksfzhaohui

ksfzhaohui

粉丝 390
博文 146
码字总数 207455
作品 3
南京
高级程序员
私信 提问
RHEL7下Tomcat启动慢的原因及解决方案

分析结果 主要原因是生成随机数的时候卡住了,导致tomcat启动不了。 是否有足够的熵来用于产生随机数,可以通过如下命令来查看 [root@tomcat tools]# cat /proc/sys/kernel/random/entropy_a...

有功夫
2018/05/30
0
0
java /dev/./urandom

spring batch jdk1.8 Oracle 12c Linux 程序通过 java -jar -Djava.security.egd=file:/dev/./urandom xxx 的方式执行, 但是在跟数据库进行交互的时候,总会时不时的出现java.sql.SQLRecov...

zdy4494
2017/03/13
192
0
偶遇 JDK 1.8 还未修复的 SecureRandom.getInstance("SHA1PRNG") 之 bug

楼主今天兴高采烈的在部署环境,下载 JDK,打包项目,上传至服务器。 配置 JDK ,打包上传项目楼主就不在这里重复了,读者自行解决哈! 1. 启动项目 java -jar xxxx.jar 令楼主没有想到的是:...

Ryan-瑞恩
05/22
0
0
Java 编程之美:并发编程高级篇之一

本文来自作者 追梦 在 GitChat 上分享 「Java 编程之美:并发编程高级篇之一」 编辑 | 工藤 前言 借用 Java 并发编程实践中的话:编写正确的程序并不容易,而编写正常的并发程序就更难了。 ...

gitchat
2018/05/24
0
0
mysql驱动协议之loadbalance和replication

背景 偶然下和朋友聊到了mysql多节点集群架场景,对应我们各系代码如何去使用它,牵扯到mysql的驱动包中已经支持的策略。发现这块的概念有些模糊,索性就梳理了一番留着后用。重点是:repli...

Owen_Blog
2018/12/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式架构 实现分布式锁的常见方式

一、我们为什么需要分布式锁? 在单机时代,虽然不需要分布式锁,但也面临过类似的问题,只不过在单机的情况下,如果有多个线程要同时访问某个共享资源的时候,我们可以采用线程间加锁的机制...

太猪-YJ
46分钟前
3
0
GitLab Docker 安装记录

安装环境 环境Centos7.4 64 1.拉取镜像文件 docker pull gitlab/gitlab-ce:latest 2.docker 安装 git.zddts.com 为访问域名或换成可以访问的IP docker run -d --hostname git.***.com -p ......

侠者圣
今天
0
0
部署kubernates dashboard

参考官方文档: https://github.com/kubernetes/dashboard 直接部署官方默认的dashboard: kubectl apply -f https://raw.githubusercontent.com/kubernetes/dashboard/v1.10.1/src/deploy/r......

猫海豚
今天
0
0
Docker中Redis的安装

一、下载镜像 docker pull redis 二、创建外挂目录及配置 mkdir /opt/docker/redismkdir /opt/docker/redis/confmkdir /opt/docker/redis/data 三、安装 docker run -d --name compose_r......

闊苡訆涐囍醣
今天
0
0
JNI内存泄露处理方法汇总

在c++中new的对象,如果不返回java,必须用release掉,否则内存泄露。包括NewStringUTF,NewObject。如果返回java不必release,java会自己回收。   jstring jstr = env->NewStringUTF((*p)....

shzwork
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部