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.

The API documentation is here.

Usage

Add this to your Cargo.toml:

[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 cheating_coin = ["Heads!", "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
    // external ThreadRng instance.
    let mut result = [""; 10000];
    let mut rng = rand::thread_rng();
    for r in &mut result {
        let j = wa_table.next_rng(&mut rng);
        *r = cheating_coin[j];
    }

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

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.