Struct rand::distributions::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. There are two alternative implementations with different runtimes characteristics:

• rand_distr::weighted_alias supports O(1) sampling, but with much higher initialisation cost.
• rand_distr::weighted_tree keeps the weights in a tree structure where sampling and updating is O(log N).

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::distributions::WeightedIndex;

let choices = ['a', 'b', 'c'];
let weights = [2,   1,   1];
let dist = WeightedIndex::new(&weights).unwrap();
let mut rng = thread_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>, WeightError>

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:

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

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

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:

• WeightError::InvalidInput when new_weights are not ordered by index or an index is too large.
• WeightError::InvalidWeight when a weight is not-a-number or negative.
• WeightError::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::distributions::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::distributions::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 copy 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<'de, X> Deserialize<'de> for WeightedIndex<X>

where X: Deserialize<'de> + SampleUniform + PartialOrd, X::Sampler: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

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) -> DistIter<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) -> DistMap<Self, F, T, S>

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

Create a distribution of values of ‘S’ by mapping the output of Self through the closure F

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

where X::Sampler: PartialEq,

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<X> Serialize for WeightedIndex<X>

where X: Serialize + SampleUniform + PartialOrd, X::Sampler: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

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