[PD] Weighted Randomness

[Frank Barknecht]

Hallo,
Mathieu Bouchard hat gesagt: // Mathieu Bouchard wrote:

> First, the sum all the weights should be 1. If it doesn't, or if you 
> don't know in advance, sum all the weights.
> 
> Then build a second table, in which each element is the sum all 
> (inclusively) previous elements of the first table. This is the sum of the 
> previous element of the second table and the current element of the first 
> table. This second table is the cumulative distribution.
> 
> Then generate a random number between 0 included and the sum of all 
> weights excluded. Finally, scan the table from 0 upwards until you hit any 
> number above the random number. That index is the output value.

Yep, that's what's used in [list-wrandom]

> You don't absolutely need the second table, but it does save a bit of time 
> afterwards.
> 
> If ever you need a much larger table, then it may become too slow, and if 
> so, then write again and I'll explain how to accelerate it.

You made me curious: How would you recommend to make it faster for
large lists? 

Ciao
-- 
 Frank Barknecht                                     _ ______footils.org__