在O（1）空间中从流中选择随机项

Question

Select an item from a stream at random with uniform probability, using constant space

该流提供以下操作：

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

为每个元素生成一个随机数，并记住编号最小的元素。

这是我最喜欢的答案，但您可能正在寻找的答案是：

如果流是N项长，那么返回第N项的概率是1 / N.由于每个N的概率不同，任何能够完成此任务的机器在读取不同长度的流后必须进入不同的状态。由于可能长度的数量是无限的，所需的可能状态数量是无限的，并且机器将需要无限量的存储器来区分它们。

Answer 2

在恒定的空间？当然，Reservoir Sampling，恒定的空间，线性时间

一些经过轻微测试的代码

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，硬件设备一次返回一位。我们只在get index的代码中使用它。

if (idx < ni):

选择一个元素时触发条件的唯一方法是ni=1，因此idx只能为ZERO。

因此，具有这种实现的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

QED，这样的实现是可能的，因此这种采样方法应该有效

UPDATE

@kyrill可能是对的 - 我必须有一个计数（log2（k）存储），到目前为止看不到它的避免。即使使用RNG技巧，我也必须以概率1/k采样0，并且这个k随着流的大小而增长。