从一个非常长的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}来自^代码。在

Answer 2

因为您知道iterable返回的数据的长度，所以可以使用xrange()快速生成iterable的索引。然后可以运行iterable，直到获取所有数据：

import random

def sample(it, length, k):
    indices = random.sample(xrange(length), k)
    result = [None]*k
    for index, datum in enumerate(it):
        if index in indices:
            result[indices.index(index)] = datum
    return result

print sample(iter("abcd"), 4, 2)

另一种方法是使用“算法R”实现保留采样：

^{pr2}$

注意，算法R没有为结果提供随机顺序。在给定的示例中，'b'永远不会在结果中的'a'之前。

Answer 3

如果您需要一个固定频率的原始迭代器的子集（即，如果生成器生成10000个数字，您希望“统计地”生成100个数字，如果它生成1000000个数字，则需要10000个数字—始终为1%），那么您应该将迭代器包装在一个构造中，生成概率为1%的内循环结果。在

因此，我想您需要的是一个固定数量的样本，这些样本来自于一个未知基数的源，就像您提到的Perl算法一样。在

您可以将迭代器包装在一个拥有自己的小内存的结构中，以便跟踪库，并以降低概率的方式循环它。在

import random

def reservoir(iterator, size):
    n = size
    R = iterator[0:n]
    for e in iterator:
        j = random.randint(0, n-1)
        n = n + 1
        if (j < size):
                R[j] = e
    return R

所以

^{pr2}$

可能会打印出来

[656, 774, 828]

我已经尝试生成100万发子弹，并用这个滤波器比较了三列的分布（我预期是高斯分布）。在

#                get first column and clean it
python file.py | cut -f 1 -d " " | tr -cd "0-9\n" \
    | sort | uniq -c | cut -b1-8 | tr -cd "0-9\n" | sort | uniq -c

虽然还不是真正的高斯分布，但在我看来已经足够好了。在