7

给定一个一致播种的 Random：

Random r = new Random(0);

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

我的场景是通过r.Next(). 该应用程序偶尔会从任意索引处的数组中读取一个值。我想通过消除数组来优化内存使用，而是按需生成值。但是暴力破解r.Next()500 万次来模拟数组的第 500 万个索引比存储数组更昂贵。是否可以在没有 / 较少循环的情况下捷径到达 Nth .Next() 值？

4

4 回答 4

7

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

这个解决方法怎么样：

使随机数生成器的种子成为所需的索引，然后选择第一个生成的数字。这同样是“确定性的”，并为您提供了在 O(1) 空间中的广泛使用范围。

static int GetRandomNumber(int index)
{
    return new Random(index).Next();
}
于 2011-03-22T00:49:33.063 回答
2

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

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

于 2011-03-22T00:59:06.667 回答
1

不，我不相信有。对于某些 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 慢。

于 2011-03-22T00:54:36.347 回答
-1

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

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];
}
于 2011-03-22T01:10:56.007 回答