Итеративный или ленивый отбор проб из коллектора

Я довольно хорошо знаком с использованием выборки резервуара для выборки из набора неопределенной длины за один проход по данным. Одним из ограничений этого подхода, на мой взгляд, является то, что он все еще требует прохождения через весь набор данных, прежде чем можно будет получить какие-либо результаты. Концептуально это имеет смысл, так как необходимо предоставить элементам во всей последовательности возможность заменить ранее встречавшиеся элементы для достижения однородного образца.

Есть ли способ быть в состоянии дать какие-то случайные результаты, прежде чем вся последовательность будет оценена? Я думаю о том, какой ленивый подход будет хорошо сочетаться с великолепной библиотекой itertools python. Возможно, это можно было бы сделать в пределах некоторой заданной погрешности? Я был бы признателен за любую обратную связь по этой идее!

Просто чтобы немного прояснить вопрос, эта диаграмма подводит итог моему пониманию компромиссов между потоковой и встроенной памятью различных методов выборки. То, что я хочу, это то, что попадает в категориявыборки потока , где мы заранее не знаем длину популяции.

Введите описание изображения здесь

Очевидно, что существует кажущееся противоречие в незнании априорной длины и все же получении однородной выборки, поскольку мы, скорее всего, будем смещать выборку в сторону начала популяции. Есть ли способ количественно оценить это смещение? Есть ли какие-то компромиссы? Есть ли у кого-нибудь умный алгоритм для решения этой проблемы?
2 7
python algorithm random-sample

2 ответа:

Если вы заранее знаете общее количество элементов, которые будут получены итерацией population, то можно получить элементы выборки population по мере их поступления (а не только после достижения конца). Если вы заранее не знаете размер популяции, это невозможно (так как вероятность любого элемента, находящегося в выборке, не может быть вычислена).

Вот быстрый генератор, который делает это: 

def sample_given_size(population, population_size, sample_size):
    for item in population:
        if random.random() < sample_size / population_size:
            yield item
            sample_size -= 1
        population_size -= 1

Обратите внимание, что генератор выдает элементы в том порядке, в котором они появляются в популяция (не в случайном порядке, как random.sample или большинство кодов выборки резервуаров), поэтому срез выборки не будет случайным подмножеством!

6

Если размер популяции известен до руки, не можете ли вы просто сгенерировать случайные "индексы" sample_size (в потоке) и использовать их для получения ленивой доходности? Вам не придется читать весь поток.

Например, если population_size равен 100, а sample_size равен 3, Вы генерируете случайный набор целых чисел от 1 до 100, скажем, вы получаете 10, 67 и 72. Теперь вы выделяете 10-й, 62-й и 72-й элементы потока и игнорируете остальные.

Наверное, я не понимаю вопроса.

0