pub struct WeightedIndex<X>where
X: SampleUniform + PartialOrd,{ /* 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:
rand_distr::weighted_alias
supportsO(1)
sampling, but with much higher initialisation cost.rand_distr::weighted_tree
keeps the weights in a tree structure where sampling and updating isO(log N)
.
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::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§
Source§impl<X> WeightedIndex<X>where
X: SampleUniform + PartialOrd,
impl<X> WeightedIndex<X>where
X: SampleUniform + PartialOrd,
Sourcepub fn new<I>(weights: I) -> Result<WeightedIndex<X>, WeightError>
pub fn new<I>(weights: I) -> Result<WeightedIndex<X>, WeightError>
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:
WeightError::InvalidInput
when the iteratorweights
is empty.WeightError::InvalidWeight
when a weight is not-a-number or negative.WeightError::InsufficientNonZero
when the sum of all weights is zero.WeightError::Overflow
when the sum of all weights overflows.
Sourcepub fn update_weights(
&mut self,
new_weights: &[(usize, &X)],
) -> Result<(), WeightError>
pub fn update_weights( &mut self, new_weights: &[(usize, &X)], ) -> Result<(), WeightError>
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:
WeightError::InvalidInput
whennew_weights
are not ordered by index or an index is too large.WeightError::InvalidWeight
when a weight is not-a-number or negative.WeightError::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)
.
Source§impl<X> WeightedIndex<X>
impl<X> WeightedIndex<X>
Sourcepub fn weight(&self, index: usize) -> Option<X>
pub fn weight(&self, index: usize) -> Option<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::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);
Sourcepub fn weights(&self) -> WeightedIndexIter<'_, X>
pub fn weights(&self) -> WeightedIndexIter<'_, 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::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]);
Sourcepub fn total_weight(&self) -> X
pub fn total_weight(&self) -> X
Returns the sum of all weights in this distribution.
Trait Implementations§
Source§impl<X> Clone for WeightedIndex<X>
impl<X> Clone for WeightedIndex<X>
Source§fn clone(&self) -> WeightedIndex<X>
fn clone(&self) -> WeightedIndex<X>
1.0.0 · Source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more