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 randomimport numpy as npimport matplotlib.pyplot as plt from array import *import timeittrailList = {}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 trailsdef 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/300nvalues= []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()
Coupon collector
python;optimization;performance
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 becomedef 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 msAfter deleting .keys() from if num not in numDic.keys():  19.4 msMy version 1.98 msFurther improvements would be possible by vectorizing the computation in NumPy.