Struct flow_sdk::algorithms::rand::distributions::WeightedIndex

pub struct WeightedIndex<X> where
    X: SampleUniform + PartialOrd<X>,  { /* fields omitted */ }

A distribution using weighted sampling to pick a discretely selected item.

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 value of the element. The weights can use any type X for which an implementation of Uniform<X> exists.

Performance

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, this might cause additional allocations, though for primitive types, [’Uniform`] doesn’t allocate any memory.

Time complexity of sampling from WeightedIndex is O(log N) where N is the number of weights.

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 implementaiton 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), ('b', 3), ('c', 7)];
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> WeightedIndex<X> where
    X: SampleUniform + PartialOrd<X>, 

pub fn new<I>(weights: I) -> Result<WeightedIndex<X>, WeightedError> where
    I: IntoIterator,
    X: for<'a> AddAssign<&'a X> + Clone + Default,
    <I as IntoIterator>::Item: SampleBorrow<X>, 

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.

Returns an error if the iterator is empty, if any weight is < 0, or if its total value is 0.

Trait Implementations

impl<X> Clone for WeightedIndex<X> where
    X: Clone + SampleUniform + PartialOrd<X>,
    <X as SampleUniform>::Sampler: Clone, 

pub 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 for WeightedIndex<X> where
    X: Debug + SampleUniform + PartialOrd<X>,
    <X as SampleUniform>::Sampler: Debug, 

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

Formats the value using the given formatter.

impl<X> Distribution<usize> for WeightedIndex<X> where
    X: SampleUniform + PartialOrd<X>, 

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

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

fn sample_iter<R>(&'a self, rng: &'a mut R) -> DistIter<'a, Self, R, T> where
    R: Rng, 

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