algorithm - 在 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) 空间从流中随机选择一个项目。

任何人都可以(反)证明这一点吗？

Answer 1

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

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

如果流的长度为 N 个项目，则返回第 N 个项目的概率为 1/N。由于这个概率对于每个 N 都是不同的，任何能够完成这个任务的机器都必须在读取不同长度的流后进入不同的状态。由于可能长度的数量是无限的，所需的可能状态数量也是无限的，机器将需要无限量的内存来区分它们。