从一个非常长的iterable中随机抽取的样本，在python中

Question

我有一个很长的python生成器，我想通过随机选择值的子集来“精简”它。不幸的是，random.sample()不能处理任意的iterable。显然，它需要一些支持len()操作的东西（也许还有对序列的非顺序访问，但这并不清楚）。我不想建立一个庞大的清单，只是为了把它精简。在

事实上，在不知道序列长度的情况下，一次从序列中均匀采样是可能的——在Programming perl中有一个很好的算法可以做到这一点（编辑：“油藏采样”，谢谢@user2357112！）。但是有人知道有一个标准的python模块提供这个功能吗？在

问题演示（Python3）

>>> import itertools, random
>>> random.sample(iter("abcd"), 2)
...
TypeError: Population must be a sequence or set.  For dicts, use list(d).

在Python 2上，错误更加透明：

^{pr2}$

如果没有random.sample()的替代方案，我会试试运气，将生成器包装到一个提供__len__方法的对象中（我可以提前找到长度）。所以我会接受一个明确的答案。在

Answer 1

使用O(n)算法Rhttps://en.wikipedia.org/wiki/Reservoir_sampling，从iterable中选择k随机元素：

import itertools
import random

def reservoir_sample(iterable, k):
    it = iter(iterable)
    if not (k > 0):
        raise ValueError("sample size must be positive")

    sample = list(itertools.islice(it, k)) # fill the reservoir
    random.shuffle(sample) # if number of items less then *k* then
                           #   return all items in random order.
    for i, item in enumerate(it, start=k+1):
        j = random.randrange(i) # random [0..i)
        if j < k:
            sample[j] = item # replace item with gradually decreasing probability
    return sample

示例：

^{pr2}$

{cd4{2}来自^代码。在