[PD] Weighted Randomness

Frank Barknecht fbar at footils.org
Sat Oct 13 11:49:25 CEST 2007

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? 

 Frank Barknecht                                     _ ______footils.org__

More information about the Pd-list mailing list