6 releases (3 breaking)
0.4.1  Jul 3, 2023 

0.4.0 

0.3.2  Nov 11, 2021 
0.2.0  Nov 8, 2021 
0.1.0  Nov 7, 2021 
#201 in Algorithms
201 downloads per month
Used in 3 crates
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
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 (LICENSEAPACHE or http://www.apache.org/licenses/LICENSE2.0)
 MIT license (LICENSEMIT 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 Apache2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Dependencies
~0.7–1.3MB
~30K SLoC