Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: •Re: Re: Weighted random numbers generator

by Zaxo (Archbishop)
on Mar 13, 2003 at 18:28 UTC ( [id://242781]=note: print w/replies, xml ) Need Help??


in reply to •Re: Re: Weighted random numbers generator
in thread Weighted random numbers generator

But it's only set up once. That's why the closure. Overhead is not charged in scaling arguments, and array indexing is certainly O(1) for positional representations - up until you need bigints for the indexes.

After Compline,
Zaxo

Replies are listed 'Best First'.
Re: Re: •Re: Re: Weighted random numbers generator
by no_slogan (Deacon) on Mar 13, 2003 at 18:48 UTC
    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

    sub search { my ($tree, $val) = @_; return $tree if $val < $tree->{weight}; $val -= $tree->{weight}; return search($tree->{left}, $val) if $val < $tree->{left}->{total_w +eght}; $val -= $tree->{left}->{total_weight}; return search($tree->{right}, $val); }

    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?

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://242781]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (7)
As of 2024-03-28 13:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found