1

我有一个大小为 n 的输入流，我想生成一个大小为 k 的输出流，其中包含输入流的不同随机元素，而不需要为样本选择的元素提供任何额外的内存。

我要使用的算法基本上如下：

for each element in input stream
    if random()<k/n
        decrement k
        output element
        if k = 0
            halt
        end if
    end if
    decrement n
end for

函数 random() 在随机分布上从 [0..1) 生成一个数字，我相信该算法的操作原理很简单。

尽管该算法在选择最后一个元素时可以提前终止，但通常该算法仍约为 O(n)。起初它似乎按预期工作（从输入流中输出大致均匀分布但仍然是随机的元素），但我认为当 k 远小于 n 时，可能会有一种不均匀的倾向来选择后面的元素。但是，我不确定这一点......所以我很高兴知道一种或另一种方式。我也想知道是否存在更快的算法。显然，由于必须生成 k 个元素，因此算法不能比 O(k) 快。对于 O(k) 解决方案，可以假设存在一个函数 skip(x)，它可以在 O(1) 时间内跳过输入流中的 x 个元素（但不能向后跳过）。

4

1 回答 1

0

如果它是一个真实的流，你需要O(n)时间来扫描它。

您现有的算法很好。（我之前弄错了。）你可以通过归纳证明你没有在i尝试中选择第一个元素的概率是1 - i/n = (n-i)/n。首先，i=0通过检查是正确的。现在，如果您在 th 尝试中没有选择它i，那么下一个选择它的几率是1/(n-i)。i+1然后在第一次尝试时选择它的几率是((n-i)/n) * (1/(n-i)) = 1/n。这意味着第一次不选择它的几率i+1是1 - i/n - 1/n = 1 - (i+i)/n。这样就完成了归纳。因此，在第一次k尝试中选择第一个元素的几率是没有选择它的几率，或者1 - (n - k/n) = k/n.

但是，如果您可以O(1)访问任何元素怎么办？请注意，选择k采取与选择n-k离开相同。所以不失一般性，我们可以假设k <= n/2。这意味着我们可以使用这样的随机算法：

chosen = set()
count_chosen = 0
while count_chosen < k:
    choice = random_element(stream)
    if choice not in chosen:
        chosen.add(choice)
        count_chosen = count_chosen + 1

该集合将是O(k)空间，并且由于每个随机选择对您来说是新的概率至少是0.5，因此预期的运行时间不会比2k选择差。

于 2018-04-27T16:36:41.310 回答