Reservoir Sampling from an Unknown-Length Stream
Problem statement
You are processing a data stream of unknown length $n$, one element at a time, and you cannot store the entire stream.
Implement the function:
def reservoir_sample(stream, k, seed):
...
It performs Vitter's Algorithm R (reservoir sampling) to draw $k$ items without replacement from stream, pinned to a canonical RNG so the output is deterministic:
- Create
rng = random.Random(seed). - Fill the reservoir with the first
kitems. - For each later item at 1-based position
i, drawj = rng.randint(1, i); ifj <= k, replacereservoir[j-1]with that item. - Return the reservoir (a list of length
min(k, len(stream)), in slot order).
Conceptually: each new element gets a fair shot at replacing a current selection, calibrated with decreasing probability $k/i$ so that after the whole stream, every size-$k$ subset is equally likely. The algorithm uses $O(k)$ memory, a single pass, and exactly $n-k$ random draws.
Example
reservoir_sample([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4, 2024) -> [9, 4, 7, 1]
The first 4 items fill the reservoir as [9, 8, 7, 6]; later items at positions 5..10 each draw j = rng.randint(1, i) and, when j <= 4, overwrite that slot; after processing the full stream two slots have been replaced, yielding [9, 4, 7, 1].
Show hint
If you already hold a fair sample of what came before, with what probability should a newly arriving item be let in?
Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.