17

在 Josh 给出的有缺陷的随机方法的示例中，该方法生成具有给定上限的正随机数n，我不理解他所说的两个缺陷。

书中的方法是：

private static final Random rnd = new Random();

//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}
  • 他说，如果 n 是 2 的小幂，则生成的随机数序列将在短时间内重复。为什么会这样？的文档Random.nextInt()说Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence.所以不应该是如果 n 是一个小整数那么序列会重复自己，为什么这只适用于 2 的幂？
  • 接下来他说，如果 n 不是 2 的幂，则平均而言，某些数字将比其他数字更频繁地返回。Random.nextInt()如果生成均匀分布的随机整数，为什么会发生这种情况？（他提供了一个代码片段，清楚地证明了这一点，但我不明白为什么会这样，以及这与 n 是 2 的幂有何关系）。
4

2 回答 2

38

问题 1：如果 n 是 2 的小幂，则生成的随机数序列会在短时间内重复。

这不是乔希所说的任何事情的必然结果。相反，它只是线性同余生成器的一个已知属性。维基百科有以下说法：

LCG 的另一个问题是，如果 m 设置为 2 的幂，则生成序列的低位比特的周期远短于整个序列。通常，基数中的第 n 个最低有效位b 表示输出序列，其中 b k = m 对于某个整数 k，最多以周期 b n重复。

Javadoc中也指出了这一点：

已知线性同余伪随机数生成器（例如由此类实现的那个）在其低位的值序列中具有短周期。

另一个版本的函数 ,Random.nextInt(int)在这种情况下通过使用不同的位来解决这个问题（强调我的）：

该算法特别处理 n 是 2 的幂的情况：它从底层伪随机数生成器返回正确数量的高位。

Random.nextInt(int)这是比使用Random.nextInt()和进行自己的范围转换更喜欢的一个很好的理由。

问题 2： 接下来他说如果 n 不是 2 的幂，则某些数字的平均返回频率会比其他数字高。

可以返回2 32 个nextInt()不同的数字。如果您尝试使用 将它们放入 n 个存储桶中% n，并且 n 不是 2 的幂，则某些存储桶的数量会比其他存储桶多。这意味着即使原始分布是均匀的，某些结果也会比其他结果更频繁地发生。

让我们用小数字来看看这个。假设nextInt()返回了四个等概率的结果，0、1、2 和 3。让我们看看如果我们应用% 3它们会发生什么：

0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0

如您所见，该算法返回 0 的频率是返回 1 和 2 的频率的两倍。

当 n 是 2 的幂时，这不会发生，因为 2 的一个幂可以被另一个整除。考虑n=2：

0 maps to 0
1 maps to 1
2 maps to 0
3 maps to 1

这里，0 和 1 以相同的频率出现。

其他资源

以下是一些与 LCG 相关的额外资源（如果只是切线相关）：

于 2015-01-05T12:18:54.590 回答
5

1）当n是2的幂时，rnd % n相当于选择了原来的几个低位。众所周知，java 使用的生成器类型生成的数字的低位比高位“随机性更小”。这只是用于生成数字的公式的属性。

2) 想象一下，由 10 返回的最大可能值random()是 10，并且n = 7。现在n % 7将数字 7、8、9 和 10 分别映射到 0、1、2、3。因此，如果原始数字是均匀分布的，结果将严重偏向较低的数字，因为它们出现的频率是 4、5 和 6 的两倍。在这种情况下，无论是否n是 2 的幂，都会发生这种情况与否，但是，如果我们选择 15 而不是 15（即 2^4-1），那么 any n，即 2 的幂将导致均匀分布，因为不会有“多余”数字留在范围的末尾会导致偏差，因为可能值的总数将完全可以被可能的余数整除。

于 2015-01-05T12:19:35.553 回答