关于随机数序列的生成

Question

我对随机算法很陌生，我是通过读书来学习的。我正在阅读马克·艾伦·韦西斯()的一本书“数据结构和算法分析”。

假设我们只需要抛硬币，那么我们必须随机生成0或1。一种方法是检查系统时钟。时钟可能会将时间记录为一个整数，该整数计算自1970年1月1日以来的秒数(至少在Unix系统上如此)。然后我们可以使用最低位。问题是，如果需要随机数序列，这种方法就不能很好地工作。一秒是一段很长的时间，当程序运行时，时钟可能根本不会改变。即使以微秒为单位记录时间，如果程序自行运行，生成的数字序列也不会是随机的，因为每次调用程序时，对生成器的调用之间的时间基本上是相同的。我们看到，真正需要的是一个随机数序列。这些数字应该看起来是独立的。如果一枚硬币被抛出并出现正面，那么下一次抛硬币的可能性仍然是相同的:正面或反面。

下面是关于上述文本片段的问题。

1. 在上面的文字片段“我们可以使用最低位数的秒数”中，作者提到这是不工作的，因为一秒是很长的时间，时钟可能根本不会改变。我的问题是，为什么一秒是长时间，时钟每秒钟都会变化，在什么上下文中作者提到时钟不改变?请求帮助理解简单的例子。
2. 作者怎么提到，即使在微秒内，我们也不会得到随机数的序列？

谢谢!

Answer 1

1. 电脑速度很快。我已经过分简化了，但是如果您的时钟速度是用GHz测量的，它可以在1秒内完成数十亿次操作。相对而言，1秒是永恒，所以它是有可能不会改变的。
2. 如果您的程序正在进行正常操作，则不能保证在任意时间对时钟进行采样。因此，你不会得到一个随机数。

Answer 2

使用随机(或在本例中为伪随机)的程序通常在短时间内需要大量的随机数。这就是为什么简单地使用时钟不起作用的原因之一，因为系统时钟不会像您的代码请求新数字那样快速更新，因此qui很可能一次又一次地得到相同的结果，直到时钟发生变化。在Unix系统中，它可能更引人注目，因为通常获取时间的方法只会给出第二次精确性。即使是微秒也没有真正的帮助，因为计算机比现在快得多。

你要避免的第二个问题是伪随机值的线性依赖性。想象一下，你想在一个正方形里随机地放置一些点。你会选择x和y坐标。如果你的伪随机值是一个简单的线性序列(就像你从时钟中得到的一样)，你就会得到一条对角线，许多点在同一个地方聚集在一起。这不太管用。

作为最简单的伪随机数生成器之一，线性同余发生器也有类似的问题，尽管乍一看它并不那么明显。由于非常简单的公式

​

​

你仍然会得到相当可预测的结果，尽管只有当你选择3D空间中的点时，因为所有的数字都在一些不同的平面上(所有伪随机生成器在某个维度上都显示出的问题)：

​

​

Answer 3

别忘了，对一台电脑来说，一秒就可以是“永恒”。程序/算法通常在毫秒内执行。(1000秒。)

以下伪码：

for(int i = 0; i < 1000; i++)
   n = rand(0, 1000) 

用0到1000之间的随机数填充n一千次。在一台典型的机器上，这个脚本几乎立即执行。

通常只在开始时初始化种子：

以下伪码：

srand(time());
for(int i = 0; i < 1000; i++)
   n = rand(0, 1000) 

初始化种子一次，然后执行代码，生成一组看似随机的数字。然后，当您多次执行代码时，就会出现问题。假设代码在3毫秒内执行。然后，代码在3毫秒内再次执行，但两者都在同一秒钟内执行。结果是一组相同的数字。

关于第二点:作者可能假设一台快速计算机。THe以上问题仍然存在.