Re:Ask HN: Fast sampling and update of weighted items? (data...
by hotpockets on Wednesday March 25, 2009 @03:40PM
(#532321)
As long as the weights are distributed randomly in the array, you can just perform the algorithm on a random subsection of the array. The subsection needs to have the same distribution of weights as the whole section. I think thats the only requirement you need.
Ideally, you could pick smaller fraction of the array as N gets bigger, giving you sub O(N) scaling.
In other words, if the array indexes that get picked using a slow algorithm are distributed randomnly, you might as well just pick a random subsection, as long as it is big enough to have the same distribution of W's as the whole array.
Ideally, you could pick smaller fraction of the array as N gets bigger, giving you sub O(N) scaling.
In other words, if the array indexes that get picked using a slow algorithm are distributed randomnly, you might as well just pick a random subsection, as long as it is big enough to have the same distribution of W's as the whole array.