11

我需要在最大值内生成随机整数。由于性能至关重要，我决定使用 XORShift 生成器而不是 Java 的 Random 类。

long seed = System.nanoTime();
seed ^= (seed << 21);
seed ^= (seed >>> 35);
seed ^= (seed << 4);

这个实现（源代码）给了我一个长整数，但我真正想要的是一个介于 0 和最大值之间的整数。 

public int random(int max){ /*...*/}

实现此方法的最有效方法是什么？

4

2 回答 2

8

我对你的代码很感兴趣，并想出了这个：

public class XORShiftRandom {

private long last;
private long inc;

public XORShiftRandom() {
    this(System.currentTimeMillis());
}

public XORShiftRandom(long seed) {
    this.last = seed | 1;
    inc = seed;
}

public int nextInt(int max) {
    last ^= (last << 21);
    last ^= (last >>> 35);
    last ^= (last << 4);
    inc += 123456789123456789L;
    int out = (int) ((last+inc) % max);     
    return (out < 0) ? -out : out;
}

}

我做了一个简单的测试，它的速度大约是之前的四倍java.util.Random

如果您对它的工作原理感兴趣，可以阅读本文：

免责声明：

上面的代码仅用于研究，不能替代股票 Random 或 SecureRandom。

于 2012-11-23T18:00:20.730 回答
4

播种

这里有很多问题。万一你使用nanoTime了不止一次，你肯定做错了，因为它nanoTime很慢（几百纳秒）。此外，这样做可能会导致质量不佳。

所以让我们假设，你只为你的生成器播种一次。

均匀度

如果关心均匀性，那么至少有两个问题：

异频

它永远不会产生零（除非你不走运播种然后你得到的就是零）。

这很容易通过简单的事情来解决

private long nextLong() {
    x ^= x << 21;
    x ^= x >>> 35;
    x ^= x << 4;
    y += 123456789123456789L;
    return x + y;
}

使用的常量非常随意，除了它必须是奇数。为了获得最佳结果，它应该很大（以便所有位经常更改），它应该有很多位转换（在二进制表示中出现10和01）并且它不应该太规则（0x55...55不好）。

但是，对于x!=0任何奇数常数，均一性得到保证，并且生成器的周期为2**64 * (2*64-1).

我建议像播种

seed = System.nanoTime();
x = seed | 1;
y = seed;

nextInt(int 限制)

由于我在评论中提到的原因，接受的答案提供了非均匀分布的值。正确操作有点复杂，您可以从中复制代码，Random#nextInt也可以尝试这样的事情（未经测试）：

public int nextInt(int limit) {
    checkArgument(limit > 0);
    int mask = -1 >>> Integer.numberOfLeadingZeros(limit);
    while (true) {
        int result = (int) nextLong() & mask;
        if (result < limit) return result;
    }
}

上面，mask二进制看起来像0...01...1，其中最高的对应于最高的limit。使用它，可以在范围内产生一个均匀分布的数字0..mask（均匀性很容易，就像mask+12 的幂一样）。有条件的拒绝不低于的数字limit。因为limit > mask/2，这种情况发生的概率低于 50%，因此预期的迭代次数低于 2。

推荐

玩弄这个很有趣，但测试它很困难，我建议ThreadLocalRandom改用它，除非你需要可重复性。

于 2017-12-04T12:53:25.663 回答