search

google / guava

Google core libraries for Java
Apache License 2.0
50.03k stars 10.86k forks source link

Add a random weighted selector #2041

Open ogregoire opened 9 years ago

ogregoire commented 9 years ago

I've often had to implement a random weighted selector in my various assignments (mostly for routing). As most programmers, I've turned to StackOverflow to find a solution to this issue. Most of the solutions suggested by Google on SO use algorithms with an init in O(n) and a get in O(n) or O(log n). The thing is that some nice solutions exist with O(n) for the init and O(1) for the get method, for instance. And those are mostly unknown, I think mostly about the "alias method" which return a value in O(1).

I've implemented a generalized RandomSelector to solve the random selection issue with both a uniform and a weighted implementations.

If you feel that this is indeed something that the Guava users might need, feel free to copy it / inspire from it (CLA is signed).

aliakhtar commented 6 years ago

I'm using this library in a project and have had pretty good results. Makes getting random weighted values really simple. Recommended. Should be merged IMO.