Rust Random Choice

I created a new, very small random lib for choosing randomly samples by their weights/probabilites.
As far as I know this feature is not part of the random crate. So may be there is interest to merge this lib to rust random.

###Advantages

  • There is a good diversity for the case that all weights are equally distributed (in contrast to the roulette wheel selection algorithm which tends to select the same sample n times)
  • Blazingly fast: O(n) (Roulette wheel selection algorithm: O(n * log n))
  • The sum of the weights don't have to be 1.0, but must not overflow

This algorithm is based on the Low Variance Resampling algorithm.

###Applications

  • Evolutionary algorithms: Choose the fittest population with fitness x
  • Monte Carlo Localization: Resampling of particles with weight w

I have to rewrite the comments in rust style. I will do this on tuesday, because right now I have to study for exams.

https://github.com/StefanoD/Rust_Random_Choice

4 Likes

Finally available on crates.io!