pub struct WeightedIndex<X>{ /* private fields */ }
Available on crate feature alloc only.
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).

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