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

Question

假设已经有了一个一直用相同种子生成的随机数：

Random r = new Random(0);

调用 r.Next() 将会持续产生同样的序列，那么有没有快速地找到该序列中第 N 个值的方法，而不需要调用 r.Next() N 次呢？

我的场景是需要创建一个大的由 r.Next() 生成的值的数组。应用程序偶尔需要在任意索引处从数组中读取一个值。我想通过消除数组并代之以按需生成值来优化内存使用率。但是，要模拟出数组的第五百万个索引，需要使用暴力法来调用 r.Next() 五百万次，这比存储数组更加昂贵。是否可能通过较少循环的方式，快速地找到第 N 个 .Next() 值呢？

- with

---

这显然取决于所使用的算法。我相信大多数伪随机数生成器使用一个函数来计算下一个值，该函数从前一个值计算出来。虽然可能有一些算法允许直接计算第N个值。System.Random使用的算法可能不在其中。 - dtb

Answer 1

我不知道BCL中使用的PRNG的详细信息，但我的猜测是你会发现极其困难/不可能找到一个漂亮的、封闭形式的解决方案来计算该系列的第N个值。

那么这个解决方法如何：

将随机数生成器的seed设置为所需的索引，然后选择第一个生成的数字。这同样是“确定性”的，并且在O(1)空间内可以让您有很大的可操作范围。

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

- Ani

---

+1 我喜欢它。这也非常适合使用单个前向种子的线性同余生成器。然而，这只是每个LCG /生成器的固定映射。:( - user166390

一些注意事项。(1) 初始化随机数生成器可能会很耗费时间，因此这可能会使您的随机数生成比本来应该慢得多。(2) 随机数生成器执行的迭代操作可能并不是那么随机。 （例如，线性同余生成法并不是那么糟糕，尽管它们已经过时了，但如果您将此方法应用于LCG，则会得到一个非常不随机的序列。）对于.NET的Random类，我认为#1适用，但#2可能不适用。 - Gareth McCaughan

我曾考虑过这个方法，但因为Gareth提到的新Random()成本太高而放弃了。然而，阅读其他回答后，这似乎是使用System.Random“虚拟化”随机数数组的唯一方法，所以我会试着搭建它，并查看在我的特定应用程序中性能如何。如果失败，听起来我应该探索LCG。 - with

Answer 2

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

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

- uesp

---

我真的不确定我能够使用多糟糕的伪随机数生成器，因为我正在制作Perlin噪声，所以唯一的要求是输出在视觉上看起来像Perlin噪声。我会阅读关于LCG的内容，感谢提供链接。 - with

还有一个https://dev59.com/-3VC5IYBdhLWcg3w1E7w SO问题，其中包含一些其他快速PRNG的想法，可能对您有用。 - uesp

那个 Stack Overflow 的链接非常有用 - 好主意。使用“world”种子来进行整数哈希，然后将该哈希结果应用为基本 LCG 的种子，似乎非常快速并且很可能完全满足我的需求。 - with

Answer 3

不，我不相信有这样的方法。对于某些随机数生成算法（例如线性同余生成器），原则上可以获取第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慢。

- Gareth McCaughan

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];
}

- Robert Levy