Mercurial > public > think_complexity

annotate ch3ex6.py @ 22:84e183b40c63

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