假设我想存储 N 个样本（每个样本占用了很大一部分内存），这应该形成一个由总共 M>>N 个样本按顺序呈现给我的代表性集合。我事先不知道M，只能同时在内存中保存N个样本。
在这里，代表性意味着 M 个样本中的每个样本都应该具有相同的存储概率。
问问题
56 次
这个问题被称为储层采样，并且有一个非常有效的 O(M) 时间、O(N) 空间算法。该算法的工作原理如下：在每个点上，保持“猜测”您要选择哪些 N 个元素。最初，选择前 N 个元素。然后，在看到序列的第 k 个元素后，在 1 和 k 之间选择一个随机数，包括 1 和 k。如果选择的数字在 1..N 范围内，则将索引的“猜测”项替换为当前项；否则什么也不做。您可以使用快速归纳论证表明这将随机均匀地对 N 个元素进行采样，并且一次遍历数据。
希望这可以帮助！