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 -- http://mail.python.org/mailman/listinfo/python-list