Struct WeightedIndex

struct WeightedIndex<X: SampleUniform + PartialOrd> { ... }

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. See also rand_distr::weighted for alternative implementations supporting potentially-faster sampling or a more easily modifiable tree structure.

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::distr::weighted::WeightedIndex;

let choices = ['a', 'b', 'c'];
let weights = [2,   1,   1];
let dist = WeightedIndex::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.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

impl<X: SampleUniform + PartialOrd + Clone> WeightedIndex<X>

fn weight(self: &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::distr::weighted::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);

fn weights(self: &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::distr::weighted::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]);

fn total_weight(self: &Self) -> X

Returns the sum of all weights in this distribution.

impl<X: SampleUniform + PartialOrd> WeightedIndex<X>

fn new<I>(weights: I) -> Result<WeightedIndex<X>, Error>
where
    I: IntoIterator,
    <I as >::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:

fn update_weights(self: &mut Self, new_weights: &[(usize, &X)]) -> Result<(), Error>
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:

  • Error::InvalidInput when new_weights are not ordered by index or an index is too large.
  • Error::InvalidWeight when a weight is not-a-number or negative.
  • Error::InsufficientNonZero when the sum of all weights is zero. Note that due to floating-point loss of precision, this case is not always correctly detected; usage of a fixed-point weight type may be preferred.

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).

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

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

impl<T> Any for WeightedIndex<X>

fn type_id(self: &Self) -> TypeId

impl<T> Borrow for WeightedIndex<X>

fn borrow(self: &Self) -> &T

impl<T> BorrowMut for WeightedIndex<X>

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

impl<T> CloneToUninit for WeightedIndex<X>

unsafe fn clone_to_uninit(self: &Self, dest: *mut u8)

impl<T> DeserializeOwned for WeightedIndex<X>

impl<T> From for WeightedIndex<X>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> ToOwned for WeightedIndex<X>

fn to_owned(self: &Self) -> T
fn clone_into(self: &Self, target: &mut T)

impl<T, U> Into for WeightedIndex<X>

fn into(self: Self) -> U

Calls U::from(self).

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

impl<T, U> TryFrom for WeightedIndex<X>

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

impl<T, U> TryInto for WeightedIndex<X>

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

impl<V, T> VZip for WeightedIndex<X>

fn vzip(self: Self) -> V

impl<X> Distribution for WeightedIndex<X>

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

impl<X> Freeze for WeightedIndex<X>

impl<X> RefUnwindSafe for WeightedIndex<X>

impl<X> Send for WeightedIndex<X>

impl<X> Serialize for WeightedIndex<X>

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

impl<X> Sync for WeightedIndex<X>

impl<X> Unpin for WeightedIndex<X>

impl<X> UnsafeUnpin for WeightedIndex<X>

impl<X> UnwindSafe for WeightedIndex<X>

impl<X: $crate::clone::Clone + SampleUniform + PartialOrd> Clone for WeightedIndex<X>

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

impl<X: $crate::cmp::PartialEq + SampleUniform + PartialOrd> PartialEq for WeightedIndex<X>

fn eq(self: &Self, other: &WeightedIndex<X>) -> bool

impl<X: $crate::fmt::Debug + SampleUniform + PartialOrd> Debug for WeightedIndex<X>

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

impl<X: SampleUniform + PartialOrd> StructuralPartialEq for WeightedIndex<X>