播种连续编号的java.util.Random

Question

我已经将我遇到的一个错误简化为以下几行代码:

    int[] vals = new int[8];
    for (int i = 0; i < 1500; i++)
        vals[new Random(i).nextInt(8)]++;
    System.out.println(Arrays.toString(vals));

输出为:[0,0,0,0,0,1310,190,0]

这只是选择连续数字来种子随机然后使用功率为2的nextInt的工件吗？如果是这样,我是否应该注意到这样的其他陷阱,如果没有,我做错了什么？(我不是在寻找上述问题的解决方案,只是对其他可能出错的一些理解)

---

丹,写得很好的分析.由于javadoc非常清楚如何计算数字,所以为什么会发生这种情况并不是一个谜,就像还有其他类似的异常需要注意 - 我没有看到任何关于连续种子的文档,而我我希望有一些java.util.Random经验的人可以指出其他常见的陷阱.

至于代码,需要几个并行代理具有可重复的随机行为,这些行为恰好从枚举8个元素中选择,只要它们的第一步.一旦我发现了这种行为,种子都来自一个从已知种子创建的主随机对象.在程序的前一个(顺序播种)版本中,所有行为在第一次调用nextInt后迅速分散,因此我花了很长时间才将程序的行为缩小到RNG库,我想避免未来的情况.

Answer 1

RNG的种子本身应该是随机的.您使用的种子只会有一两位不同.

在一个程序中创建两个单独的RNG的理由很少.您的代码不是有意义的情况之一.

只需创建一个RNG并重复使用它,那么您将不会遇到此问题.

回应mmyers的评论:

你碰巧知道java.util.Random足以解释为什么它在这种情况下选择5和6？

答案在java.util.Random的源代码中,它是一个线性同余RNG.在构造函数中指定种子时,将按如下方式对其进行操作.

seed = (seed ^ 0x5DEECE66DL) & mask;

掩模只保留较低的48位并丢弃其他位.

生成实际随机位时,此种子操作如下:

randomBits = (seed * 0x5DEECE66DL + 0xBL) & mask;

现在,如果您认为Parker使用的种子是连续的(0-1499),并且它们被使用一次然后丢弃,则前四个种子生成以下四组随机位:

101110110010000010110100011000000000101001110100
101110110001101011010101011100110010010000000111
101110110010110001110010001110011101011101001110
101110110010011010010011010011001111000011100001

请注意,前10位在每种情况下都是缩进的.这是一个问题,因为他只想生成0-7范围内的值(只需要几位),而RNG实现通过将高位向右移位并丢弃低位来实现这一点.这样做是因为在一般情况下,高位比低位更随机.在这种情况下,它们不是因为种子数据很差.

最后,要了解这些位如何转换为我们得到的十进制值,您需要知道当n是2的幂时,java.util.Random会产生一种特殊情况.它请求31个随机位(来自前三位)高于48),将该值乘以n,然后将其向右移31位.

乘以8(本例中的n值)与左移3位相同.因此,此过程的净效果是将31位28位置向右移动.在上述4个例子的每一个中,这留下了位模式101(或十进制的5).

如果我们在一个值之后没有丢弃RNG,我们会看到序列发散.虽然上面的四个序列都以5开头,但每个序列的第二个值分别为6,0,2和4.初始种子的微小差异开始产生影响.

为了响应更新的问题: java.util.Random是线程安全的,您可以跨多个线程共享一个实例,因此仍然不需要有多个实例.如果您确实需要多个RNG实例,请确保它们完全相互独立地播种,否则您无法相信输出是独立的.

至于为什么你会得到这些效果,java.util.Random并不是最好的RNG.这很简单,非常快,如果你看起来不太近,那就相当随机.但是,如果您对其输出进行了一些严格的测试,您会发现它存在缺陷.你可以在这里看到它.

如果您需要更随机的RNG,可以使用java.security.SecureRandom.这有点慢,但它运作正常.但是,对你来说可能有问题的一件事是它不可重复.具有相同种子的两个SecureRandom实例将不会提供相同的输出.这是设计的.

那么还有其他选择吗？这是我插入自己的库的地方.它包括3个可重复的伪RNG,比SecureRandom更快,比java.util.Random更随机.我没有发明它们,我只是从最初的C版本移植它们.它们都是线程安全的.

我实现了这些RNG,因为我需要更好的进化计算代码.根据我原来的简要回答,这段代码是多线程的,但它只使用一个RNG实例,在所有线程之间共享.