Mailing List Archive

list = [('one', 25), ('two', 25), ('three', 50)]
l = []
for x, y in list:
l.extend([x] * y)
item=whrandom.choice(list)

Too bulky?


On 21-Jun-99 kevinsl wrote:
> I've been using the whrandom.choice routine and it's very
> useful. But is there any way to add weights or
> probabilities of being chosen to the items in the list?
>
> example:
>
> list=['one','two','three']
> item=whrandom.choice(list)
>
> Is there any way to say that 'one' and 'two' have a 25%
> chance of being chosen, and 'three' has a 50% chance?
>
> I'm hoping there's already a module to do this... or else
> I'll be writing my own..


----------------------------------
Nathan Clegg
nathan@islanddata.com

I'm no expert but....

import whrandom

def popList(l):
selList=[]
for i in l:
for v in range(i[1]):
selList.append(i[0])
return selList

list=popList([('one',25),('two',50),('three',25)])
item=whrandom.choice(list)


--
--Darrell

In this simple case, you could use:

weighted = [0, 1, 2, 2]
item = list[whrandom.choice(weighted)]

If you really need arbitrary weights, try:

list = [('one', 0.25), ('two', 0.25), ('three', 0.5)]
def weighted_choice(list):
from whrandom import uniform
n = uniform(0, 1)
for item, weight in list:
if n < weight:
break
n = n - weight
return item

kevinsl wrote in message <929987267.6227@www.remarq.com>...
I've been using the whrandom.choice routine and it's very
useful. But is there any way to add weights or
probabilities of being chosen to the items in the list?

example:

list=['one','two','three']
item=whrandom.choice(list)

Is there any way to say that 'one' and 'two' have a 25%
chance of being chosen, and 'three' has a 50% chance?

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


def wc_test1(list, cnt=100000):
t1=time.time()
hist={}
for i in range(cnt):
k=wc(list)
if hist.has_key(k):
hist[k]=hist[k]+1
else:
hist[k]=1
print " Time: %.2f sec"%(time.time()-t1)
return hist

def popList(l):
selList=[]
for i in l:
for v in range(i[1]):
selList.append(i[0])
return selList

list2=popList([('one',25),('two',50),('three',25)])

def wc_test2(list, cnt=100000):
t1=time.time()
hist={}
list=popList([('one',25),('two',50),('three',25)])
for i in range(cnt):
k=whrandom.choice(list)
if hist.has_key(k):
hist[k]=hist[k]+1
else:
hist[k]=1
print " Time: %.2f sec"%(time.time()-t1)
return hist


wc_test1(list1)
Time: 10.36 sec
{'one': 25069, 'three': 50087, 'two': 24844}
wc_test2(list2)
Time: 4.52 sec
{'one': 24964, 'two': 50278, 'three': 24758}

Selecting from a list is faster.
--
--Darrell

kevinsl <kevinsl@yahoo.com> writes:

> I've been using the whrandom.choice routine and it's very
> useful. But is there any way to add weights or
> probabilities of being chosen to the items in the list?
>
> example:
>
> list=['one','two','three']
> item=whrandom.choice(list)
>
> Is there any way to say that 'one' and 'two' have a 25%
> chance of being chosen, and 'three' has a 50% chance?

One very obvious, not very extensible, way:

list=['one','two','three','three']
item=whrandom.choice(list)

(NB: list is a builtin; using list as a variable name can lead to
confusion)

A not very efficient but more general method:

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

list=[(0.25,'one'),(0.25,'two'),(0.5,'three')]
weighted_choice(list)

seems to work. Haven't tested it much, so please don't rely on it...

HTH
Michael


> I'm hoping there's already a module to do this... or else
> I'll be writing my own..
>
> thanks,
>
> Kevin

The standard way to do this (with non-integer weights) is to have
a weight associated with each choice, normalized (scaled) so that the
maximum weight is equal to 1.0. Then, after randomly selecting an item
from the collection, generate a uniform random number between 0.0 and
1.0 and accept the choice only if the second random number is less
than the weight of the randomly selected item. If it is not, the item
is not used and you have to repeat the entire process with new
random numbers as many times as needed to get an item for which the
weight exeeds the second random number.

Al


kevinsl wrote:
>
> I've been using the whrandom.choice routine and it's very
> useful. But is there any way to add weights or
> probabilities of being chosen to the items in the list?
>
> example:
>
> list=['one','two','three']
> item=whrandom.choice(list)
>
> Is there any way to say that 'one' and 'two' have a 25%
> chance of being chosen, and 'three' has a 50% chance?
>
> I'm hoping there's already a module to do this... or else
> I'll be writing my own..
>
> thanks,
>
> Kevin
>
> **** Posted from RemarQ - http://www.remarq.com - Discussions Start Here (tm) ****

Did a run of 100000. Looks like it works pretty well.

Time: 5.33 sec
{'one': 24781, 'three': 50148, 'two': 25071}

--Darrell

In article <ERwb3.1452$U6.5885@newsr2.twcny.rr.com>, news@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

Orig:
Time: 10.28 sec
{'one': 25167, 'two': 25144, 'three': 49689}

Terry's:
Time: 9.94 sec
{'one': 24983, 'three': 50020, 'two': 24997}

--
--Darrell

It looks like generating the random number takes much longer than
searching a short list, so that the method I described, which takes
two or more random numbers per selection, is a big loser on speed
unless one is searching a list of 100 elements or more. I think
it might be better for statistical properties of the results,
depending on lots of things (the magnitudes of the weights and
the quality of the rng), but in simple applications, that probably
doesn't matter much, and IDK for sure.

Al


Darrell wrote:
>
> Orig:
> Time: 10.28 sec
> {'one': 25167, 'two': 25144, 'three': 49689}
>
> Terry's:
> Time: 9.94 sec
> {'one': 24983, 'three': 50020, 'two': 24997}
>
> --
> --Darrell