Vose Alias

A Rust implementation of the Vose-Alias Algorithm. This algorithm allows to sample an element from a list given a discrete probability distribution.

For a vecotr of n elements, the initialization time is O(n), the sampling time is O(1), and the memory usage is O(n).

Usage

Add this to your Cargo.toml

[dependencies]
vose-alias = "1.0.0"

Example

use vose_alias::VoseAlias

let va = VoseAlias::new(vec!["orange", "yellow", "green", "turquoise", "grey", "blue", "pink"], vec![0.125, 0.2, 0.1, 0.25, 0.1, 0.1, 0.125]);
let element = va.sample();

Crate functionalities

This crate provides a VoseAlias structure, that stores the list of elements given by the user of the library, as well as the probability and alias tables. The probability and alias tables are created by the new function.

The crate also provides a sample function, that allows to sample an element from the element vector in constant time. The function returns the element directly.

External Resources

For a description of the method implemented as well as the algorithm (in pseudo-code), see [https://www.keithschwarz.com/darts-dice-coins/]