Выберите случайный предмет из потока в пространстве O (1)

Question

Выберите элемент из потока случайным образом с равномерной вероятностью, используя постоянное пространство

Поток обеспечивает следующие операции:

class Stream:

  def __init__(self, data):
    self.data = list(data)

  def read(self):
    if not self.data:
      return None

    head, *self.data = self.data
    return head

  def peek(self):
    return self.data[0] if self.data else None

Элементы в потоке (т.е. элементыdata) имеют постоянный размер, и ни один из них не равен None, поэтому None сигнализирует об окончании потока.Длина потока может быть изучена только при использовании всего потока.И обратите внимание, что при подсчете количества элементов расходуется O (log n) пробел.

Я считаю, что нет способа равномерно выбрать элемент из потока случайным образомиспользуя O (1) пробел .

Может кто-нибудь (dis) доказать это?

Answer 1

в постоянном пространстве? Конечно, Отбор проб резервуара , постоянное пространство, линейное время

Некоторый слегка проверенный код

import numpy as np

def stream(size):
    for k in range(size):
        yield k

def resSample(ni, s):
    ret = np.empty(ni, dtype=np.int64)

    k = 0
    for k, v in enumerate(s):
        if k < ni:
            ret[k] = v
        else:
            idx = np.random.randint(0, k+1)
            if (idx < ni):
                ret[idx] = v

    return ret

SIZE = 12

s = stream(SIZE)
q = resSample(1, s)
print(q)

Я вижу, что есть вопрос в отношении RNG. Предположим, у меня есть настоящий RNG, аппаратное устройство, которое возвращает один бит за раз. Мы используем его только в коде, где получаем индекс.

if (idx < ni):

Единственное условие-условие будет вызвано для выбора одного элемента. это когда ni=1 и, следовательно, idx может быть только НОЛЬ.

Таким образом, np.random.randint (0, k + 1) с такой реализацией будет выглядеть примерно так:

def trng(k):
    for _ in range(k+1):
        if next_true_bit():
            return 1 # as soon as it is not 0, we don't care
    return 0 # all bits are zero, index is zero, proceed with exchange

КЭД, такая реализация возможна, и поэтому этот метод отбора проб будет работать

UPDATE

@ kyrill, вероятно, прав - мне нужно вести подсчет (журнал ₂ (k) хранения), поэтому пока не вижу способа избежать этого. Даже с помощью трюка с ГСЧ мне нужно сэмплировать 0 с вероятностью 1/k, и это k увеличивается с размером потока.

Answer 2

Создайте случайное число для каждого элемента и запомните элемент с наименьшим номером.

Это ответ, который мне нравится больше всего, но вы, вероятно, ищете ответ:

Если поток имеет длину N элементов, то вероятность возврата элемента Nth равна 1 / N . Поскольку эта вероятность различна для каждого N , любой компьютер, который может выполнить эту задачу, должен войти в разные состояния после чтения потоков различной длины. Поскольку число возможных длин не ограничено, необходимое количество возможных состояний не ограничено, и машине потребуется различный объем памяти для различения между ними.