Keep a sample before the final length is known
A stream delivers log records one at a time without revealing its final length. Reservoir sampling retains k records without storing the complete input. Keep the first k, then accept item i with probability k/i and replace one retained position uniformly. That description uses a one-based count; the code's zero-based enumerate index therefore needs i plus one in its random range.
The sampling units are input positions, not distinct values. Two identical log strings are two separate records. Sampling unique values or favoring recent records would be a different task. Define uniform inclusion over positions before implementing the update rule. Otherwise a small memory footprint may hide a sampling policy that answers a different statistical or operational question.
Use one random integer for acceptance and replacement
With reservoir size three, consider the fifth incoming record. Draw uniformly from integers zero through four. Values zero, one and two replace that stored slot; three and four leave the reservoir unchanged. Acceptance probability is three fifths, and conditional replacement is uniform among the three slots. One random draw represents both decisions without needing a second replacement draw.
A zero-sized reservoir returns an empty sample after consuming input. If the stream has fewer than k items, retain every available item rather than padding with invented records. Negative k is rejected. An API requiring exactly k results would need a separate short-stream policy. These boundaries belong to the sample contract, because output size can legitimately differ from k when insufficient input exists.
| Draw for item five | Action | Probability |
|---|---|---|
| 0,1,2 | Replace that reservoir slot | 1/5 each; 3/5 total |
| 3,4 | Keep current sample | 2/5 total |
Derive an old item’s survival probability
Assume each earlier item is retained with probability k/(i minus one) after the previous step. A particular stored slot is replaced with probability 1/i on the next step, so that old item survives with probability one minus 1/i. Multiplying gives k/i. The new item is also accepted with probability k/i, making all processed positions equally likely to remain.
This reasoning uses a uniform draw and the matching replacement rule. Accepting with probability k/i but always overwriting the first slot biases survival. The uniform-subset property can likewise be established inductively for the update rule. Observed inclusion counts that look similar provide a diagnostic, not a replacement for that argument about the full sampling distribution.
Separate reproducibility from distribution diagnostics
The code asserts fixed-seed reproducibility, zero-size and short-stream behavior, sample size and unique positions for unique input. It then samples N equal to twenty with k equal to four across seeds zero through 1,999 and prints every inclusion count. Total inclusions must be eight thousand; the expected count per position is four hundred. Exact equality of all observed counts is not required.
Random samples fluctuate, so unequal counts alone do not establish a defect. They can still reveal severe bias and complement the mathematical argument. Preserve all observations rather than selecting an attractive seed. If generator implementation or version changes, check what fixed-seed compatibility is actually promised. Reproducibility of one run and uniformity over possible random choices are different claims.
import random
from collections import Counter
def reservoir(stream,k,rng):
if k<0:raise ValueError('negative sample size')
result=[]
for i,item in enumerate(stream):
if i<k:result.append(item)
else:
slot=rng.randrange(i+1)
if slot<k:result[slot]=item
return result
assert reservoir(iter([1,2]),5,random.Random(7))==[1,2]
assert reservoir(range(10),0,random.Random(7))==[]
assert reservoir(range(20),4,random.Random(7))==reservoir(iter(range(20)),4,random.Random(7))
counts=Counter()
for seed in range(2000):
sample=reservoir(range(20),4,random.Random(seed));assert len(sample)==len(set(sample))==4
counts.update(sample)
assert sum(counts.values())==8000
print('seeds=0..1999 N=20 k=4 inclusion_counts=',[counts[i] for i in range(20)])
print('expected inclusion count=400; observations do not prove uniformity')
Count retained records and consumed input separately
The basic reservoir retains at most k records and uses O(k) auxiliary storage. It still consumes every one of N input records, so its running time is O(N). A small sample does not imply only k reads. Retaining references rather than copying records may keep large backing objects alive, so reference count and retained data bytes are separate memory measures.
Known-length random-access input may support another selection strategy. More advanced reservoir algorithms can optimize skipping, but this lesson uses the per-record rule because its probability argument is visible. An unbounded stream needs an external stopping or inspection policy. The reservoir at an inspection time samples the entire prefix processed so far, not automatically a recent sliding time window.
Preserve the population when resuming or combining
Resuming a run requires more than its current sample. Preserve the processed count and, for exact reproduction, generator state and input identity/order. Resetting the count to k accepts later records too aggressively and changes the population weighting. Replaying the same record twice creates two input positions under this contract.
Parallel workers with unequal input sizes cannot generally concatenate equal-sized reservoirs and uniformly trim them without accounting for their original populations. A correct merge needs a specified weighting or sampling rule. Do not treat the single-stream implementation as an automatically uniform sample of arbitrary parallel streams. State both the saved-state boundary and the population from which inclusion is intended, especially when checkpoints or worker restarts change how records are replayed.
Repeated values remain separate stream positions. Deduplicating values changes the population being sampled.
Distinguish equal values from equal sampling units
For A,A,B,B and k one, every position has probability one quarter while each displayed value has probability one half. Changing input to A,A,A,B gives value A probability three quarters. That is not uniform sampling over distinct values.
Converting the stream to a set first changes the population by removing repeated positions; it is not merely a memory optimization of the same task. Decide whether the unit is a log record, user or distinct value. Counting positions in distribution checks helps separate input value frequency from algorithmic bias. Sampling semantics belong to the data definition as much as to the replacement loop.
Exercise: multiply survival probabilities
With k equal to two, ask whether the first item remains after four arrivals. It starts in the reservoir. Survival at arrival three is two thirds and at arrival four is three quarters. Their product is one half, matching k/N. The fourth item is also accepted with probability two fourths. Show the conditional survival steps rather than only quoting the final formula.
Now checkpoint after ten of twenty records and reset the processed count before continuing. The later half is treated like a new beginning and can be overrepresented. The sample and count must describe the same processed history. Connect the probability denominator, zero-based code index and state retained for restart. That relationship is more important than reproducing one attractive fixed-seed sample.