Struct WeightedAliasIndex

pub struct WeightedAliasIndex<W: AliasableWeight> { /* private fields */ }

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

Sampling a WeightedAliasIndex<W> distribution returns the index of a randomly selected element from the vector used to create the WeightedAliasIndex<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 AliasableWeight exists.

Performance

Given that n is the number of items in the vector used to create an WeightedAliasIndex<W>, it 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 WeightedAliasIndex<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_distr::WeightedAliasIndex;
use rand::prelude::*;

let choices = vec!['a', 'b', 'c'];
let weights = vec![2, 1, 1];
let dist = WeightedAliasIndex::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), ('b', 3), ('c', 7)];
let dist2 = WeightedAliasIndex::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: AliasableWeight> WeightedAliasIndex<W>

pub fn new(weights: Vec<W>) -> Result<Self, WeightError>

Creates a new WeightedAliasIndex.

Error cases:

• WeightError::InvalidInput when weights.len() is zero or greater than u32::MAX.
• WeightError::InvalidWeight when a weight is not-a-number, negative or greater than max = W::MAX / weights.len().
• WeightError::InsufficientNonZero when the sum of all weights is zero.

Trait Implementations

impl<W: AliasableWeight> Clone for WeightedAliasIndex<W>

where Uniform<W>: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<W> Debug for WeightedAliasIndex<W>

where W: Debug + AliasableWeight, Uniform<W>: Debug,

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

Formats the value using the given formatter.

impl<'de, W> Deserialize<'de> for WeightedAliasIndex<W>

where W: Deserialize<'de> + AliasableWeight, W::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<W: AliasableWeight> Distribution<usize> for WeightedAliasIndex<W>

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<W> Serialize for WeightedAliasIndex<W>

where W: Serialize + AliasableWeight, W::Sampler: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.