Случайный образец Python с итерационным итератором генератора

Знаете ли вы, есть ли способ заставить 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, как и следовало ожидать для всех трех методов.

Ответы

Ответ 1

Хотя ответ Martijn Pieters верен, он замедляется, когда 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

Ответ 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.

Ответ 3

Просто для этого, здесь однострочный, который отображает k элементов без замены из n элементов, сгенерированных в O (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)))

Ответ 4

Если количество элементов в итераторе известно (в другом месте, подсчитывающем элементы), другой подход:

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, samplesize = 100) time: (1, 'ms') iter_sample_fast (iterlen = 10000, samplesize = 100) time: (15, 'ms')

iter_sample (iterlen = 1000000, samplesize = 100) time: (65, 'ms') iter_sample_fast (iterlen = 1000000, samplesize = 100) time: (1477, 'ms')

iter_sample (iterlen = 1000000, samplesize = 1000) time: (64, 'ms') iter_sample_fast (iterlen = 1000000, samplesize = 1000) time: (1459, 'ms')

iter_sample (iterlen = 1000000, samplesize = 10000) time: (86, 'ms') iter_sample_fast (iterlen = 1000000, samplesize = 10000) time: (1480, 'ms')

iter_sample (iterlen = 1000000, samplesize = 100000) time: (388, 'ms') iter_sample_fast (iterlen = 1000000, samplesize = 100000) time: (1521, 'ms')

iter_sample (iterlen = 1000000, samplesize = 1000000) time: (25359, 'ms') iter_sample_fast (iterlen = 1000000, samplesize = 1000000) time: (2178, 'ms')

Ответ 5

Самый быстрый метод, пока не будет доказано обратное, если у вас есть представление о том, как долго генератор (и будет асимптотически равномерно распределен):

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