Reservoir Sampling

Maintains a uniform random sample of exactly k items from a stream of unknown or unbounded length, seen in a single pass, using only O(k) memory.

How it works

Algorithm R (Vitter, 1985) is disarmingly simple. The first k items always fill the reservoir. For every item after that, at stream position i (0-based, so it's the (i+1)-th item seen), draw a random integer j uniformly from [0, i]. If j < k, the new item replaces reservoir[j]; otherwise it's discarded.

Why does this stay uniform? By induction: after processing the first n items, each one has exactly a k/n chance of being in the reservoir. When item n+1 arrives, it gets in with probability k/(n+1). Each item already in the reservoir survives that step only if either the new item is rejected, or it lands on a different slot -- working out the combined probability shows every item still ends up with exactly a k/(n+1) chance of survival, so the invariant holds for the whole stream without ever needing to know its length in advance.

The optional weighted variant (Algorithm A-Res, Efraimidis & Spirakis, 2006) generalizes this to weighted sampling without replacement: each item gets a key u^(1/w) for a fresh random u ∈ (0, 1) and its weight w, and the k items with the largest keys form the sample -- so heavier items are more likely to survive, but every item still has a chance.

Interactive demo

Reservoir size (k)5
Items seen (n)0
Slots filled0 / 5
P(next item sampled)100%
slot 0·
slot 1·
slot 2·
slot 3·
slot 4·
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new ReservoirSampler(k, seed?)Allocate a reservoir of k empty slots.O(k) space
add(item): ReservoirStepFeed the next stream item; fills, replaces, or skips a slot.O(1) time
sample(): (string | null)[]Current k-item sample (nulls if the stream is shorter than k).O(k) time
clear(): voidReset the reservoir and item counter.O(k) time
new WeightedReservoirSampler(k, seed?)Optional weighted variant (Algorithm A-Res).O(k) space
add(item, weight): WeightedReservoirStepFeed a weighted item; larger weight → higher chance of survival.O(k) time

References

Original papers

Library implementations

Real-world use cases