Re: Weighted random numbers generator

Your way is basically to redistribute the random numbers generated by random(). Seems to me, the problem is that its performance would go down, when the number of sections goes up. It is an ~o(n), and the internal random() is o(1).

Perl’s algorithm to generate random number is in the same algorithm family with the following: (srand() plays the role to determine the initial seed).

this_seed = (last_seed * 69069) % 2 ** 32; (equation 1)
this_random_number = this_seed / 2 ** 32; (equation 2)

You may want to play with it, and see whether you can find a way to distribute the numbers weighted, and at the same time sacrifice less performance.

Update

Agree with no_slogan, binary search, if you choose to stick with random().

Comment on Re: Weighted random numbers generator

Replies are listed 'Best First'.
Re: Re: Weighted random numbers generator by no_slogan (Deacon) on Mar 13, 2003 at 17:57 UTC
Seems to me, the problem is that its performance would go down, when the number of sections goes up. It is an ~o(n), and the internal random() is o(1). Using a modified binary search, you can get O(log n) performance. You'll need to precompute `@acc_arr` instead of building it on the fly, of course. See Math::IntervalSearch, though that's not optimized for the random number generation case. If the weights aren't too vastly different (for example, `[(1) x 1000, 1_000_000]`), you can get a O(1) solution by slicing up `@acc_arr` into equal-sized intervals. Details left as an exercise for the reader. Update: This is roughly what dga is proposing. With care, it's possible to remove the rounding-off from his solution.	[reply] [d/l]
Re: Re: Weighted random numbers generator by Eimi Metamorphoumai (Deacon) on Mar 13, 2003 at 17:44 UTC
There's no way you can possibly do it in better than O(n) time, since you're going to have to look at each weight at least once (otherwise, ((1)x100, 10000) wouldn't be treated properly).	[reply]


Don't ask to ask, just ask
	PerlMonks