如何保留数据流的随机子集？

Question

我有一系列事件流经我的服务器.我不可能存储所有这些,但我希望能够定期处理其中的一些.所以,我想保留一个流的子集,它是我所见过的所有内容的随机抽样,但是上限为最大尺寸.

因此,对于每个新项目,我需要一个算法来决定是否应该将它添加到存储集,或者我是否应该丢弃它.如果我添加它,并且我已经达到极限,我需要一个算法来驱逐其中一个旧项目.

显然,只要我低于我的极限(只保存一切),这很容易.但是,一旦我超过这个限制,我怎样才能保持良好的随机抽样而不偏向旧物品或新物品？

谢谢,

Answer 1

这是一个常见的面试问题.

一种简单的方法是以概率k/n(或1,以较小者为准)保存第n个元素.如果需要删除元素以保存新样本,请逐出随机元素.

这为您提供了n个元素的均匀随机子集.如果你不知道n,你可以估计它并获得一个近似统一的子集.

Answer 2

这称为随机抽样.资料来源:http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

一个不错的解释/证据:http://propersubset.com/2010/04/choosing-random-elements.html

Answer 3

虽然本文并不是您正在寻找的内容，但它可能是您搜索的一个很好的起点。