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.