Struct rand_distr::weighted_tree::WeightedTreeIndex

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

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§

source§

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

source

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:

source

pub fn is_empty(&self) -> bool

Returns true if the tree contains no weights.

source

pub fn len(&self) -> usize

Returns the number of weights.

source

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.

source

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

Gets the weight at an index.

source

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

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

source

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

Appends a new weight at the end.

Error cases:

source

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

Updates the weight at an index.

Error cases:

source§

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

source

pub fn try_sample<R: Rng + ?Sized>( &self, rng: &mut R ) -> Result<usize, WeightError>

Samples a randomly selected index from the weighted distribution.

Returns an error if there are no elements or all weights are zero. This is unlike Distribution::sample, which panics in those cases.

Trait Implementations§

source§

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

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn default() -> WeightedTreeIndex<W>

Returns the “default value” for a type. Read more
source§

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

source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>
where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
source§

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.

source§

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

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

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. Read more
source§

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 Read more
source§

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

source§

fn eq(&self, other: &WeightedTreeIndex<W>) -> bool

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

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.
source§

impl<W> Serialize for WeightedTreeIndex<W>

source§

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

Serialize this value into the given Serde serializer. Read more
source§

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

Auto Trait Implementations§

§

impl<W> Freeze for WeightedTreeIndex<W>

§

impl<W> RefUnwindSafe for WeightedTreeIndex<W>
where W: RefUnwindSafe,

§

impl<W> Send for WeightedTreeIndex<W>
where W: Send,

§

impl<W> Sync for WeightedTreeIndex<W>
where W: Sync,

§

impl<W> Unpin for WeightedTreeIndex<W>
where W: Unpin,

§

impl<W> UnwindSafe for WeightedTreeIndex<W>
where W: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

source§

fn vzip(self) -> V

source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,