Struct rand_distr::weighted::alias_method::WeightedIndex

pub struct WeightedIndex<W> where
    W: Weight,  { /* fields omitted */ }

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

Sampling a WeightedIndex<W> distribution returns the index of a randomly selected element from the vector used to create the WeightedIndex<W>. The chance of a given element being picked is proportional to the value of the element. The weights can have any type W for which a implementation of Weight exists.

Performance

Given that n is the number of items in the vector used to create an WeightedIndex<W>, WeightedIndex<W> will require O(n) amount of memory. More specifically it takes up some constant amount of memory plus the vector used to create it and a Vec<u32> with capacity n.

Time complexity for the creation of a WeightedIndex<W> is O(n). Sampling is O(1), it makes a call to Uniform<u32>::sample and a call to Uniform<W>::sample.

Example

use rand::distributions::weighted::alias_method::WeightedIndex;
use rand::prelude::*;

let choices = vec!['a', 'b', 'c'];
let weights = vec![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).collect()).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<W> WeightedIndex<W> where
    W: Weight, 

pub fn new(weights: Vec<W, Global>) -> Result<WeightedIndex<W>, WeightedError>

Creates a new WeightedIndex.

Returns an error if:

• The vector is empty.
• The vector is longer than u32::MAX.
• For any weight w: w < 0 or w > max where max = W::MAX / weights.len().
• The sum of weights is zero.

Trait Implementations

impl<W> Clone for WeightedIndex<W> where
    W: Weight,
    Uniform<W>: Clone, 

pub fn clone(&self) -> WeightedIndex<W>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<W> Debug for WeightedIndex<W> where
    W: Weight + Debug,
    Uniform<W>: Debug, 

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

Formats the value using the given formatter.

impl<W> Distribution<usize> for WeightedIndex<W> where
    W: Weight, 

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.

pub fn sample_iter<R>(self, rng: R) -> DistIter<Self, R, T> where
    R: Rng, 

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