Module reservoir 

Reservoir sampling.

Maintains a uniform sample of size k from a stream of unknown length.

Uses Algorithm L (Li, 1994) for optimal performance. Instead of generating a random number for every item (Algorithm R), we compute the number of items to skip before the next replacement. This reduces complexity from O(N) RNG calls to O(k * (1 + log(N/k))).

References

• Vitter (1985): reservoir sampling “Algorithm R”.
• Li (1994): reservoir sampling “Algorithm L” (skip-based).
• Efraimidis & Spirakis (2006): weighted reservoir sampling (A-Res).
• Meligrana & Fazzone (2024): “Weighted Reservoir Sampling With Replacement from Data Streams” – extends A-Res to with-replacement sampling (potential future variant)
• Pettie & Wang (2024): “Universal Perfect Samplers for Incremental Streams” – exact G-samplers using O(1) space for general moment functions

Notes:

• This module provides *_with_rng entrypoints for deterministic testing/benchmarking.

Structs

ReservoirSampler

A reservoir sampler that maintains a uniform sample of size k from a stream.

ReservoirSamplerR

A reservoir sampler using Algorithm R (Vitter, 1985).

WeightedReservoirSampler

A weighted reservoir sampler (Efraimidis-Spirakis, A-Res).

Enums

WeightedReservoirError

Errors for weighted reservoir sampling.