迭代或延迟储层取样

Question

我很熟悉用储层取样法从一组未确定长度的数据中取样。在我看来，这种方法的一个局限性是，在返回任何结果之前，它仍然需要传递整个数据集。从概念上讲，这是有意义的，因为我们必须允许整个序列中的项目有机会替换以前遇到的项目，以获得统一的样本。在

在整个序列被评估之前，有没有一种方法可以产生一些随机结果？我在想一种懒散的方法，它很适合python伟大的itertools库。也许这可以在一定的误差容限内完成？如果您能对我的想法提出任何反馈意见，我将不胜感激！在

为了稍微澄清一下这个问题，这个图表总结了我对不同采样技术的内存和流的权衡的理解。我想要的是属于流抽样的一类，我们事先不知道种群的长度。在

显然，在事先不知道长度的情况下，仍然得到一个统一的样本，这似乎是一个矛盾，因为我们很可能会将样本偏向种群的开始。有没有办法量化这种偏见？是否需要进行权衡？有谁有一个聪明的算法来解决这个问题吗？在

Answer 1

如果事先知道种群大小，你不能生成样本大小的随机“指数”（在流中）并用它来做一个懒惰的产量吗？你不必阅读整个流。在

例如，如果population_size为100，sample_size为3，则生成一个从1到100的随机整数集，比如得到10、67和72。在

现在您将得到流的第10、62和72个元素，而忽略其余元素。在

我想我不明白这个问题。在

Answer 2

如果您事先知道iterable population将产生的项目总数，那么当您找到一个{}的样本时，就有可能产生这些项目（不仅仅是在到达末尾之后）。如果你事先不知道总体规模，这是不可能的（因为样本中任何项目的概率都无法计算）。在

下面是一个快速生成器，它可以做到：

def sample_given_size(population, population_size, sample_size):
    for item in population:
        if random.random() < sample_size / population_size:
            yield item
            sample_size -= 1
        population_size -= 1

请注意，生成器按项目在总体中出现的顺序生成项目（不是按随机顺序，如random.sample或大多数储层采样代码），因此样本的一部分将不是随机子样本！在