News for hackers. Stuff that matters.
Re:Ask HN: Fast sampling and update of weighted items? (data... by loicfevrier on Wednesday March 25, 2009 @03:30PM (#532299)
Red-black trees are far too complex for this simple task : just use any binary balanced tree so that the maximum height is O(log n). (red-black trees will work but take any one you want, red-black tree are slow) On each node you store two numbers : - sum of the weights at the left - sum of the weights at the right Want you want to choose an item just explore the tree and for each node choose left or right according to the two weights. ==> O(log n) If you update an item you'll need to update all the weight up to the root of the tree. ==> O(log n) for each update
Re:Ask HN: Fast sampling and update of weighted items? (data... by nkurz on Wednesday March 25, 2009 @05:48PM (#532488)
I don't think I'm quite understanding your algorithm. When you say "choose left or right", do you mean to choose randomly between the branches with probability equal to the ratio of the weights of the trees? So that each sample requires log(n) random numbers before you reach a leaf? Or do you mean something else?
Re:Ask HN: Fast sampling and update of weighted items? (data... by bravura on Wednesday March 25, 2009 @06:08PM (#532514)
You know the sum of the weights. Sample a random number between 0 and sum. Then, use this value to guide your search in the tree. For example, if the left branch has weight 30 and the right branch has weight 50, the total weight is 80. If I pick 40, then I am going down the right branch.

At the next child, if the left branch has weight 12 and the right branch has weight 38, the left branch spans 30-42 and the right branch spans 42-80. So you follow the left branch, because you want 40.

Re:Ask HN: Fast sampling and update of weighted items? (data... by praptak on Wednesday March 25, 2009 @06:10PM (#532521)
Basically, yes - branches are chosen with probabilities proportional to their weights, but you can achieve that with just one random float.

Just pick a random x from [0, sum of weights in the tree], then find a node n, such that sum of weights S to the left of n is no more than x and S+weight(n)>=x.

Re:Ask HN: Fast sampling and update of weighted items? (data... by bravura on Wednesday March 25, 2009 @04:45PM (#532405)
The more I think about your solution, the more correct and elegant it seems. Cheers!