Crate infinity_sampler

Infinity Sampler

✨ Allocation free ✨ No dependencies ✨ no_std compatible ✨

The Infinity Sampler lets you automatically sample an infinite stream of values into a fixed size buffer, while keeping an even spread of samples.

It’s a deterministic variation of the Reservoir Sampling algorithm. Writes are O(1), iteration is O(N*log(N)). See math for an illustrated explainer.

Your primary interface is the SamplingReservoir struct:

use infinity_sampler::SamplingReservoir;

let mut reservoir = SamplingReservoir::<u32, 8>::new();
for i in 0..256 {
   reservoir.sample(i);
}
let samples: Vec<_> = reservoir.into_ordered_iter().collect();

assert_eq!(samples, vec![0, 32, 64, 96, 128, 160, 192, 224]);

Both reservoir types require N * (sizeof<T> + sizeof<usize>) memory.

Modules

• math
  Algorithm explainer

Structs

• InitializedItem
  A single Item that is guaranteed to be initialized.
• Item
  A single item in the reservoir’s buffer. This is a thin wrapper over MaybeUninit that also tracks the insertion index and initialization state.
• ReservoirOrderedIter
  Chronological iterator over stored items.
• SamplingRate
  A simple sampler.
• SamplingReservoir
  Infinity Sampler

Enums

• SamplingOutcome