Mercurial > public > think_complexity

comparison ch3ex6.py @ 21:55880b29b4d4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
3.6 exercise 6: characterize LinearMap, BetterMap, and HashMap using pyplot.
author Brian Neal <bgneal@gmail.com>
date Sat, 29 Dec 2012 22:16:11 -0600
parents
children 84e183b40c63
comparison
equal deleted inserted replaced
20:0326803882ad 21:55880b29b4d4
1 """This module contains code from
2 Think Python by Allen B. Downey
3 http://thinkpython.com
4
5 Copyright 2012 Allen B. Downey
6 License: GNU GPLv3 http://www.gnu.org/licenses/gpl.html
7
8 This is 3.6 exercise 6:
9
10 "Test the performance of LinearMap, BetterMap and HashMap; see if you can
11 characterize their order of growth. You can download my map implementations
12 from thinkcomplex.com/Map.py, and the code I used in this section from
13 thinkcomplex.com/listsum.py.
14
15 You will have to find a range of n that is big enough to show asymptotic
16 behavior, but small enough to run quickly."
17
18 """
19 import os
20 import random
21 import timeit
22
23 import matplotlib.pyplot as pyplot
24
25 from ch3ex4 import LinearMap, BetterMap, HashMap
26
27
28 MAP = None
29 VALUES = None
30
31 def test_map():
32
33 MAP.get(random.choice(VALUES))
34
35
36 def test_func():
37
38 elapsed = timeit.timeit('test_map()',
39 setup='from __main__ import test_map', number=100)
40 return elapsed
41
42
43 def test(map_class):
44 """Tests the given function with a range of values for n.
45
46 Returns a list of ns and a list of run times.
47 """
48 global MAP, VALUES
49
50 klass = eval(map_class)
51
52 d = {'LinearMap': 100000, 'BetterMap': 100000, 'HashMap': 100000}
53 factor = d[map_class]
54
55 # test (f) over a range of values for (n)
56 ns = []
57 ts = []
58 for i in range(2, 25):
59 n = factor * i
60
61 MAP = klass()
62 VALUES = range(n)
63 random.shuffle(VALUES)
64 for v in VALUES:
65 MAP.add(v, v)
66
67 t = test_func()
68
69 print n, t
70 ns.append(n)
71 ts.append(t)
72
73 return ns, ts
74
75
76 def plot(ns, ts, label, color='blue', exp=1.0):
77 """Plots data and a fitted curve.
78
79 ns: sequence of n (problem size)
80 ts: sequence of t (run time)
81 label: string label for the data curve
82 color: string color for the data curve
83 exp: exponent (slope) for the fitted curve
84 """
85 tfit = fit(ns, ts, exp)
86 pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed')
87 pyplot.plot(ns, ts, label=label, color=color, linewidth=3)
88
89
90 def fit(ns, ts, exp=1.0, index=-1):
91 """Fits a curve with the given exponent.
92
93 Use the given index as a reference point, and scale all other
94 points accordingly.
95 """
96 nref = ns[index]
97 tref = ts[index]
98
99 tfit = []
100 for n in ns:
101 ratio = float(n) / nref
102 t = ratio**exp * tref
103 tfit.append(t)
104
105 return tfit
106
107
108 def save(root, exts=['eps', 'pdf']):
109 """Saves the current figure in the given formats.
110
111 root: string filename root
112 exts: list of string extensions (specifying output formats).
113 """
114 for ext in exts:
115 filename = '%s.%s' % (root, ext)
116 print 'Writing', filename
117 pyplot.savefig(filename)
118
119
120 def make_fig(funcs, scale='log', exp=1.0, filename=None):
121 pyplot.clf()
122 pyplot.xscale(scale)
123 pyplot.yscale(scale)
124 pyplot.title('')
125 pyplot.xlabel('n')
126 pyplot.ylabel('run time (s)')
127
128 colors = ['blue', 'orange', 'green']
129 for func, color in zip(funcs, colors):
130 data = test(func)
131 plot(*data, label=func, color=color, exp=exp)
132
133 pyplot.legend(loc=4)
134
135 if filename:
136 save(filename)
137 else:
138 pyplot.show()
139
140
141 def main(script):
142 make_fig(['LinearMap', 'BetterMap', 'HashMap'], scale='log', exp=1.0)
143
144
145 if __name__ == '__main__':
146 import sys
147 main(*sys.argv)
148