jeudi 11 avril 2019

Select random item from stream in O(1) space

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

The stream provides the following operations:

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

The elements in the stream (ergo the elements of data) are of constant size and neither of them is None, so None signals end of stream. The length of stream can only be learned by consuming the entire stream. And note that counting the number of elements consumes O(log n) space.

I believe there is no way to uniformly choose an item from the stream at random using O(1) space.

Can anyone (dis)prove this?




Aucun commentaire:

Enregistrer un commentaire