# Coupon collector

This is a coupon collector code to analyze the running time. I need some suggestions on improving the running times of this code. I have used the data structure dictionary, but is there any other data structure that will perform faster?

import random
import numpy as np
import matplotlib.pyplot as plt
from array import *
import timeit

trailList = {}

def couponcollector(n):
numDic = {}
trails = 0
while len(numDic) < n:
num = np.random.random_integers(n);
trails = trails + 1
if num not in numDic.keys():
numDic[num] = 1

return trails

def starter(n,m):
summ = 0
for i in range(0,m):
r = couponcollector(n)
summ = summ + r
if trailList.has_key(r):
trailList[r] = trailList[r] + 1
else:
trailList[r] = 1
print trailList
#print "Expected Trails"
#print summ/300

nvalues= []
runtimes = []
runtimes1 = []
runtimes2 = []
runtimes3 = []
runtimes4 = []
#color = {300: 'blue', 1000: 'green', 5000: 'red', 10000: 'black'}
def runtimer():
for n in range(300,20000,4000):
nvalues.append(n)
#stmt = 'starter(' + str(n)+','+str(300) + ')'
#stmt1 = 'starter(' + str(n)+','+str(800) + ')'
stmt2 = 'starter(' + str(n)+','+str(1000) + ')'
stmt3 = 'starter(' + str(n)+','+str(3000) + ')'
stmt4= 'starter(' + str(n)+','+str(5000) + ')'
print(nvalues)
#runtimes.append(timeit.timeit(stmt, setup="from __main__ import starter", number = 1))
#runtimes1.append(timeit.timeit(stmt1, setup="from __main__ import starter", number = 1))
runtimes2.append(timeit.timeit(stmt2, setup="from __main__ import starter", number = 1))
print runtimes2
runtimes3.append(timeit.timeit(stmt3, setup="from __main__ import starter", number = 1))
runtimes4.append(timeit.timeit(stmt4, setup="from __main__ import starter", number = 1))

fig = plt.figure()
#plt.plot(nvalues, runtimes, c='blue', label='m = 300')
#plt.plot(nvalues, runtimes1, c='green', label='m = 800')
plt.plot(nvalues, runtimes2, c='red', label='m = 1000')
plt.plot(nvalues, runtimes3, c='blue', label='m = 3000')
plt.plot(nvalues, runtimes4, c='green', label='m = 5000')
plt.ylabel('Runtimes')
plt.xlabel('Coupon Collector Domain Size')
plt.title('Plot of Coupon Collector runtimes')
plt.legend(loc='upper left')
plt.grid(True)
fig.savefig('ccFinal.png')
runtimer()


I have used the data structure dictionary, but is there any other data structure that will perform faster?

As far as numDict is concerned, you don't really need a data structure at all.

After $k$ coupons have been collected, the probability of drawing a new coupon is $\frac{n-k}{n}$ per trial. The number of trials required to get the next coupon follows the geometric distribution. Instead of simulating all those trials by drawing random numbers from the uniform distribution, you can draw just one random number from the geometric distribution. The couponcollector function can become

def couponcollector(n):
return sum(np.random.geometric(float(n-k)/n) for k in xrange(n))


I took some timings of couponcollector(2000):

• Original version 888 ms
• After deleting .keys() from if num not in numDic.keys(): 19.4 ms
• My version 1.98 ms

Further improvements would be possible by vectorizing the computation in NumPy.

Typically, dictionaries are "blazingly fast" with common operations performed in O(1) time. This suggests that perhaps the semantics are the problem.

## Code Analysis

Looking at couponcollector()

1. if num not in numDic.keys(): may also not take advantage of dictionary semantics. In Python 2.x according to this StackOverflow answer calls to dict.keys returns a list. This call is made n times and the average length of the list would be n/2. This is also 0(n^2) time complexity.

2. while len(numDic) < n is a good place to start. A dictionary may not be optimized around returning its size. In Python, fortunately dict.len() runs in 0(1). However, because dict is a mutable data structure there is no general way to locally predict the value of the next call to dict.len() based on the current value. Modern compilers and CPU's have optimizations such as predictive branching, parallel execution pipelines, etc. These are tuned for iterative looping. There is likely to be an execution difference between while i < n ... i += 1 and the call to while dict.len() < n.

Looking at starter():

for i in range(0,m):
r = couponcollector(n)


means that for n = 300 and m = 1000 there could be in the ballpark of 90,000,000 operations and at n = 20,000 m=5000 around 2 trillion operations. Even with optimized compiled code that many operations can take noticeable time.

## Possible Alternatives

In the while loop:

• use dict.get() instead of looking at dict.keys() if using Python 2.x.

• use simpler iteration rather than measuring the size of the dictionary with dict.len(). This may also allow for optimizations by the Python engine and even lower down at the CPU level.

This is not the right way to check if an element is in a dictionary:

if num not in numDic.keys():
pass


This is the right and natural way:

if num not in numDic:
pass


As @benrudgers said, in Python 2 the .keys method returns a list, which makes your script significantly slower than it needs to be.

Instead of incrementing variables like this:

trailList[r] = trailList[r] + 1


Use the augmented assignment operator += instead:

trailList[r] += 1


In addition to what has been mentioned, replace

if trailList.has_key(r):


with

if r in trailList


and

trails = trails + 1


with

trails += 1


Further, consider using a set for numDic with pre-initialization of n elements:

def couponcollector(n):
numDic = set(np.random.random_integers(0, n, n).tolist())
trails = n

while len(numDic) < n:
trails += 1

return trails


Replace

for i in range(0,m):


with

for _ in range(m):


Make trailList a Counter to simplify the main loop, and make it local to the function (perhaps as a parameter).

def starter(n,m):
trailList = Counter()
summ = 0
for _ in range(m):
r = couponcollector(n)
summ += r
trailList[r] += 1
return trailList