472,330 Members | 1,236 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,330 software developers and data experts.

Random Drawing Simulation -- performance issue

I need to simulate scenarios like the following: "You have a deck of
3 orange cards, 5 yellow cards, and 2 blue cards. You draw a card,
replace it, and repeat N times."

So, I wrote the following code, which works, but it seems quite slow
to me. Can anyone point out some obvious thing that I'm doing
inefficiently? Or, is this more or less as good as it gets?

For reference, my typical numbers look like this:

2 <= len(population) <= 7
4 <= len(mapping) <= 50
10 <= count <= 1000000

B.

<code>
#!/usr/bin/env python

import random

def randomDrawing(count, population):
"""Simulates drawing <countitems from <population>, with
replacement.
population is a list of lists: [[count1, type1], [count2,
type2], ...]

Typical examples:
>>>randomDrawing(100, [[3, 'orange'], [5, 'yellow'], [2, 'blue']])
[[28, 'orange'], [57, 'yellow'], [15, 'blue']]
>>>randomDrawing(100000, [[3, 'orange'], [5, 'yellow'], [2,
'blue']])
[[29923, 'orange'], [50208, 'yellow'], [19869, 'blue']]

"""
res = [[0, item[1]] for item in population]
mapping = []
for i in xrange(len(population)):
mapping.extend([i]*population[i][0])
for i in xrange(count):
index = random.choice(mapping)
res[index][0] += 1
return res

</code>

--
Brendon Towle, PhD
Cognitive Scientist
+1-412-690-2442x127
Carnegie Learning, Inc.
The Cognitive Tutor Company
Helping over 375,000 students in 1000 school districts succeed in math.
Sep 12 '06 #1
2 2132
Brendon Towle wrote:
I need to simulate scenarios like the following: "You have a deck of 3
orange cards, 5 yellow cards, and 2 blue cards. You draw a card, replace
it, and repeat N times."

So, I wrote the following code, which works, but it seems quite slow to
me. Can anyone point out some obvious thing that I'm doing
inefficiently? Or, is this more or less as good as it gets?

For reference, my typical numbers look like this:

2 <= len(population) <= 7
4 <= len(mapping) <= 50
10 <= count <= 1000000

B.

<code>
#!/usr/bin/env python

import random

def randomDrawing(count, population):
"""Simulates drawing <countitems from <population>, with replacement.
population is a list of lists: [[count1, type1], [count2, type2], ...]

Typical examples:
>>>randomDrawing(100, [[3, 'orange'], [5, 'yellow'], [2, 'blue']])
[[28, 'orange'], [57, 'yellow'], [15, 'blue']]
>>>randomDrawing(100000, [[3, 'orange'], [5, 'yellow'], [2, 'blue']])
[[29923, 'orange'], [50208, 'yellow'], [19869, 'blue']]

"""
res = [[0, item[1]] for item in population]
mapping = []
for i in xrange(len(population)):
mapping.extend([i]*population[i][0])
for i in xrange(count):
index = random.choice(mapping)
res[index][0] += 1
return res

</code>

--Brendon Towle, PhD
Cognitive Scientist
+1-412-690-2442x127
Carnegie Learning, Inc.
The Cognitive Tutor Company
Helping over 375,000 students in 1000 school districts succeed in math.

Given the data structure, might it not be faster to generate binomial
variates for n-1 types, and set nth count = #draws - sum(other
outcomes)? And for a "large" count, could you get by with a normal
approximation? If you *do* feel the need for exact binomial, there are
short, somewhat sluggish routines in Devroye (1986 - on the web!, pg
525), and Random_binomial1, compiled by Alan Miller(AMrandom.zip0,
available, xlated, at http://www.esbconsult.com/. Even though they are
relatively slow, generating a few of these would seem to be a lot faster
than your current approach.

Sorry I can't help more - I'm just starting to learn Python, have yet to
even get IDLE going.

Regards,
Dave Braden
Sep 12 '06 #2
Brendon Towle wrote:
I need to simulate scenarios like the following: "You have a deck of
3 orange cards, 5 yellow cards, and 2 blue cards. You draw a card,
replace it, and repeat N times."

So, I wrote the following code, which works, but it seems quite slow
to me. Can anyone point out some obvious thing that I'm doing
inefficiently? Or, is this more or less as good as it gets?

For reference, my typical numbers look like this:

2 <= len(population) <= 7
4 <= len(mapping) <= 50
10 <= count <= 1000000

B.

<code>
#!/usr/bin/env python

import random

def randomDrawing(count, population):
"""Simulates drawing <countitems from <population>, with
replacement.
population is a list of lists: [[count1, type1], [count2,
type2], ...]

Typical examples:
>>>randomDrawing(100, [[3, 'orange'], [5, 'yellow'], [2, 'blue']])
[[28, 'orange'], [57, 'yellow'], [15, 'blue']]
>>>randomDrawing(100000, [[3, 'orange'], [5, 'yellow'], [2,
'blue']])
[[29923, 'orange'], [50208, 'yellow'], [19869, 'blue']]

"""
res = [[0, item[1]] for item in population]
mapping = []
for i in xrange(len(population)):
mapping.extend([i]*population[i][0])
for i in xrange(count):
index = random.choice(mapping)
res[index][0] += 1
return res

</code>

--
Brendon Towle, PhD
Cognitive Scientist
+1-412-690-2442x127
Carnegie Learning, Inc.
The Cognitive Tutor Company
Helping over 375,000 students in 1000 school districts succeed in math.
I got nearly a 2x speed up with this variant:

def randomDrawing3(count, population):
res = [[0, item[1]] for item in population]
mapping = []
for i in xrange(len(population)):
mapping.extend([i]*population[i][0])

n = len(mapping)
for i in xrange(count):
index = int(n * random.random())
res[mapping[index]][0] += 1

return res
Apparently "int(n * random.random())" is faster than random.choice()
or random.randint()

sforman@garbage:~ $ python -mtimeit -s'import random; n=10' 'int(n *
random.random())'
100000 loops, best of 3: 3.22 usec per loop

sforman@garbage:~ $ python -mtimeit -s'import random; n=10'
'random.randint(1, n)'
100000 loops, best of 3: 13 usec per loop

sforman@garbage:~ $ python -mtimeit -s'import random; n=range(10)'
'random.choice(n)'
100000 loops, best of 3: 6.07 usec per loop

(Note that the first and last examples produce values 0..9 while the
middle one produces 1..10)
I don't know for sure, but I think the random, uh, spread or whatever
will be the same for random() as for choice(). If it's important, you
should verify that. ;-)

Peace,
~Simon

Sep 12 '06 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: Constandinos Mavromoustakis | last post by:
Dear all, first we apologize if you receive multiple copies of this announcement. please see below if you are interested. Thank you in...
28
by: Paul Rubin | last post by:
http://www.nightsong.com/phr/python/sharandom.c This is intended to be less predicable/have fewer correlations than the default Mersenne Twister...
0
by: Constandinos Mavromoustakis | last post by:
http://agent.csd.auth.gr/~cmavrom --------------------------------------------------...
0
by: Gus | last post by:
---------------------------------------------------------------------------- ------------------------------------ Call for Papers: 38th Annual...
0
by: Karatza Helen | last post by:
Our apologies if you have received multiple copies -------------------------------------------------- Call for Papers: 38th Annual Simulation...
21
by: Marc Dansereau | last post by:
Hi all I am new to this forum and to the c programming language. If I understand, the random() function in C return numbers that follow a...
4
by: tshad | last post by:
I am trying to set up an Image authorization where you type in the value that is in a picture to log on to our site. I found a program that is...
6
by: Intiha | last post by:
Hello all, I am trying to generate random seeds for my simulations. currently i was using srand(time(NULL); for this purpose. But for confidence...
6
by: Mike Langworthy | last post by:
i can not seem to get this code to work. someone please help using System; using System.Collections.Generic; using System.Text; namespace...
0
by: tammygombez | last post by:
Hey everyone! I've been researching gaming laptops lately, and I must say, they can get pretty expensive. However, I've come across some great...
0
by: concettolabs | last post by:
In today's business world, businesses are increasingly turning to PowerApps to develop custom business applications. PowerApps is a powerful tool...
0
better678
by: better678 | last post by:
Question: Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct? Answer: Java is an object-oriented...
0
by: teenabhardwaj | last post by:
How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of...
0
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...
0
by: CD Tom | last post by:
This happens in runtime 2013 and 2016. When a report is run and then closed a toolbar shows up and the only way to get it to go away is to right...
0
by: Naresh1 | last post by:
What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge...
2
by: Matthew3360 | last post by:
Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it...
0
by: AndyPSV | last post by:
HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.