Perl Monk, Perl Meditation | |
PerlMonks |
Re: Re: •Re: Re: Weighted random numbers generatorby no_slogan (Deacon) |
on Mar 13, 2003 at 18:48 UTC ( [id://242789]=note: print w/replies, xml ) | Need Help?? |
But it's only set up once. In merlyn's article, the weights change every time a random value is chosen. It's reasonable that one might want to do that. It seems like it should be possible to set up some kind of search tree that will work in O(log n) time in that situation, but that's making my brain hurt. Update: Couldn't let this go. Use a balanced binary tree. Each node knows its own weight, and the total weight of its subtree. Let $val = rand($tree->{total_weight}) and then
Insertions, deletions, and weight changes must recalculate up to log(n) weights. Now where's the brain specialist... ...up until you need bigints for the indexes. Where are you going to store an array that big?
In Section
Seekers of Perl Wisdom
|
|