Mercurial > public > think_complexity

annotate 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
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 os
bgneal@21 20 import random
bgneal@21 21 import timeit
bgneal@21 22
bgneal@21 23 import matplotlib.pyplot as pyplot
bgneal@21 24
bgneal@21 25 from ch3ex4 import LinearMap, BetterMap, HashMap
bgneal@21 26
bgneal@21 27
bgneal@21 28 MAP = None
bgneal@21 29 VALUES = None
bgneal@21 30
bgneal@21 31 def test_map():
bgneal@21 32
bgneal@21 33 MAP.get(random.choice(VALUES))
bgneal@21 34
bgneal@21 35
bgneal@21 36 def test_func():
bgneal@21 37
bgneal@21 38 elapsed = timeit.timeit('test_map()',
bgneal@21 39 setup='from __main__ import test_map', number=100)
bgneal@21 40 return elapsed
bgneal@21 41
bgneal@21 42
bgneal@21 43 def test(map_class):
bgneal@21 44 """Tests the given function with a range of values for n.
bgneal@21 45
bgneal@21 46 Returns a list of ns and a list of run times.
bgneal@21 47 """
bgneal@21 48 global MAP, VALUES
bgneal@21 49
bgneal@21 50 klass = eval(map_class)
bgneal@21 51
bgneal@21 52 d = {'LinearMap': 100000, 'BetterMap': 100000, 'HashMap': 100000}
bgneal@21 53 factor = d[map_class]
bgneal@21 54
bgneal@21 55 # test (f) over a range of values for (n)
bgneal@21 56 ns = []
bgneal@21 57 ts = []
bgneal@21 58 for i in range(2, 25):
bgneal@21 59 n = factor * i
bgneal@21 60
bgneal@21 61 MAP = klass()
bgneal@21 62 VALUES = range(n)
bgneal@21 63 random.shuffle(VALUES)
bgneal@21 64 for v in VALUES:
bgneal@21 65 MAP.add(v, v)
bgneal@21 66
bgneal@21 67 t = test_func()
bgneal@21 68
bgneal@21 69 print n, t
bgneal@21 70 ns.append(n)
bgneal@21 71 ts.append(t)
bgneal@21 72
bgneal@21 73 return ns, ts
bgneal@21 74
bgneal@21 75
bgneal@21 76 def plot(ns, ts, label, color='blue', exp=1.0):
bgneal@21 77 """Plots data and a fitted curve.
bgneal@21 78
bgneal@21 79 ns: sequence of n (problem size)
bgneal@21 80 ts: sequence of t (run time)
bgneal@21 81 label: string label for the data curve
bgneal@21 82 color: string color for the data curve
bgneal@21 83 exp: exponent (slope) for the fitted curve
bgneal@21 84 """
bgneal@21 85 tfit = fit(ns, ts, exp)
bgneal@21 86 pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed')
bgneal@21 87 pyplot.plot(ns, ts, label=label, color=color, linewidth=3)
bgneal@21 88
bgneal@21 89
bgneal@21 90 def fit(ns, ts, exp=1.0, index=-1):
bgneal@21 91 """Fits a curve with the given exponent.
bgneal@21 92
bgneal@21 93 Use the given index as a reference point, and scale all other
bgneal@21 94 points accordingly.
bgneal@21 95 """
bgneal@21 96 nref = ns[index]
bgneal@21 97 tref = ts[index]
bgneal@21 98
bgneal@21 99 tfit = []
bgneal@21 100 for n in ns:
bgneal@21 101 ratio = float(n) / nref
bgneal@21 102 t = ratio**exp * tref
bgneal@21 103 tfit.append(t)
bgneal@21 104
bgneal@21 105 return tfit
bgneal@21 106
bgneal@21 107
bgneal@21 108 def save(root, exts=['eps', 'pdf']):
bgneal@21 109 """Saves the current figure in the given formats.
bgneal@21 110
bgneal@21 111 root: string filename root
bgneal@21 112 exts: list of string extensions (specifying output formats).
bgneal@21 113 """
bgneal@21 114 for ext in exts:
bgneal@21 115 filename = '%s.%s' % (root, ext)
bgneal@21 116 print 'Writing', filename
bgneal@21 117 pyplot.savefig(filename)
bgneal@21 118
bgneal@21 119
bgneal@21 120 def make_fig(funcs, scale='log', exp=1.0, filename=None):
bgneal@21 121 pyplot.clf()
bgneal@21 122 pyplot.xscale(scale)
bgneal@21 123 pyplot.yscale(scale)
bgneal@21 124 pyplot.title('')
bgneal@21 125 pyplot.xlabel('n')
bgneal@21 126 pyplot.ylabel('run time (s)')
bgneal@21 127
bgneal@21 128 colors = ['blue', 'orange', 'green']
bgneal@21 129 for func, color in zip(funcs, colors):
bgneal@21 130 data = test(func)
bgneal@21 131 plot(*data, label=func, color=color, exp=exp)
bgneal@21 132
bgneal@21 133 pyplot.legend(loc=4)
bgneal@21 134
bgneal@21 135 if filename:
bgneal@21 136 save(filename)
bgneal@21 137 else:
bgneal@21 138 pyplot.show()
bgneal@21 139
bgneal@21 140
bgneal@21 141 def main(script):
bgneal@21 142 make_fig(['LinearMap', 'BetterMap', 'HashMap'], scale='log', exp=1.0)
bgneal@21 143
bgneal@21 144
bgneal@21 145 if __name__ == '__main__':
bgneal@21 146 import sys
bgneal@21 147 main(*sys.argv)
bgneal@21 148