Re:Ask HN: Fast sampling and update of weighted items? (data...
by jonnyba on Wednesday March 25, 2009 @03:37PM
(#532316)
if the number of different weights is finite and small, you could create a bucket for each different weight.
for example if the possible weights are .25, .5, and .75, put all items into one of those buckets (array backed). The bucket then gets a weight of (individual weight)*(bucket size). First randomly choose a bucket based on the bucket weight, then randomly choose an object from the bucket.
for example if the possible weights are .25, .5, and .75, put all items into one of those buckets (array backed). The bucket then gets a weight of (individual weight)*(bucket size). First randomly choose a bucket based on the bucket weight, then randomly choose an object from the bucket.