Re:Ask HN: Fast sampling and update of weighted items? (data...
by bravura on Wednesday March 25, 2009 @04:21PM
(#532369)
Rejection sampling is perhaps not a good option, because the assumption does not hold: "the maximum weight isn't too much greater than the average weight"
In learning algorithms, the distribution of the weights can get piqued.
1) Determine the maximum weight mw. (This is O(N) the first time, O(K) subsequent times.)
2) Repeat until an index i is accepted:
3) Return the accepted index i.This gives you the desired distribution in time O(mw/aw) (maximum weight over average weight).