蟒与发电机/迭代/迭代随机样品(Python random sample with a genera

你知道，如果有办法让Python的random.sample与发电机对象的工作。 我想从一个非常大的文本语料库得到一个随机样本。 问题是， random.sample()引发了以下错误。

TypeError: object of type 'generator' has no len()

我在想，也许有来自一些这样的一些方式itertools但未能找到一点搜索的东西。

一个有点组成例如：

import random
def list_item(ls):
    for item in ls:
        yield item

random.sample( list_item(range(100)), 20 )

---

---

UPDATE

---

按照MartinPieters的要求，我做了目前提出了三种方法的一些具体时机。 结果如下。

Sampling 1000 from 10000
Using iterSample 0.0163 s
Using sample_from_iterable 0.0098 s
Using iter_sample_fast 0.0148 s

Sampling 10000 from 100000
Using iterSample 0.1786 s
Using sample_from_iterable 0.1320 s
Using iter_sample_fast 0.1576 s

Sampling 100000 from 1000000
Using iterSample 3.2740 s
Using sample_from_iterable 1.9860 s
Using iter_sample_fast 1.4586 s

Sampling 200000 from 1000000
Using iterSample 7.6115 s
Using sample_from_iterable 3.0663 s
Using iter_sample_fast 1.4101 s

Sampling 500000 from 1000000
Using iterSample 39.2595 s
Using sample_from_iterable 4.9994 s
Using iter_sample_fast 1.2178 s

Sampling 2000000 from 5000000
Using iterSample 798.8016 s
Using sample_from_iterable 28.6618 s
Using iter_sample_fast 6.6482 s

因此，原来的array.insert具有严重的缺陷，当涉及到大的样本量。 该代码我用时间的方法

from heapq import nlargest
import random
import timeit


def iterSample(iterable, samplesize):
    results = []
    for i, v in enumerate(iterable):
        r = random.randint(0, i)
        if r < samplesize:
            if i < samplesize:
                results.insert(r, v) # add first samplesize items in random order
            else:
                results[r] = v # at a decreasing rate, replace random items

    if len(results) < samplesize:
        raise ValueError("Sample larger than population.")

    return results

def sample_from_iterable(iterable, samplesize):
    return (x for _, x in nlargest(samplesize, ((random.random(), x) for x in iterable)))

def iter_sample_fast(iterable, samplesize):
    results = []
    iterator = iter(iterable)
    # Fill in the first samplesize elements:
    for _ in xrange(samplesize):
        results.append(iterator.next())
    random.shuffle(results)  # Randomize their positions
    for i, v in enumerate(iterator, samplesize):
        r = random.randint(0, i)
        if r < samplesize:
            results[r] = v  # at a decreasing rate, replace random items

    if len(results) < samplesize:
        raise ValueError("Sample larger than population.")
    return results

if __name__ == '__main__':
    pop_sizes = [int(10e+3),int(10e+4),int(10e+5),int(10e+5),int(10e+5),int(10e+5)*5]
    k_sizes = [int(10e+2),int(10e+3),int(10e+4),int(10e+4)*2,int(10e+4)*5,int(10e+5)*2]

    for pop_size, k_size in zip(pop_sizes, k_sizes):
        pop = xrange(pop_size)
        k = k_size
        t1 = timeit.Timer(stmt='iterSample(pop, %i)'%(k_size), setup='from __main__ import iterSample,pop')
        t2 = timeit.Timer(stmt='sample_from_iterable(pop, %i)'%(k_size), setup='from __main__ import sample_from_iterable,pop')
        t3 = timeit.Timer(stmt='iter_sample_fast(pop, %i)'%(k_size), setup='from __main__ import iter_sample_fast,pop')

        print 'Sampling', k, 'from', pop_size
        print 'Using iterSample', '%1.4f s'%(t1.timeit(number=100) / 100.0)
        print 'Using sample_from_iterable', '%1.4f s'%(t2.timeit(number=100) / 100.0)
        print 'Using iter_sample_fast', '%1.4f s'%(t3.timeit(number=100) / 100.0)
        print ''

我也跑了一个测试，以检查所有的方法确实不采取发电机的无偏差的样本。 因此，对于所有的方法我采样1000从元件10000 100000倍和计算每个项目的发生的平均频率，其中原来是人口~.1正如人们所期望的所有三种方法。

Answer 1:

虽然马亭皮特斯的答案是正确的，它确实慢下来时samplesize变大，因为使用list.insert在一个循环中可能有二次的复杂性。

这里，在我看来，蜜饯同时提高性能均匀性的选择：

def iter_sample_fast(iterable, samplesize):
    results = []
    iterator = iter(iterable)
    # Fill in the first samplesize elements:
    try:
        for _ in xrange(samplesize):
            results.append(iterator.next())
    except StopIteration:
        raise ValueError("Sample larger than population.")
    random.shuffle(results)  # Randomize their positions
    for i, v in enumerate(iterator, samplesize):
        r = random.randint(0, i)
        if r < samplesize:
            results[r] = v  # at a decreasing rate, replace random items
    return results

所不同的慢慢开始显示samplesize上面的值10000 。 与呼叫次数(1000000, 100000)

• iterSample：5.05s
• iter_sample_fast：2.64s

Answer 2:

你不能。

你有两个选择：读取整个发电机到一个列表，然后从该列表样，或使用一个读发生器之一，从挑选样品的方法：

import random

def iterSample(iterable, samplesize):
    results = []

    for i, v in enumerate(iterable):
        r = random.randint(0, i)
        if r < samplesize:
            if i < samplesize:
                results.insert(r, v) # add first samplesize items in random order
            else:
                results[r] = v # at a decreasing rate, replace random items

    if len(results) < samplesize:
        raise ValueError("Sample larger than population.")

    return results

这种方法调整的下一个项目是基于项目的迭代次数至今部分样品的机会。 它并不需要持有超过samplesize内存中的数据。

该解决方案是不矿; 它是作为的一部分提供在这里SO另一个答案 。

Answer 3:

只为它赫克，这里是一个一行是样本k个元素，而不从为O产生的n项替换（N LG的K）时间：

from heapq import nlargest

def sample_from_iterable(it, k):
    return (x for _, x in nlargest(k, ((random.random(), x) for x in it)))

Answer 4:

我想从一个非常大的文本语料库得到一个随机样本。

你优秀的综合答案目前显示为胜利iter_sample_fast(gen, pop) 。 不过，我试过的Katriel的建议random.sample(list(gen), pop) -它通过比较的速度极快！

def iter_sample_easy(iterable, samplesize):
    return random.sample(list(iterable), samplesize)

Sampling 1000 from 10000
Using iter_sample_fast 0.0192 s
Using iter_sample_easy 0.0009 s

Sampling 10000 from 100000
Using iter_sample_fast 0.1807 s
Using iter_sample_easy 0.0103 s

Sampling 100000 from 1000000
Using iter_sample_fast 1.8192 s
Using iter_sample_easy 0.2268 s

Sampling 200000 from 1000000
Using iter_sample_fast 1.7467 s
Using iter_sample_easy 0.3297 s

Sampling 500000 from 1000000
Using iter_sample_easy 0.5628 s

Sampling 2000000 from 5000000
Using iter_sample_easy 2.7147 s

---

现在，当你的阴茎变得非常大 ，物化整个迭代到一个list将使用大得惊人的内存。 但是，我们仍然可以利用Python的速度超炫的烦躁，如果我们能块了问题 ：基本上，我们选择一个CHUNKSIZE是“相当小”，做random.sample上的小块，然后用random.sample再次它们合并起来。 我们只需要得到边界条件的权利。

我看怎么做，如果长度list(iterable)是的整数倍CHUNKSIZE ，而不是比我的大samplesize*CHUNKSIZE ：

def iter_sample_dist_naive(iterable, samplesize):
    CHUNKSIZE = 10000
    samples = []
    it = iter(iterable)
    try:
        while True:
            first = next(it)
            chunk = itertools.chain([first], itertools.islice(it, CHUNKSIZE-1))
            samples += iter_sample_easy(chunk, samplesize)
    except StopIteration:
        return random.sample(samples, samplesize)

然而，上面的代码产生非均匀的采样时len(list(iterable)) % CHUNKSIZE != 0 ，以及它运行的存储器中作为len(list(iterable)) * samplesize / CHUNKSIZE变为“非常大”。 修复这些错误是我上面的薪酬等级，我很害怕，而是一个解决方案中描述的这个博客帖子 ，听起来很有道理的我。 （搜索术语：“分布式随机抽样”，“分布式储存器采样”。）

Sampling 1000 from 10000
Using iter_sample_fast 0.0182 s
Using iter_sample_dist_naive 0.0017 s
Using iter_sample_easy 0.0009 s

Sampling 10000 from 100000
Using iter_sample_fast 0.1830 s
Using iter_sample_dist_naive 0.0402 s
Using iter_sample_easy 0.0103 s

Sampling 100000 from 1000000
Using iter_sample_fast 1.7965 s
Using iter_sample_dist_naive 0.6726 s
Using iter_sample_easy 0.2268 s

Sampling 200000 from 1000000
Using iter_sample_fast 1.7467 s
Using iter_sample_dist_naive 0.8209 s
Using iter_sample_easy 0.3297 s

---

当我们真正取胜时samplesize相对非常小，是len(list(iterable))

Sampling 20 from 10000
Using iterSample 0.0202 s
Using sample_from_iterable 0.0047 s
Using iter_sample_fast 0.0196 s
Using iter_sample_easy 0.0001 s
Using iter_sample_dist_naive 0.0004 s

Sampling 20 from 100000
Using iterSample 0.2004 s
Using sample_from_iterable 0.0522 s
Using iter_sample_fast 0.1903 s
Using iter_sample_easy 0.0016 s
Using iter_sample_dist_naive 0.0029 s

Sampling 20 from 1000000
Using iterSample 1.9343 s
Using sample_from_iterable 0.4907 s
Using iter_sample_fast 1.9533 s
Using iter_sample_easy 0.0211 s
Using iter_sample_dist_naive 0.0319 s

Sampling 20 from 10000000
Using iterSample 18.6686 s
Using sample_from_iterable 4.8120 s
Using iter_sample_fast 19.3525 s
Using iter_sample_easy 0.3162 s
Using iter_sample_dist_naive 0.3210 s

Sampling 20 from 100000000
Using iter_sample_easy 2.8248 s
Using iter_sample_dist_naive 3.3817 s

Answer 5:

如果项的迭代器中的数量是已知的（由别处计数的项目），另一种方法是：

def iter_sample(iterable, iterlen, samplesize):
    if iterlen < samplesize:
        raise ValueError("Sample larger than population.")
    indexes = set()
    while len(indexes) < samplesize:
        indexes.add(random.randint(0,iterlen))
    indexesiter = iter(sorted(indexes))
    current = indexesiter.next()
    ret = []
    for i, item in enumerate(iterable):
        if i == current:
            ret.append(item)
            try:
                current = indexesiter.next()
            except StopIteration:
                break
    random.shuffle(ret)
    return ret

我觉得这是更快，特别是当sampsize是相对于iterlen小。 当整个或接近整个，样品要求但是，也有问题。

iter_sample（iterlen = 10000，采样大小= 100）时间：（1， '毫秒'）iter_sample_fast（iterlen = 10000，采样大小= 100）时间：（15， '毫秒'）

iter_sample（iterlen = 1000000，采样大小= 100）时：（65， '毫秒'）iter_sample_fast（iterlen = 1000000，采样大小= 100）时间：（1477年， '毫秒'）

iter_sample（iterlen = 1000000，采样大小= 1000）的时间：（64， '毫秒'）iter_sample_fast（iterlen = 1000000，采样大小= 1000）的时间：（1459， '毫秒'）

iter_sample（iterlen = 1000000，采样大小= 10000）时间：（86， '毫秒'）iter_sample_fast（iterlen = 1000000，采样大小= 10000）时间：（1480， '毫秒'）

iter_sample（iterlen = 1000000，采样大小= 100000）时间：（388， '毫秒'）iter_sample_fast（iterlen = 1000000，采样大小= 100000）时间：（1521， '毫秒'）

iter_sample（iterlen = 1000000，采样大小= 1000000）时间：（25359， '毫秒'）iter_sample_fast（iterlen = 1000000，采样大小= 1000000）时间：（2178， '毫秒'）

Answer 6:

最快的方法，直到证明并非如此，当你有关于发电机多久（和将渐近均匀分布）的想法：

def gen_sample(generator_list, sample_size, iterlen):
    num = 0
    inds = numpy.random.random(iterlen) <= (sample_size * 1.0 / iterlen)
    results = []
    iterator = iter(generator_list)
    gotten = 0
    while gotten < sample_size: 
        try:
            b = iterator.next()
            if inds[num]: 
                results.append(b)
                gotten += 1
            num += 1    
        except: 
            num = 0
            iterator = iter(generator_list)
            inds = numpy.random.random(iterlen) <= ((sample_size - gotten) * 1.0 / iterlen)
    return results

它既是最快的小迭代以及庞大的迭代（大概都在随后之间）

# Huge
res = gen_sample(xrange(5000000), 200000, 5000000)
timing: 1.22s

# Small
z = gen_sample(xrange(10000), 1000, 10000) 
timing: 0.000441    

文章来源: Python random sample with a generator / iterable / iterator