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.
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.