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