Mercurial > public > think_complexity

annotate ch3ex6.py @ 24:5c2c4ce095ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A stab at the L(p)/L(0) plot. I still don't quite get how the graphs in the Watts and Strogatz paper were generated. My results have basically the same shape, but don't converge to 0. I'm not sure how this is possible if the rewire function does not remove edges.
author Brian Neal <bgneal@gmail.com>
date Thu, 03 Jan 2013 18:41:13 -0600
parents 84e183b40c63
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