[Tutor] (No Subject)

[Scott Widney]

> 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