# Struct rand::distributions::WeightedIndex

source · `pub struct WeightedIndex<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`

supports`O(1)`

sampling, but with much higher initialisation cost.`rand_distr::weighted_tree`

keeps the weights in a tree structure where sampling and updating is`O(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::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: SampleUniform + PartialOrd> WeightedIndex<X>

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

source#### pub 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 iterator`weights`

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.

source#### pub 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`

when`new_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: SampleUniform + PartialOrd + Clone> WeightedIndex<X>

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

source#### pub 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::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>

#### 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::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

#### pub fn total_weight(&self) -> X

Returns the sum of all weights in this distribution.

## Trait Implementations§

source§### impl<X: Clone + SampleUniform + PartialOrd> Clone for WeightedIndex<X>

### impl<X: Clone + SampleUniform + PartialOrd> 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 moresource§### impl<X: Debug + SampleUniform + PartialOrd> Debug for WeightedIndex<X>

### impl<X: Debug + SampleUniform + PartialOrd> Debug for WeightedIndex<X>

source§### impl<'de, X> Deserialize<'de> for WeightedIndex<X>

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

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

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

source§### impl<X> Distribution<usize> for WeightedIndex<X>where
X: SampleUniform + PartialOrd,

### impl<X> Distribution<usize> for WeightedIndex<X>where
X: SampleUniform + PartialOrd,

source§### impl<X: PartialEq + SampleUniform + PartialOrd> PartialEq for WeightedIndex<X>

### impl<X: PartialEq + SampleUniform + PartialOrd> PartialEq for WeightedIndex<X>

source§#### fn eq(&self, other: &WeightedIndex<X>) -> bool

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

`self`

and `other`

values to be equal, and is used
by `==`

.