Struct rand_distr::WeightedIndex

source ·
pub struct WeightedIndex<X>{ /* private fields */ }
Expand description

A distribution using weighted sampling of discrete items

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 weight of the element. The weights can use any type X for which an implementation of Uniform<X> exists. The implementation guarantees that elements with zero weight are never picked, even when the weights are floating point numbers.

§Performance

Time complexity of sampling from WeightedIndex is O(log N) where N is the number of weights. There are two alternative implementations with different runtimes characteristics:

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 an instance of X::Sampler, this might cause additional allocations, though for primitive types, Uniform<X> doesn’t allocate any memory.

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 implementation 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.0), ('b', 3.0), ('c', 7.0)];
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§

source§

impl<X> WeightedIndex<X>

source

pub fn new<I>(weights: I) -> Result<WeightedIndex<X>, WeightError>
where I: IntoIterator, <I as IntoIterator>::Item: SampleBorrow<X>, X: Weight,

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.

Error cases:

source

pub fn update_weights( &mut self, new_weights: &[(usize, &X)] ) -> Result<(), WeightError>
where X: for<'a> AddAssign<&'a X> + for<'a> SubAssign<&'a X> + Clone + Default,

Update a subset of weights, without changing the number of weights.

new_weights must be sorted by the index.

Using this method instead of new might be more efficient if only a small number of weights is modified. No allocations are performed, unless the weight type X uses allocation internally.

In case of error, self is not modified. Error cases:

Updates take O(N) time. If you need to frequently update weights, consider rand_distr::weighted_tree as an alternative where an update is O(log N).

source§

impl<X> WeightedIndex<X>

source

pub fn weight(&self, index: usize) -> Option<X>
where X: for<'a> SubAssign<&'a X>,

Returns the weight at the given index, if it exists.

If the index is out of bounds, this will return None.

§Example
use rand::distributions::WeightedIndex;

let weights = [0, 1, 2];
let dist = WeightedIndex::new(&weights).unwrap();
assert_eq!(dist.weight(0), Some(0));
assert_eq!(dist.weight(1), Some(1));
assert_eq!(dist.weight(2), Some(2));
assert_eq!(dist.weight(3), None);
source

pub fn weights(&self) -> WeightedIndexIter<'_, X>
where X: for<'a> SubAssign<&'a X>,

Returns a lazy-loading iterator containing the current weights of this distribution.

If this distribution has not been updated since its creation, this will return the same weights as were passed to new.

§Example
use rand::distributions::WeightedIndex;

let weights = [1, 2, 3];
let mut dist = WeightedIndex::new(&weights).unwrap();
assert_eq!(dist.weights().collect::<Vec<_>>(), vec![1, 2, 3]);
dist.update_weights(&[(0, &2)]).unwrap();
assert_eq!(dist.weights().collect::<Vec<_>>(), vec![2, 2, 3]);
source

pub fn total_weight(&self) -> X

Returns the sum of all weights in this distribution.

Trait Implementations§

source§

impl<X> Clone for WeightedIndex<X>

source§

fn clone(&self) -> WeightedIndex<X>

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<X> Debug for WeightedIndex<X>

source§

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

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

impl<'de, X> Deserialize<'de> for WeightedIndex<X>

source§

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

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

impl<X> Distribution<usize> for WeightedIndex<X>

source§

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.
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<X> PartialEq for WeightedIndex<X>

source§

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

source§

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

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

impl<X> StructuralPartialEq for WeightedIndex<X>

Auto Trait Implementations§

§

impl<X> Freeze for WeightedIndex<X>
where X: Freeze, <X as SampleUniform>::Sampler: Freeze,

§

impl<X> RefUnwindSafe for WeightedIndex<X>

§

impl<X> Send for WeightedIndex<X>
where X: Send, <X as SampleUniform>::Sampler: Send,

§

impl<X> Sync for WeightedIndex<X>
where X: Sync, <X as SampleUniform>::Sampler: Sync,

§

impl<X> Unpin for WeightedIndex<X>
where X: Unpin, <X as SampleUniform>::Sampler: Unpin,

§

impl<X> UnwindSafe for WeightedIndex<X>

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>,