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