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

Question

我有一系列事件流经我的服务器。存储所有这些对我来说是不可行的，但我希望能够定期地汇总处理其中的一些。所以，我想保留流的一个子集，它是我所见过的所有内容的随机采样，但限制为最大大小。

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

显然，这很容易，只要我低于我的极限(只需保存所有内容)。但是，一旦超过该限制，我如何才能保持良好的随机抽样而不偏向于旧项目或新项目？

谢谢，

Answer 1

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

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

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