Struct WeightedIndex

pub struct WeightedIndex<X: SampleUniform + PartialOrd> { /* private fields */ }

A distribution using weighted sampling of discrete items.

Sampling a WeightedIndex distribution returns the index of a randomly selected element from the iterator used when the WeightedIndex was created. The chance of a given element being picked is proportional to the weight of the element. The weights can use any type X for which an implementation of Uniform<X> exists. The implementation guarantees that elements with zero weight are never picked, even when the weights are floating point numbers.

Performance

Time complexity of sampling from WeightedIndex is O(log N) where N is the number of weights. See also rand_distr::weighted for alternative implementations supporting potentially-faster sampling or a more easily modifiable tree structure.

A WeightedIndex<X> contains a Vec<X> and a Uniform<X> and so its size is the sum of the size of those objects, possibly plus some alignment.

Creating a WeightedIndex<X> will allocate enough space to hold N - 1 weights of type X, where N is the number of weights. However, since Vec doesn’t guarantee a particular growth strategy, additional memory might be allocated but not used. Since the WeightedIndex object also contains an instance of X::Sampler, this might cause additional allocations, though for primitive types, Uniform<X> doesn’t allocate any memory.

Sampling from WeightedIndex will result in a single call to Uniform<X>::sample (method of the Distribution trait), which typically will request a single value from the underlying RngCore, though the exact number depends on the implementation of Uniform<X>::sample.

Example

use rand::prelude::*;
use rand::distr::weighted::WeightedIndex;

let choices = ['a', 'b', 'c'];
let weights = [2,   1,   1];
let dist = WeightedIndex::new(&weights).unwrap();
let mut rng = rand::rng();
for _ in 0..100 {
    // 50% chance to print 'a', 25% chance to print 'b', 25% chance to print 'c'
    println!("{}", choices[dist.sample(&mut rng)]);
}

let items = [('a', 0.0), ('b', 3.0), ('c', 7.0)];
let dist2 = WeightedIndex::new(items.iter().map(|item| item.1)).unwrap();
for _ in 0..100 {
    // 0% chance to print 'a', 30% chance to print 'b', 70% chance to print 'c'
    println!("{}", items[dist2.sample(&mut rng)].0);
}

Implementations

impl<X: SampleUniform + PartialOrd> WeightedIndex<X>

pub fn new<I>(weights: I) -> Result<WeightedIndex<X>, Error>

where I: IntoIterator, I::Item: SampleBorrow<X>, X: Weight,

Creates a new a WeightedIndex Distribution using the values in weights. The weights can use any type X for which an implementation of Uniform<X> exists.

Error cases:

• Error::InvalidInput when the iterator weights is empty.
• Error::InvalidWeight when a weight is not-a-number or negative.
• Error::InsufficientNonZero when the sum of all weights is zero.
• Error::Overflow when the sum of all weights overflows.

pub fn update_weights( &mut self, new_weights: &[(usize, &X)], ) -> Result<(), Error>

where X: for<'a> AddAssign<&'a X> + for<'a> SubAssign<&'a X> + Clone + Default,

Update a subset of weights, without changing the number of weights.

new_weights must be sorted by the index.

Using this method instead of new might be more efficient if only a small number of weights is modified. No allocations are performed, unless the weight type X uses allocation internally.

In case of error, self is not modified. Error cases:

• Error::InvalidInput when new_weights are not ordered by index or an index is too large.
• Error::InvalidWeight when a weight is not-a-number or negative.
• Error::InsufficientNonZero when the sum of all weights is zero. Note that due to floating-point loss of precision, this case is not always correctly detected; usage of a fixed-point weight type may be preferred.

Updates take O(N) time. If you need to frequently update weights, consider rand_distr::weighted_tree as an alternative where an update is O(log N).

impl<X: SampleUniform + PartialOrd + Clone> WeightedIndex<X>

pub fn weight(&self, index: usize) -> Option<X>

where X: for<'a> SubAssign<&'a X>,

Returns the weight at the given index, if it exists.

If the index is out of bounds, this will return None.

Example

use rand::distr::weighted::WeightedIndex;

let weights = [0, 1, 2];
let dist = WeightedIndex::new(&weights).unwrap();
assert_eq!(dist.weight(0), Some(0));
assert_eq!(dist.weight(1), Some(1));
assert_eq!(dist.weight(2), Some(2));
assert_eq!(dist.weight(3), None);

pub fn weights(&self) -> WeightedIndexIter<'_, X>

where X: for<'a> SubAssign<&'a X>,

Returns a lazy-loading iterator containing the current weights of this distribution.

If this distribution has not been updated since its creation, this will return the same weights as were passed to new.

Example

use rand::distr::weighted::WeightedIndex;

let weights = [1, 2, 3];
let mut dist = WeightedIndex::new(&weights).unwrap();
assert_eq!(dist.weights().collect::<Vec<_>>(), vec![1, 2, 3]);
dist.update_weights(&[(0, &2)]).unwrap();
assert_eq!(dist.weights().collect::<Vec<_>>(), vec![2, 2, 3]);

pub fn total_weight(&self) -> X

Returns the sum of all weights in this distribution.

Trait Implementations

impl<X: Clone + SampleUniform + PartialOrd> Clone for WeightedIndex<X>

where X::Sampler: Clone,

fn clone(&self) -> WeightedIndex<X>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<X: Debug + SampleUniform + PartialOrd> Debug for WeightedIndex<X>

where X::Sampler: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<X> Distribution<usize> for WeightedIndex<X>

where X: SampleUniform + PartialOrd,

fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize

Generate a random value of T, using rng as the source of randomness.

fn sample_iter<R>(self, rng: R) -> Iter<Self, R, T>

where R: Rng, Self: Sized,

Create an iterator that generates random values of T, using rng as the source of randomness.

fn map<F, S>(self, func: F) -> Map<Self, F, T, S>

where F: Fn(T) -> S, Self: Sized,

Map sampled values to type S

impl<X: PartialEq + SampleUniform + PartialOrd> PartialEq for WeightedIndex<X>

where X::Sampler: PartialEq,

fn eq(&self, other: &WeightedIndex<X>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<X: SampleUniform + PartialOrd> StructuralPartialEq for WeightedIndex<X>