我有一个大小为 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 个元素(但不能向后跳过)。但是,我仍然希望保留不需要任何额外内存的要求。
最佳答案
如果是真实流,需要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
差选择。
关于algorithm - 常量内存库采样,O(k) 可能吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50065008/