dynamic-weighted-sampler

Crates.io	dynamic-weighted-sampler
lib.rs	dynamic-weighted-sampler
version	0.2.1
created_at	2025-04-23 11:38:40.692267+00
updated_at	2025-07-18 08:25:02.038732+00
description	An efficient weighted sampler with dynamically updatable weights
homepage
repository	https://github.com/germank/dynamic-weighted-sampler
max_upload_size
id	1645408
size	18,205

Germán Kruszewski (germank)

documentation

README

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 max_value = 10.;
let mut sampler = DynamicWeightedSampler::new(max_value);
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.);