dynamic_weighted_sampler

A dynamically-updated, weighted random sampler for discrete items, based on the algorithm described by Aaron Defazio, itself derived from the method presented in:

Yossi Matias, Jeffrey Scott Vitter, and Wen-Chun Ni. Dynamic Generation of Discrete Random Variates. Theory of Computing Systems, 36 (2003): 329–358. Springer Link

This crate allows for efficient weighted sampling from a collection where item weights can be changed at runtime, and supports fast sampling and updates.

✨ Features

Dynamic updates to weights
Efficient close to constant sampling time
Efficient constant weight update time
Optional serde support via a feature flag

📦 Installation

Add to your Cargo.toml:

[dependencies]
dynamic_weighted_sampler = "0.1"

To enable serialization support:

[dependencies]
dynamic_weighted_sampler = { version = "0.1", features = ["serde"] }

🔧 Usage

use dynamic_weighted_sampler::DynamicWeightedSampler;

let mut sampler = DynamicWeightedSampler::new();
sampler.insert(1, 4.);  // 80% of the mass
sampler.insert(2, 1.); // 20% of the mass

// Sample an item
let item = sampler.sample(&mut rand::rng());
println!("Sampled: {:?}", item);

// Update the weight
sampler.update(1, 5.);

🔒 License

Licensed under either of:

MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)

🤝 Contributions

Contributions, issues, and feature requests are welcome! Feel free to open a pull request or issue.