# [Tutor] (No Subject)

**Scott Widney
**
SWidney@ci.las-vegas.nv.us

*Fri, 22 Feb 2002 10:14:30 -0800*

>* someone else suggested this with the disclaimer that it
*>* was not very efficient method and was untested:
*>*
*>* def weighted_choice(choices):
*>* tot = 0
*>* for w,v in choices:
*>* tot = tot + w
*>* d = random.random()*tot
*>* tot = 0
*>* for w,v in choices:
*>* tot = tot + w
*>* if tot > d:
*>* return v
*>*
*
I understand what this is doing, but I see that it's inefficient because it
iterates over the list at least once, possibly twice. It seemed to me that
there ought to be a way to rework this so that it only walks the list once.
This is what I came up with:
###
def weightedPick(weightedList, choice):
""" weightedList is of the form: [('symbol', weight), ...]
where 0.0 < weight < 1.0
"""
if len(weightedList) == 1:
return weightedList[0][0]
if choice < weightedList[0][1]:
return weightedList[0][0]
else:
return weightedPick(weightedList[1:],
(choice - weightedList[0][1]))
###
I pulled random() out of the function to make testing easier, but there are
probably other benefits as well. The function would probably be called this
way:
###
import random
wList = [('three', .3), ('one', .1), ('four', .4), ('two', .2)]
weighedPick(wList, random.random())
###
Some notes:
The function doesn't check to see if the sum of the weights =~ 1.0 (why
would you want anything else?). A Class that wraps the function and the data
could do that. For that matter, the function doesn't ensure that 'choice' is
between 0.0 and 1.0; but that's what random.random() returns. Again, I
suppose that's a job for the Class.
One other thing: I haven't had the chance to run this 1000 or so times to
check its accuracy. Does anyone have the time?
Scott