News for hackers. Stuff that matters.
Re:Ask HN: Fast sampling and update of weighted items? (data... by drcode on Wednesday March 25, 2009 @03:20PM (#532277)
First, put all items into an array, computing a number k for each item, where k=(sum of all weights above it).

Then, just generate a random number 0<x<(sum of all weights).

Finally, do a binary search on the array O(log(n)) comparing x to k.

...As for the "updating" step, you didn't define that very well or state whether you're interested in minimizing that as well- But given that the number of items may be as large as N it seems that a naive linear update would be the best you could achieve.

Re:Ask HN: Fast sampling and update of weighted items? (data... by loicfevrier on Wednesday March 25, 2009 @03:29PM (#532296)
But you will need to re-compute the sum each time you are doing an update wich takes O(n). You can use Binary Indexed Trees to do that efficiently : http://www.topcoder.com/tc?module=Static&d1=tutorials...
Re:Ask HN: Fast sampling and update of weighted items? (data... by bravura on Wednesday March 25, 2009 @04:25PM (#532375)
It appears that Binary Indexed Trees are appropriate only when the weights are integral?
Re:Ask HN: Fast sampling and update of weighted items? (data... by loicfevrier on Wednesday March 25, 2009 @04:44PM (#532401)
Exact, I forgot that point.