выборка из резервуара с постоянной памятью, O (k) возможно? - PullRequest
Новая
       47

выборка из резервуара с постоянной памятью, O (k) возможно?

0 голосов
/ 27 апреля 2018

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

Алгоритм, который я собирался использовать, в основном таков: 

for each element in input stream
    if random()<k/n
        decrement k
        output element
        if k = 0
            halt
        end if
    end if
    decrement n
end for

Функция random () генерирует число из [0..1) по случайному распределению, и я верю, что принцип работы алгоритма прост.

Хотя этот алгоритм может завершаться рано, когда он выбирает последний элемент, в целом алгоритм все еще приблизительно равен O (n). Сначала казалось, что он работает как задумано (выводит примерно равномерно распределенные, но все еще случайные элементы из входного потока), но я думаю, что может быть неравномерная тенденция выбирать более поздние элементы, когда k намного меньше, чем n. Я не уверен в этом, однако ... поэтому я был бы признателен, если бы знал точно так или иначе. Мне также интересно, существует ли более быстрый алгоритм. Очевидно, что поскольку необходимо сгенерировать k элементов, алгоритм не может быть быстрее O (k). Для решения O (k) можно предположить существование функции skip (x), которая может пропустить x элементов во входном потоке за O (1) время (но не может пропустить назад). Однако я все же хотел бы сохранить требование не требовать дополнительной памяти.

1 Ответ

0 голосов
/ 27 апреля 2018

Если это реальный поток, вам нужно O(n) время для его сканирования.

Ваш существующий алгоритм хорош. (Я ошибался раньше.) Вы можете по индукции доказать, что вероятность того, что вы не выбрали первый элемент в i попытках, равна 1 - i/n = (n-i)/n. Первое, что верно для i=0 осмотром. Теперь, если вы не выбрали его в i -х попытках, вероятность того, что следующий выберет его, равна 1/(n-i). И тогда шансы выбрать его на i+1 -ой попытке - ((n-i)/n) * (1/(n-i)) = 1/n. Это означает, что вероятность не выбрать его в первый раз i+1 равна 1 - i/n - 1/n = 1 - (i+i)/n. Это завершает индукцию. И поэтому вероятность выбора первого элемента в первых k попытках - это вероятность того, что он не был выбран, или 1 - (n - k/n) = k/n.

Но что, если у вас есть O(1) доступ к любому элементу? Обратите внимание, что выбор k - это то же самое, что и выбор n-k. Таким образом, без ограничения общности мы можем предположить, что k <= n/2. Это означает, что мы можем использовать рандомизированный алгоритм, подобный этому: 

chosen = set()
count_chosen = 0
while count_chosen < k:
    choice = random_element(stream)
    if choice not in chosen:
        chosen.add(choice)
        count_chosen = count_chosen + 1

Набор будет O(k) пробел, и, поскольку вероятность того, что каждый случайный выбор будет для вас новым, составляет не менее 0.5, ожидаемое время выполнения не хуже, чем 2k вариантов.

...