algorithm - 常量内存库采样，O(k) 可能吗？

Question

我有一个大小为 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 个元素(但不能向后跳过)。但是，我仍然希望保留不需要任何额外内存的要求。

Answer 1

如果是真实流，需要O(n)是时候扫描它了。

您现有的算法很好。 (我之前弄错了。)你可以通过归纳法证明你没有选择 i 中的第一个元素的概率。尝试是 1 - i/n = (n-i)/n .首先对于 i=0 是正确的通过检查。现在，如果您还没有在 i 中选择它第 th 次尝试，下一个选择它的几率是 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 中选择第一个元素的几率tries 是没有选择它的几率，或者 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差选择。