[PD] Weighted Randomness

[Mathieu Bouchard]

On Sat, 13 Oct 2007, Frank Barknecht wrote:
> Mathieu Bouchard hat gesagt: // Mathieu Bouchard wrote:
>
>> 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?

You make a binary search in the array. Suppose every element could be what 
you look for. Look at the value in the middle element. You know that 
elements are already sorted (because they are cumulative of a nonnegative 
function) so you can eliminate all possibilities on one of the sides of 
the middle element. Then you pick a new middle... You can go through a 
1024-element array in 10 steps using just [<].

So, this is the real reason for cumulating: you can't use that trick if 
you don't cumulate.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada