来自python中非常长的迭代的随机样本

Question

我有一个很长的python生成器,我想通过随机选择一个值的子集来"稀释".不幸的是,random.sample()不能使用任意迭代.显然,它需要支持len()操作的东西(可能是对序列的非顺序访问,但这一点并不清楚).而且我不想建立一个庞大的列表,所以我可以把它简化.

事实上,有可能在一次通过中均匀地从序列中采样,而不知道它的长度 - 这就是一个很好的算法Programming perl(编辑:"水库采样",谢谢@ user2357112!).但有没有人知道提供此功能的标准python模块？

演示问题(Python 3)

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

在Python 2上,错误更透明:

Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    random.sample(iter("abcd"), 2)
  File "/usr/local/Cellar/python/2.7.9/Frameworks/Python.framework/Versions/2.7/lib/python2.7/random.py", line 321, in sample
    n = len(population)
TypeError: object of type 'iterator' has no len()

如果没有别的选择random.sample(),我会试着把发电机包装成一个提供__len__方法的对象(我可以事先找出它的长度).所以我会接受一个答案,说明如何干净利落地做到这一点.

Answer 1

由于您知道iterable返回的数据的长度,因此您可以使用xrange()快速生成可迭代的索引.然后你就可以运行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"进行重新采样的实现:

import random

def R(it, k):
    '''https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_R'''
    it = iter(it)
    result = []
    for i, datum in enumerate(it):
        if i < k:
            result.append(datum)
        else:
            j = random.randint(0, i-1)
            if j < k:
                result[j] = datum
    return result

print R(iter("abcd"), 2)

请注意,算法R不为结果提供随机顺序.在给出的示例中,结果中'b'永远不会'a'出现.