## weighted_rand

A weighted random sampling crate using Walker's Alias Method

### 6 releases(3 breaking)

 0.4.1 Jul 3, 2023 Jul 3, 2023 Nov 11, 2021 Nov 8, 2021 Nov 7, 2021

#201 in Algorithms

Used in 3 crates

MIT/Apache

19KB
258 lines

# weighted_rand

A weighted random sampling crate using Walker's Alias Method.

Walker's Alias Method (WAM) is one method for performing weighted random sampling.
WAM weights each index of a array by giving two pieces of information: an alias to a different index and a probability to decide whether to jump to that index.

WAM is a very fast algorithm, and its computational complexity of the search is O(1).
The difference in complexity between WAM and the Cumulative Sum Method is as follows.

Algorithm Building table Search
Walker's Alias Method O(N) O(1)
Cumulative Sum Method O(N) O(log N)

The API documentation is here.

## Usage

``````[dependencies]
weighted_rand = "0.4"
``````

## Example

``````use weighted_rand::builder::WalkerTableBuilder;

fn main() {
let fruit = ["Apple", "Banana", "Orange", "Peach"];

// Define the weights for each index corresponding
// to the above list.
// In the following case, the ratio of each weight
// is "2 : 1 : 7 : 0", and the output probabilities
// for each index are 0.2, 0.1, 0.7 and 0.
let index_weights = [2, 1, 7, 0];

let builder = WalkerTableBuilder::new(&index_weights);
let wa_table = builder.build();

for i in (0..10).map(|_| wa_table.next()) {
println!("{}", fruit[i]);
}
}
``````

Also, `index_weiaghts` supports `&[f32]`, like:

``````use rand;
use weighted_rand::builder::*;

fn main() {
// Coin with a 5% higher probability of heads than tails
let index_weights = [0.55, 0.45];

let builder = WalkerTableBuilder::new(&index_weights);
let wa_table = builder.build();

// If you want to process something in a large number of
// loops, we recommend using the next_rng method with an
let mut result = [""; 10000];
for r in &mut result {
let j = wa_table.next_rng(&mut rng);
*r = cheating_coin[j];
}

// println!("{:?}", result);
}
``````