Random Drawing Simulation -- performance issue

[David J. Braden]

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 <count> items 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