Re: [Tutor] Weighted Random Choice - Anyone have an efficient algorithm?
Hi Steven,
Doesn't this qualify as 'monkeying with the loop index'? [*]
>>> import random
>>> weights = [5, 20, 75]
>>> counts = {0:0, 1:0, 2:0}
>>> for i in xrange(100):
... i = weighted_choice(weights) # <--- monkeying right here (?)
... counts[i] += 1
[*] http://stackoverflow.com/questions/457036/dont-monkey-with-the-loop-index
Cheers!!
Albert-Jan
~~
All right, but apart from the sanitation, the medicine, education, wine, public
order, irrigation, roads, a fresh water system, and public health, what have
the
Romans ever done for us?
~~
From: Steven D'Aprano
To: tutor@python.org
Sent: Thu, December 23, 2010 1:30:50 PM
Subject: Re: [Tutor] Weighted Random Choice - Anyone have an efficient
algorithm?
Modulok wrote:
> Does anyone know of an efficient way of doing a weighted random
> choice? (I don't even know what algorithms like this would be called.)
If you google for "python weighted random choice" you will find a number of
hits.
> Preferably, something that doesn't grow exponentially with the number
> of elements in the list, or the size of their respective values.
Here's one method that is linear on the number of elements:
def weighted_choice(weights):
total = sum(weights)
p = random.uniform(0, total) # random float between 0 and total.
assert 0.0 <= p <= total
# Do a linear search for the right index value. If you have a
# huge number of weights, a binary search may be faster.
running_total = 0
for i, weight in enumerate(weights):
running_total += weight
if p <= running_total:
return i
And tested:
>>> import random
>>> weights = [5, 20, 75]
>>> counts = {0:0, 1:0, 2:0}
>>> for i in xrange(100):
... i = weighted_choice(weights)
... counts[i] += 1
...
>>> counts
{0: 50252, 1: 17, 2: 749751}
>>> [n*1e6/100 for n in weights] # expected values
[5.0, 20.0, 75.0]
As you can see, the results are very close to what should be expected, and of
course the difference can be chalked up to random chance.
-- Steven
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Weighted Random Choice - Anyone have an efficient algorithm?
On 01/-10/-28163 02:59 PM, Albert-Jan Roskam wrote:
Hi Steven,
Doesn't this qualify as 'monkeying with the loop index'? [*]
import random
weights = [5, 20, 75]
counts = {0:0, 1:0, 2:0}
for i in xrange(100):
... i = weighted_choice(weights) #<--- monkeying right here (?)
... counts[i] += 1
[*] http://stackoverflow.com/questions/457036/dont-monkey-with-the-loop-index
(please don't top-post in these forums)
Your citation is for C#, where the loop index does indeed get changed.
In Python a loop protects itself against such monkeying, so the example
still executes a million times.
It still would be better to use a different temp variable for clarity,
but it's not as important as in other languages.
DaveA
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Problems processing accented characters in ISO-8859-1 encoded texts
Josep M. Fontana wrote: Just one more question. You say that \w means alphanumeric, not just alpha. Is there any expression that would mean "just alpha" and (given the appropriate LOCALE setting) would match 'a' and 'รถ' but not '9'? Unfortunately, I don't think there is a standard code for just alpha. Apart from listing all the characters individually, I haven't been able to find a way to get the result you want, but I'll admit I haven't tried that hard. Perhaps somebody with more regex skills can answer? -- Steven ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Weighted Random Choice - Anyone have an efficientalgorithm?
"Albert-Jan Roskam" wrote
Doesn't this qualify as 'monkeying with the loop index'? [*]
import random
weights = [5, 20, 75]
counts = {0:0, 1:0, 2:0}
for i in xrange(100):
... i = weighted_choice(weights) # <--- monkeying right here (?)
... counts[i] += 1
Not really because the for loop value is not being used as an index.
It could just as well have been written:
for n in xrange(100):
... i = weighted_choice(weights) # <--- monkeying right here (?)
... counts[i] += 1
The n is not used except to ensure there are a million iterations.
So reusing the name inside the loop body doesn't have any
bad effects. But keeping to a separate name might have been
slightly more readable.
HTH,
--
Alan Gauld
Author of the Learn to Program web site
http://www.alan-g.me.uk/
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
[Tutor] A class list
I am working on the second part of the 'Bingo' problem defined at the Bingo Praxis web page, http://programmingpraxis.com/2009/02/19/bingo/. My notes as how to best define and build the problem: 'In a large game with five hundred cards in play, what is the average number of calls required before any card achieves bingo?' In this version of the simulation we generate 500 unique cards which, by definition, implies 500 players. Initially, the rules insist there is only one pass through the cage. Since there are 500 players, we have to define a methodology such that the order of play is random. We first create 500 cards and assign them to a list so that the first card is referenced by cardlist[0] and the last card is represented by cardlist[499]. We then generate a random non-replaceable list of these same values (0-499). This becomes the ordering queue of which card will be played with the current value pulled from the cage. list.pop() determines the card in action. Since we only care about the game until it is won, as soon as one card has bingo, the entire game is finished and the value of all other cards is not considered in the simulation. The call counter is incremented every time the cage is accessed. I am building the program in incremental steps with each step to accomplish a set functionality. Each step I hope is designed to be tested with relative simplicity and rather obvious points of success and failure. The first function is simply to create an array(list) of classes. Rather than testing for 500 cards in the list, I am currently using 5 cards. Both the class and the list building function can be seen at: http://pastebin.com/QNPVec8L . The problem that is confounding me is that the list is returned where any member of bingocard.mycard is identical to all the other members of bingocard.mycard in the list. Through a number of tests I have learned that the last card of the list seems to permeate upward to the first. I have researched building a list of classes and I think I have done it correctly, but obviously at this point I am not going to say it should work. What I am asking is 1) Why is the function doing what it is doing rather than what I thought I programmed it to do, and 2) How can I code it to do what I want it to do: Produce N number of non duplicated cards. OS: Windows 7. Python version 2.6.4 IDE: Pycharm 1.1 EAP Thank you for any and all assistance. Robert -- I am using the free version of SPAMfighter. We are a community of 7 million users fighting spam. SPAMfighter has removed 174 of my spam emails to date. Get the free SPAMfighter here: http://www.spamfighter.com/len The Professional version does not have this message ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] A class list
From: Noah Hall [mailto:enali...@gmail.com]
Sent: Friday, December 24, 2010 2:36 PM
To: Robert Berman
Subject: Re: [Tutor] A class list
Alright, I'll begin by saying that you shouldn't use a list for cards , and a
separate one for players. Instead, you should use dictionaries. For example -
players = { 1: "John", 2:"Phil",..,n:"Ed"}
Or, using your method -
for x in random.sample(xrange(low,high),n):
players[x] = random.sample(list_of_names, len(list_of_names))
When I get back from holiday, I'll go through your code more thoroughly and
give you a pointer in the right direction.
>> Really big snip.
Noah,
Thanks for your prompt reply which generates its own unique question. You are
saying I should have some concern for the players. But I don't care about the
people playing. I care about the cards in play and the card that reaches
Bingo. I care about the winner only to the extent I want to know how many
numbers have been pulled from the cage for him/her to achieve Bingo. Other
than that, I don't care so please elaborate why I care about the players;
Besides I really cannot see why I should generate names(n) when card(n) will
do just as nicely; I think.
Thanks again,
Robert
_
I am using the Free version of SPAMfighter .
SPAMfighter has removed 174 of my spam emails to date.
Do you have a slow PC?
Try free scan!
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] A class list
On 12/24/2010 11:09 AM Robert Berman said... 1) Why is the function doing what it is doing rather than what I thought I programmed it to do, you've only got one mycard at the class level that's shared between the instances. and 2) How can I code it to do what I want it to do: Produce N number of non duplicated cards. I swapped colranges (which can be shared) and mycard (which needs to be an instance variable.) HTH, Emile class bingocard: colranges = [ [1,15], [16,30], [31,45], [46,60], [61,75] ] nbrcalls = 0 nbrhits = 1 def __init__(self): self.mycard = [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0] ] col = 0 while col < 5: row = 0 low = bingocard.colranges[col][0] high = bingocard.colranges[col][1] vallst = random.sample(range(low,high),5) for x in vallst: self.mycard[row][col] = x row += 1 col += 1 self.mycard[2][2] += 100 ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] A class list
Based on what you initally stated, that you would have a list containing 500
numbers, and for each number, there would be a player, using a dict would be
ideal. For example, once you've got the winning number, how do you then
intend on handling what happens to each player as they win? Do you intend to
forget them? The player index need not be a name - it could be a number,
simply referring to the player, and then storing each number that player
stores in a list, for example
players = {1:[0,0,0,0,0]n:[0,0,0,0,0]}
This is just some food for thought.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] A class list
On 01/-10/-28163 02:59 PM, Robert Berman wrote: I am working on the second part of the 'Bingo' problem defined at the Bingo Praxis web page, http://programmingpraxis.com/2009/02/19/bingo/. My notes as how to best define and build the problem: 'In a large game with five hundred cards in play, what is the average number of calls required before any card achieves bingo?' In this version of the simulation we generate 500 unique cards which, by definition, implies 500 players. Initially, the rules insist there is only one pass through the cage. Since there are 500 players, we have to define a methodology such that the order of play is random. We first create 500 cards and assign them to a list so that the first card is referenced by cardlist[0] and the last card is represented by cardlist[499]. We then generate a random non-replaceable list of these same values (0-499). This becomes the ordering queue of which card will be played with the current value pulled from the cage. list.pop() determines the card in action. Since we only care about the game until it is won, as soon as one card has bingo, the entire game is finished and the value of all other cards is not considered in the simulation. The call counter is incremented every time the cage is accessed. I am building the program in incremental steps with each step to accomplish a set functionality. Each step I hope is designed to be tested with relative simplicity and rather obvious points of success and failure. The first function is simply to create an array(list) of classes. Rather than testing for 500 cards in the list, I am currently using 5 cards. Both the class and the list building function can be seen at: http://pastebin.com/QNPVec8L . The problem that is confounding me is that the list is returned where any member of bingocard.mycard is identical to all the other members of bingocard.mycard in the list. Through a number of tests I have learned that the last card of the list seems to permeate upward to the first. I have researched building a list of classes and I think I have done it correctly, but obviously at this point I am not going to say it should work. What I am asking is 1) Why is the function doing what it is doing rather than what I thought I programmed it to do, and 2) How can I code it to do what I want it to do: Produce N number of non duplicated cards. OS: Windows 7. Python version 2.6.4 IDE: Pycharm 1.1 EAP Thank you for any and all assistance. Robert I didn't study the whole code listing, but there's an obvious problem you need to address first. You only have one instance of the mycard list. You made it a class attribute, while you meant to make it an instance attribute. So your first change should be to move that code inside the __init__ method, and of course precede it with "self". DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
