0

下面是来自 Knuth 的用于水库采样的伪代码（如何k从一组数字中选择数字n，确保每个数字具有相同的概率）。

Init：一个大小为：<code>k的容器。

for i = k+1 to N
    M = random(1, i);

    if (M < k) // should this be if (M <= k)
       SWAP the Mth value and ith value
    end if    
end for

从这段代码中，概率M < K是(k-1)/i，不是k/i，所以我认为if循环体中的语句应该是if (M < =k)。我试图测试它们之间的区别，但我没有得到任何结果。

4

2 回答 2

4

你说的对。但是，您的代码没有正确实现算法 R。错误是您的（或编写此代码的人），而不是 Knuth 的 ;-)

引自 Knuth（计算机编程艺术第 2 卷，1998 年第 3 版，第 144 页）：

...如果我们事先不知道 N 的值，就会出现问题，因为 N 的精确值在算法 S 中至关重要。假设我们想从文件中随机选择 n 个项目，而不知道确切有多少存在于该文件中。我们可以先遍历并计算记录，然后再进行第二次选择；但通常最好在第一次通过时对原始项目中的 m > n 进行采样，其中 m 远小于 N，因此在第二次通过时只需要考虑 m 个项目。当然，诀窍是这样做的方式是最终结果是原始文件的真正随机样本。

由于我们不知道输入何时结束，我们必须跟踪到目前为止看到的输入记录的随机样本，因此始终为结束做好准备。当我们读取输入时，我们将构建一个“reservoir”，其中仅包含先前样本中出现的记录。前 n 条记录总是进入存储库。当输入第 (t + 1) 条记录时，对于 t>n，我们将在内存中有一个包含 n 个索引的表，指向我们从前 t 条中选择的记录。问题是在 t 增加 1 的情况下保持这种情况，即从现在已知存在的 t + 1 条记录中找到一个新的随机样本。不难看出，我们应该以概率 n/(t + 1) 将新记录包含在新样本中，

因此，以下过程可以完成这项工作：

算法 R（水库采样）。在给定 n > 0 的情况下，从大小 > n 的文件中随机选择 n 条记录。名为“reservoir”的辅助文件包含作为最终样本候选的所有记录。该算法使用不同索引表I [j] 表示 1 < j < n，每个索引都指向存储库中的一个记录。

R1。【初始化】输入前n条记录，复制到库中。对于 1 < j < n，设置I [j] ← j，并设置 t ← m ← n。（如果被采样的文件少于n条记录，当然需要中止算法并报告失败。在此算法期间，索引I [1]，...，I [n]指向当前样本；m 是存储库的大小；t 是到目前为止处理的输入记录数。）

R2。[文件结束？] 如果没有更多记录要输入，转到步骤 R6。

R3。[生成并测试。] 将 t 增加 1，然后生成一个介于 1 和 t（含）之间的随机整数 M。如果 M > n，则转到 R5。

R4。【添加到reservoir.】将输入文件的下一条记录复制到reservoir，m加1，设置I[M]←m。（先前由 I[M] 指向的记录在样本中被新记录替换。）回到 R2。

R5。[Skip.] 跳过输入文件的下一条记录（不包含在库中），返回步骤R2。

R6。[第二遍] 对I表条目进行排序，使得I [1] < ... < I [n]; 然后通过水库，将具有这些索引的记录复制到用于保存最终样本的输出文件中。

算法 R 的伪代码如下所示：

for j= 1 to n
    Reservoir[j]= File.GetNext()
    I[j]= j

t=n // number of input records so far
m=n // size of the reservoir

while not File.EOF()
    x= File.GetNext()
    t++
    M= Random(1..t)
    if (M<=n)
        m++
        Reservoir[m]= x
        I[M]= m

Sort(I[1..n])

for j= 1 to n
    Output[j]= Reservoir[I[j]]
于 2013-07-14T20:22:35.577 回答
3

是的，应该是<=。这是基于查看wikipedia中的代码，并通过这个答案工作，这是一个很好的解释，为什么超集中的每个数字都有相同的出现机会。然而，我会毫不犹豫地声称 Knuth 有一个错误！

于 2013-07-14T12:14:23.557 回答