Random.Next() - 查找第 N 个 .Next()

Question

给定一个一致的种子随机数：

Random r = new Random(0);

调用 r.Next() 一致地生成相同的序列；那么有没有一种方法可以快速发现该系列中的第 N 个值，而无需调用 r.Next() N 次？

我的场景是通过 r.Next() 创建的大量值。应用程序有时会从数组中的任意索引处读取值。我想通过消除数组并根据需要生成值来优化内存使用。但是，暴力破解 r.Next() 500 万次来模拟数组的第 500 万个索引比存储数组的成本更高。是否可以在没有/更少循环的情况下快捷地到达第 N 个 .Next() 值？

Answer 1

我不知道 BCL 中使用的 PRNG 的详细信息，但我的猜测是，您会发现很难/不可能为第 N 个值找到一个好的封闭式解决方案系列。

这个解决方法怎么样：

将随机数生成器的种子设置为所需的索引，然后选择第一个生成的数字。这同样具有“确定性”，并且为您提供了在 O(1) 空间中进行操作的广泛范围。

static int GetRandomNumber(int index)
{
    return new Random(index).Next();
} 

Answer 2

理论上，如果您知道确切的算法和初始状态，您将能够复制该系列，但最终结果将与调用 r.next() 相同。

根据您需要随机数的“好”程度，您可以考虑基于线性同余创建自己的 PRNG生成器 生成数字相对容易/快速。如果您可以忍受“糟糕”的 PRNG，那么可能还有其他算法更适合您的目的。这是否比仅存储 r.next() 中的大量数字更快/更好是另一个问题。

Answer 3

不，我不相信有。对于某些 RNG 算法（例如线性同余生成器），原则上可以在不迭代 n 个步骤的情况下获得第 n 个值，但 Random 类不提供这样做的方法。

我不确定它使用的算法原则上是否可以实现——它是 Knuth 的减法 RNG 的变体（文档中未披露细节），并且看起来原始的 Knuth RNG 应该相当于某种多项式算术允许访问第 n 个值的东西，但是（1）我实际上还没有检查过这一点，并且（2）微软所做的任何调整都可能会破坏这一点。

如果你有一个足够好的“加扰”函数 f 那么你可以使用 f(0), f(1), f(2), ... 作为随机数序列，而不是 f(0), f(f (0))、f(f(f(0))) 等（后者大致是大多数 RNG 所做的），然后当然，在您愿意的任何点开始序列是微不足道的。但你需要选择一个好的 f，而且它可能会比标准的 RNG 慢。

Answer 4

您可以构建自己的按需“索引”和“索引”字典。 “随机值”。这假设您每次程序运行时总是以相同的顺序“要求”索引，或者您不关心每次程序运行时结果是否相同。

Random rnd = new Random(0);
Dictionary<int,int> randomNumbers = new Dictionary<int,int>();
int getRandomNumber(int index)
{
    if (!randomNumbers.ContainsKey(index))
        randomNumbers[index] = rnd.Next();
    return randomNumbers[index];
}