有效的Java项目47：了解并使用您的库 - 有缺陷的随机整数方法示例 [英] Effective Java Item 47: Know and use your libraries - Flawed random integer method example

问题描述

在Josh给出的有缺陷的随机方法的例子中，该方法生成一个带有给定上限 n 的正随机数，我不明白他的两个缺点这个方法是：

  private static final Random rnd = new Random（）; 
 
 //常见但有很大缺陷
 static int random（int n）{
 return Math.abs（rnd.nextInt（））％n; 
} 
  

• 他说如果n是小功率如图2所示，生成的随机数序列将在短时间后重复出现。为什么会这样？ Random.nextInt（）的文档说从此随机数生成器的序列中返回下一个伪随机，均匀分布的int值。所以不应该是因为如果n是一个小整数，那么序列会重复，为什么这只适用于2的幂？


• 接下来他说如果n不是2的幂，平均一些数字将比其他数字更频繁地返回。如果 Random.nextInt（）生成均匀分布的随机整数，为什么会发生这种情况？ （他提供了一个代码片段，清楚地证明了这一点，但我不明白为什么会这样，以及这与n是2的权力有什么关系。）

解决方案

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

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

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

这也在 Javadoc ：

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

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

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

这是一个有理由优先使用 Random.nextInt（int）而不是使用 Random.nextInt（）并进行自己的范围转换。

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

<$> ³² 不同的数字可由<$返回C $ C> nextInt（）。如果您尝试使用％n 将它们放入n个桶中，并且n不是2的幂，则某些桶将具有比其他桶更多的数字。这意味着即使原始分布是统一的，某些结果也会比其他结果更频繁地出现。

让我们用小数字看一下。假设 nextInt（）返回了四个等概率结果，0,1,2和3.让我们看看如果我们应用％3 给他们：

  0映射到0 
 1映射到1 
 2映射到2 
 3映射到0 
  

如您所见，算法将返回0两倍频率因为它将返回1和2中的每一个。

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

  0映射到0 
 1张地图到1 
 2张地图到0 
 3张地图到1 
  

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

其他资源

此处是一些额外的 - 如果只是切向相关 - 与LCG相关的资源：

• 光谱测试是用于评估LCG质量的统计测试。阅读更多此处和这里。


• 具有线性结构的经典伪随机数生成器的集合具有一些漂亮的散点图（Java中使用的生成器称为 DRAND48 ）。


• 有关crypto.SE的一个有趣的讨论从Java的生成器预测值。

In the example Josh gives of the flawed random method that generates a positive random number with a given upper bound n, I don't understand the two of the flaws he states.

The method from the book is:

private static final Random rnd = new Random();

//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}

• He says that if n is a small power of 2, the sequence of random numbers that are generated will repeat itself after a short period of time. Why is this the case? The documentation for Random.nextInt() says Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. So shouldn't it be that if n is a small integer then the sequence will repeat itself, why does this only apply to powers of 2?
• Next he says that if n is not a power of 2, some numbers will be returned on average more frequently than others. Why does this occur, if Random.nextInt() generates random integers that are uniformly distributed? (He provides a code snippet which clearly demonstrates this but I don't understand why this is the case, and how this is related to n being a power of 2).

解决方案

Question 1: if n is a small power of 2, the sequence of random numbers that are generated will repeat itself after a short period of time.

This is not a corollary of anything Josh is saying; rather, it is simply a known property of linear congruential generators. Wikipedia has the following to say:

A further problem of LCGs is that the lower-order bits of the generated sequence have a far shorter period than the sequence as a whole if m is set to a power of 2. In general, the n-th least significant digit in the base b representation of the output sequence, where b^k = m for some integer k, repeats with at most period bⁿ.

This is also noted in the Javadoc:

Linear congruential pseudo-random number generators such as the one implemented by this class are known to have short periods in the sequence of values of their low-order bits.

The other version of the function, Random.nextInt(int), works around this by using different bits in this case (emphasis mine):

The algorithm treats the case where n is a power of two specially: it returns the correct number of high-order bits from the underlying pseudo-random number generator.

This is a good reason to prefer Random.nextInt(int) over using Random.nextInt() and doing your own range transformation.

Question 2: Next he says that if n is not a power of 2, some numbers will be returned on average more frequently than others.

There are 2³² distinct numbers that can be returned by nextInt(). If you try to put them into n buckets by using % n, and n isn't a power of 2, some buckets will have more numbers than others. This means that some outcomes will occur more frequently than others even though the original distribution was uniform.

Let's look at this using small numbers. Let's say nextInt() returned four equiprobable outcomes, 0, 1, 2 and 3. Let's see what happens if we applied % 3 to them:

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

As you can see, the algorithm would return 0 twice as frequently as it would return each of 1 and 2.

This does not happen when n is a power of two, since one power of two is divisible by the other. Consider n=2:

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

Here, 0 and 1 occur with the same frequency.

Additional resources

Here are some additional -- if only tangentially relevant -- resources related to LCGs:

• Spectral tests are statistical tests used to assess the quality of LCGs. Read more here and here.
• A collection of classical pseudorandom number generators with linear structures has some pretty scatterplots (the generator used in Java is called DRAND48).
• There is an interesting discussion on crypto.SE about predicting values from Java's generator.

这篇关于有效的Java项目47：了解并使用您的库 - 有缺陷的随机整数方法示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！