Reservoir Sampling

Choose $k$ items uniformly at random from a stream of unknown length, using $O(k)$ memory and one pass.

Algorithm R — the classic

vector<int> reservoir(istream& in, int k) {
    vector<int> res;
    int x, i = 0;
    while (in >> x) {
        if (i < k) res.push_back(x);
        else {
            int j = uniform_int_distribution<int>(0, i)(rng);
            if (j < k) res[j] = x;
        }
        i++;
    }
    return res;
}

Keep the first $k$; for the $i$-th item ($i\ge k$, 0-indexed), keep it with probability $k/(i+1)$, replacing a uniformly chosen slot.

Why it is uniform

Claim: after processing $n$ items, each is in the reservoir with probability $k/n$.

Induction. True for $n=k$. Suppose it holds after $n-1$ items. Item $n$ enters with probability $k/n$ by construction. An earlier item survives iff either the new item is rejected (probability $1-\frac{k}{n}$), or it is accepted but evicts a different slot (probability $\frac{k}{n}\cdot \frac{k-1}{k}$). Total:

$\frac{k}{n-1}\left[\left(1-\frac{k}{n}\right)+\frac{k}{n}\cdot \frac{k-1}{k}\right]=\frac{k}{n-1}\cdot \frac{n-1}{n}=\frac{k}{n}.■$

Variants

Single item ($k=1$)

int chosen; int i = 0;
while (in >> x) { if (uniform_int_distribution<int>(0, i)(rng) == 0) chosen = x; i++; }

Keep the $i$-th item with probability $1/(i+1)$. Two lines.

Weighted reservoir sampling (A-Res)

Give item $i$ the key $u_i^{1/w_i}$ with $u_i$ uniform in $(0,1)$, and keep the $k$ largest keys in a min-heap.

priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> pq;
double key = pow(uniform_real_distribution<double>(0,1)(rng), 1.0 / w);
if ((int)pq.size() < k) pq.push({key, item});
else if (key > pq.top().first) { pq.pop(); pq.push({key, item}); }

Selects each item with probability proportional to its weight, in one pass and $O(k)$ memory.

Algorithm L — skip ahead

Instead of drawing a random number per item, compute how many items to skip before the next acceptance. Reduces the random-number count from $O(n)$ to $O(k\log (n/k))$ — the standard optimisation for very long streams.

Distributed sampling

Each machine keeps its own reservoir with a count; merge by sampling from the reservoirs weighted by their counts. Uniformity is preserved.

When it applies

Situation	Why reservoir sampling
The input length is unknown in advance	cannot pre-allocate or index
The data does not fit in memory	$O(k)$ space
A single pass is all you get	streaming
Sampling log lines, telemetry, network packets	the standard production use
Choosing a random element of a linked list	one traversal
Random node of a tree during a DFS	$k=1$ variant
Randomly selecting from a filtered subset	apply the filter as you stream

If you do know the length

Simply pick $k$ random indices, or shuffle and take the first $k$ — simpler and faster. Reservoir sampling is specifically for the unknown-length or streaming case.

shuffle(v.begin(), v.end(), rng);
vector<int> sample(v.begin(), v.begin() + k);

Or, for $k\ll n$, sample indices with a hash set to avoid the full shuffle: $O(k)$ expected.

Related streaming algorithms

Problem	Algorithm	Space
Uniform sample of $k$	reservoir sampling	$O(k)$
Count distinct elements	HyperLogLog	$O(\log \log n)$
Frequent items (“heavy hitters”)	Misra-Gries, Count-Min sketch	$O(1/\epsilon )$
Approximate quantiles	t-digest, GK summary	$O(\frac{1}{\epsilon }\log n)$
Membership testing	Bloom filter	$O(n)$ bits
Majority element	Boyer-Moore voting	$O(1)$

Boyer-Moore voting is the deterministic cousin worth pairing with this: it finds a strict majority element in one pass and $O(1)$ space, with no randomness at all.

See also: Randomized Algorithms · Boyer-Moore Voting · Probability