Struct rand_distr::weighted_tree::WeightedTreeIndex

pub struct WeightedTreeIndex<W: Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> { /* private fields */ }

Available on crate feature alloc only.

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

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

Key differences

The main distinction between WeightedTreeIndex<W> and rand::distributions::WeightedIndex<W> lies in the internal representation of weights. In WeightedTreeIndex<W>, weights are structured as a tree, which is optimized for frequent updates of the weights.

Caution: Floating point types

When utilizing WeightedTreeIndex<W> with floating point types (such as f32 or f64), exercise caution due to the inherent nature of floating point arithmetic. Floating point types are susceptible to numerical rounding errors. Since operations on floating point weights are repeated numerous times, rounding errors can accumulate, potentially leading to noticeable deviations from the expected behavior.

Ideally, use fixed point or integer types whenever possible.

Performance

A WeightedTreeIndex<W> with n elements requires O(n) memory.

Time complexity for the operations of a WeightedTreeIndex<W> are:

• Constructing: Building the initial tree from an iterator of weights takes O(n) time.
• Sampling: Choosing an index (traversing down the tree) requires O(log n) time.
• Weight Update: Modifying a weight (traversing up the tree), requires O(log n) time.
• Weight Addition (Pushing): Adding a new weight (traversing up the tree), requires O(log n) time.
• Weight Removal (Popping): Removing a weight (traversing up the tree), requires O(log n) time.

Example

use rand_distr::WeightedTreeIndex;
use rand::prelude::*;

let choices = vec!['a', 'b', 'c'];
let weights = vec![2, 0];
let mut dist = WeightedTreeIndex::new(&weights).unwrap();
dist.push(1).unwrap();
dist.update(1, 1).unwrap();
let mut rng = thread_rng();
let mut samples = [0; 3];
for _ in 0..100 {
    // 50% chance to print 'a', 25% chance to print 'b', 25% chance to print 'c'
    let i = dist.sample(&mut rng);
    samples[i] += 1;
}
println!("Results: {:?}", choices.iter().zip(samples.iter()).collect::<Vec<_>>());

Implementations

impl<W: Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> WeightedTreeIndex<W>

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

where I: IntoIterator, I::Item: SampleBorrow<W>,

Creates a new WeightedTreeIndex from a slice of weights.

Error cases:

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

pub fn is_empty(&self) -> bool

Returns true if the tree contains no weights.

pub fn len(&self) -> usize

Returns the number of weights.

pub fn is_valid(&self) -> bool

Returns true if we can sample.

This is the case if the total weight of the tree is greater than zero.

pub fn get(&self, index: usize) -> W

Gets the weight at an index.

pub fn pop(&mut self) -> Option<W>

Removes the last weight and returns it, or None if it is empty.

pub fn push(&mut self, weight: W) -> Result<(), WeightError>

Appends a new weight at the end.

Error cases:

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

pub fn update(&mut self, index: usize, weight: W) -> Result<(), WeightError>

Updates the weight at an index.

Error cases:

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

Trait Implementations

impl<W: Clone + Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> Clone for WeightedTreeIndex<W>

fn clone(&self) -> WeightedTreeIndex<W>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<W: Debug + Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> Debug for WeightedTreeIndex<W>

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

Formats the value using the given formatter.

impl<W: Default + Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> Default for WeightedTreeIndex<W>

fn default() -> WeightedTreeIndex<W>

Returns the “default value” for a type.

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

where W: Deserialize<'de> + Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight,

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<W: Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> Distribution<usize> for WeightedTreeIndex<W>

Samples a randomly selected index from the weighted distribution.

Caution: This method panics if there are no elements or all weights are zero. However, it is guaranteed that this method will not panic if a call to WeightedTreeIndex::is_valid returns true.

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: PartialEq + Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> PartialEq for WeightedTreeIndex<W>

fn eq(&self, other: &WeightedTreeIndex<W>) -> 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<W> Serialize for WeightedTreeIndex<W>

where W: Serialize + Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight, 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.

impl<W: Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight> StructuralPartialEq for WeightedTreeIndex<W>