choosing random numbers with weights/probability?

[Terry Reedy]

In article <ERwb3.1452$U6.5885 at newsr2.twcny.rr.com>, news at dorb.com says...
>
>import time, whrandom
>
>list1 = [('one', 0.25), ('two', 0.25), ('three', 0.5)]
>def wc(list):
>   from whrandom import uniform
>   n = uniform(0, 1)
>   for item, weight in list:
>     if n < weight:
>       break
>     n = n - weight
>   return item

By writing cumulative weights (standard method), the substraction is not 
needed.  Comparison with 1.0 can then be eliminated.  By putting largest 
weights first, the remaining number of comparisons is minimized.  With these 
optimizations, we get:

list1 = [('three', 0.5), ('two', 0.75)] # else 'one'
def wc(list):
   from whrandom import uniform
   n = uniform(0, 1)
   for item, weight in list:
     if n < weight:
       return item
   return 'one'

If there were a enough categories, then binary search of the list (with the 
last item with cumulative weight 1.0 added back) would be faster.

Terry J. Reedy