假设我想存储 N 个样本(每个样本占用内存的很大一部分),这应该形成一个有代表性的集合,总共有 M>>N 个样本,这些样本按顺序呈现给我。事先不知道M,只能同时在内存中保存N个样本。
这里,有代表性,意味着M个样本中的每一个都应该有相等的概率被存储。
最佳答案
此问题称为 reservoir sampling并且有一个非常有效的 O(M) 时间,O(N) 空间算法。该算法的工作原理如下:在每个点上,“猜测”您要选择的 N 个元素。最初,选择前 N 个元素。然后,在看到序列的第 k 个元素后,在 1 和 k 之间选择一个随机数,包括 1 和 k。如果选择的数字在 1..N 范围内,则将索引的“猜测”项目替换为当前项目;否则什么也不做。您可以使用快速归纳论证证明这将随机均匀地对 N 个元素进行采样,并且一次传递数据。
希望这对您有所帮助!
关于algorithm - 如何存储未知大小的顺序呈现集合的样本?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11089542/