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

There are no comments on this comment yet.