News for hackers. Stuff that matters.
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.

Re:Ask HN: Fast sampling and update of weighted items? (data... by gojomo on Wednesday March 25, 2009 @06:18PM (#532530)
Still O(n).