具有延迟初始化的随机数数组

Question

对于分布式应用程序项目，我希望有两个实例共享相同的/知道(伪)随机数。

这可以通过对随机数生成器(RNG)使用相同的种子来实现。但是，只有当两个应用程序以相同的顺序使用RNG输出时，这才有效。就我而言，这是很难甚至是不可能的。

另一种方法是(psedocode)：

rng.setSeed(42);
int[] rndArray;
for(...) {
    rndArray[i] = rng.nextInt();
}

现在，这两个应用程序都有相同的随机数数组，我的问题将得到解决。

但是数组必须是大的，非常大的。这就是延迟初始化部分的地方：rndArray.get(i)如何编写一个类，其中总是相同的随机数(取决于种子)，而不生成、0、和 i-1**?**之间的所有值。

我使用的是JAVA或C++，但是这个问题在大多数编程语言中应该是可以解决的。

Answer 1

你可以使用一个基于随机种子的公式。

例如：

public static int generate(long seed, int index) {
    Random rand = new Random(seed + index * SOME_PRIME);
    return rand.nextInt();
}

这将为给定的种子和索引组合产生相同的值。不过，不要指望它会很快。另一种方法是使用类似的公式。

public static int generate(long seed, int index) {
    double num = seed * 1123529253211.0 + index * 10123457689.0;
    long num2 = Double.doubleToRawLongBits(num);
    return (int) ((num2 >> 42) ^ (num2 >> 21) ^ num2);
}

Answer 2

如果是大型的和稀疏，您可以使用哈希表(缺点:您得到的数字取决于您的访问模式)。

否则，您可以从Programming Pearls中回收解决问题的解决方案(搜索类似于“编程珍珠初始化数组”之类的内容)，但这会浪费内存iirc。

我能想到的最后一个解决方案是，您可以使用一个随机生成器，它可以有效地跳转到指定的位置-- http://mathforum.org/kb/message.jspa?messageID=1519417上的那个非常快速，但是它一次生成16个数字；还有更好的吗？