4 ms·
Fast Proportional Selection
- rawnlq 10y agoHave you tried the Alias Method? https://en.wikipedia.org/wiki/Alias_method https://en.wikipedia.org/wiki/Alias_method
- orasis 10y agoWhat is this used for?
- sevensor 10y agoI can't speak for the OP, but proportional selection is often used in genetic algorithms. For GAs it's usually not the best selection operator.
- sevensor 10y agoBefore optimizing proportional selection, make sure that proportional selection is what you want! For population-based search algorithms like GAs, tournament selection is a better choice in most cases. It also has the benefit of being O(1), albeit with a bigger constant time because you have select several individuals and then resolve the tournament.
- ahh 10y agoYou can actually do adjustable weight sampling in logarithmic time using a modification of the binary search approach, which is likely superior in a lot of cases. The trick is to keep a dense binary tree (arbitrary order--you can use the standard array mapping), where each leaf has one of your w_i and each internal node is the sum of its two children (and therefore equals the sum of all leaves in its subtree.) To update one weight, you just walk up the tree. To sample, you walk down the tree making a weighted decision at each point. This allows log n time update and sampling. It can be quite fast in practice, though the alias method is faster if you don't need adjustable weights. There are all sorts of other issues with RNG generation of doubles that affect these cases, though - I need to write a longer post about what I've done here.
- chrchang523 10y agoAn algorithm that generates (an average of) O(n) random variates has time complexity at least O(n), not O(1).