从流中随机收集项目

假设我有一个输入流，我不知道它中有多少项。当我从流中收集物品时，我随机存储了一些物品。假设我必须存储1,000个项目，并且流中的项目远远超过1,000 是否有一个很好的算法，可以从流中随机收集项目，并且项目尽可能均匀地分布在流的长度中？从流中随机收集项目

来源

2015-09-10 Jade Tang

不，你不能得到均匀分布，除非事先知道流中有多少物品。

假设流有10,000个项目。要获得1,000个均匀分配的物品，您应该收集每十个物品。

假设流包含100,000个项目。要获得1,000个均匀分布的物品，您应该收集每一百项物品。

但是，您不能区分这两种情况，直到您到达流的末尾，此时更改您的收集频率为时已晚。如果您开始收集每十个项目，那么您最终可能会收集1,000个收集的项目，而您仍然有90,000个项目要留在流中。如果您开始收集每百项物品，则可能会达到流的末尾，而您的配额数量不足900个。

来源

2015-09-10 13:40:16 Kevin

如果存储选择的项目，那么你就可以随机选择具有均匀分布使用Reservoir sampling算法从k个流项目

for first k elements of stream: 
    store element in A array 

for every next (ith) element: 
    generate random indx in range [0, i) 
    if indx < k 
     replace A[indx] with current element

来源

2015-09-10 13:56:32 MBo

我知道水库采样算法，但我的情况略有不同，这里是因为我可以” t首先存储第一个k元素。当每个元素到达时，它将被存储或丢弃。 –

但是......你写过关于存储他们......好吧，那么凯文的答案是给你的。 – MBo

从流中随机收集项目

回答

相关问题