algorithm - 如何存储未知大小的顺序呈现集合的样本？

Question

假设我想存储 N 个样本(每个样本占用内存的很大一部分)，这应该形成一个有代表性的集合，总共有 M>>N 个样本，这些样本按顺序呈现给我。事先不知道M，只能同时在内存中保存N个样本。

这里，有代表性，意味着M个样本中的每一个都应该有相等的概率被存储。

Answer 1

此问题称为 reservoir sampling并且有一个非常有效的 O(M) 时间，O(N) 空间算法。该算法的工作原理如下:在每个点上，“猜测”您要选择的 N 个元素。最初，选择前 N 个元素。然后，在看到序列的第 k 个元素后，在 1 和 k 之间选择一个随机数，包括 1 和 k。如果选择的数字在 1..N 范围内，则将索引的“猜测”项目替换为当前项目；否则什么也不做。您可以使用快速归纳论证证明这将随机均匀地对 N 个元素进行采样，并且一次传递数据。

希望这对您有所帮助!