有效的 Java 项目 47：了解和使用您的库 - 有缺陷的随机整数方法示例

random java probability effective-java non-uniform-distribution

2022-09-02 23:29:56

在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的小幂，那么生成的随机数序列将在短时间内重复。为什么会这样？的文档说，所以不应该是如果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()

答案 1

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

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

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

Javadoc 中也记录了这一点：

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

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

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

这是一个很好的理由，而不是使用和做自己的范围变换。Random.nextInt(int)Random.nextInt()

问题 2：接下来，他说，如果n不是2的幂，那么一些数字的平均返回频率将高于其他数字。

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

让我们用小数字来看看这个。假设返回了四个等概率结果，0、1、2 和 3。让我们看看如果我们应用它们会发生什么：nextInt()% 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相关的其他资源 - 如果只是切向相关 - 资源：

光谱测试是用于评估LCG质量的统计测试。在这里和这里阅读更多内容。
具有线性结构的经典伪随机数生成器的集合具有一些漂亮的散点图（Java中使用的生成器称为DRAND48）。
关于从Java的生成器预测值 crypto.SE 有一个有趣的讨论。

答案 2

1）当是2的幂时，相当于选择原来的几个较低的位。已知由java使用的生成器类型生成的较低位数字比较高位“更不随机”。它只是用于生成数字的公式的属性。nrnd % n

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