bgneal@21: """This module contains code from
bgneal@21: Think Python by Allen B. Downey
bgneal@21: http://thinkpython.com
bgneal@21: 
bgneal@21: Copyright 2012 Allen B. Downey
bgneal@21: License: GNU GPLv3 http://www.gnu.org/licenses/gpl.html
bgneal@21: 
bgneal@21: This is 3.6 exercise 6:
bgneal@21: 
bgneal@21: "Test the performance of LinearMap, BetterMap and HashMap; see if you can
bgneal@21: characterize their order of growth.  You can download my map implementations
bgneal@21: from thinkcomplex.com/Map.py, and the code I used in this section from
bgneal@21: thinkcomplex.com/listsum.py.
bgneal@21: 
bgneal@21: You will have to find a range of n that is big enough to show asymptotic
bgneal@21: behavior, but small enough to run quickly."
bgneal@21: 
bgneal@21: """
bgneal@21: import os
bgneal@21: import random
bgneal@21: import timeit
bgneal@21: 
bgneal@21: import matplotlib.pyplot as pyplot
bgneal@21: 
bgneal@21: from ch3ex4 import LinearMap, BetterMap, HashMap
bgneal@21: 
bgneal@21: 
bgneal@21: MAP = None
bgneal@21: VALUES = None
bgneal@21: 
bgneal@21: def test_map():
bgneal@21: 
bgneal@21:     MAP.get(random.choice(VALUES))
bgneal@21: 
bgneal@21: 
bgneal@21: def test_func():
bgneal@21: 
bgneal@21:     elapsed = timeit.timeit('test_map()',
bgneal@21:         setup='from __main__ import test_map', number=100)
bgneal@21:     return elapsed
bgneal@21: 
bgneal@21: 
bgneal@21: def test(map_class):
bgneal@21:     """Tests the given function with a range of values for n.
bgneal@21: 
bgneal@21:     Returns a list of ns and a list of run times.
bgneal@21:     """
bgneal@21:     global MAP, VALUES
bgneal@21: 
bgneal@21:     klass = eval(map_class)
bgneal@21: 
bgneal@21:     d = {'LinearMap': 100000, 'BetterMap': 100000, 'HashMap': 100000}
bgneal@21:     factor = d[map_class]
bgneal@21: 
bgneal@21:     # test (f) over a range of values for (n)
bgneal@21:     ns = []
bgneal@21:     ts = []
bgneal@21:     for i in range(2, 25):
bgneal@21:         n = factor * i
bgneal@21: 
bgneal@21:         MAP = klass()
bgneal@21:         VALUES = range(n)
bgneal@21:         random.shuffle(VALUES)
bgneal@21:         for v in VALUES:
bgneal@21:             MAP.add(v, v)
bgneal@21: 
bgneal@21:         t = test_func()
bgneal@21: 
bgneal@21:         print n, t
bgneal@21:         ns.append(n)
bgneal@21:         ts.append(t)
bgneal@21: 
bgneal@21:     return ns, ts
bgneal@21: 
bgneal@21: 
bgneal@21: def plot(ns, ts, label, color='blue', exp=1.0):
bgneal@21:     """Plots data and a fitted curve.
bgneal@21: 
bgneal@21:     ns: sequence of n (problem size)
bgneal@21:     ts: sequence of t (run time)
bgneal@21:     label: string label for the data curve
bgneal@21:     color: string color for the data curve
bgneal@21:     exp: exponent (slope) for the fitted curve
bgneal@21:     """
bgneal@21:     tfit = fit(ns, ts, exp)
bgneal@21:     pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed')
bgneal@21:     pyplot.plot(ns, ts, label=label, color=color, linewidth=3)
bgneal@21: 
bgneal@21: 
bgneal@21: def fit(ns, ts, exp=1.0, index=-1):
bgneal@21:     """Fits a curve with the given exponent.
bgneal@21: 
bgneal@21:     Use the given index as a reference point, and scale all other
bgneal@21:     points accordingly.
bgneal@21:     """
bgneal@21:     nref = ns[index]
bgneal@21:     tref = ts[index]
bgneal@21: 
bgneal@21:     tfit = []
bgneal@21:     for n in ns:
bgneal@21:         ratio = float(n) / nref
bgneal@21:         t = ratio**exp * tref
bgneal@21:         tfit.append(t)
bgneal@21: 
bgneal@21:     return tfit
bgneal@21: 
bgneal@21: 
bgneal@21: def save(root, exts=['eps', 'pdf']):
bgneal@21:     """Saves the current figure in the given formats.
bgneal@21: 
bgneal@21:     root: string filename root
bgneal@21:     exts: list of string extensions (specifying output formats).
bgneal@21:     """
bgneal@21:     for ext in exts:
bgneal@21:         filename = '%s.%s' % (root, ext)
bgneal@21:         print 'Writing', filename
bgneal@21:         pyplot.savefig(filename)
bgneal@21: 
bgneal@21: 
bgneal@21: def make_fig(funcs, scale='log', exp=1.0, filename=None):
bgneal@21:     pyplot.clf()
bgneal@21:     pyplot.xscale(scale)
bgneal@21:     pyplot.yscale(scale)
bgneal@21:     pyplot.title('')
bgneal@21:     pyplot.xlabel('n')
bgneal@21:     pyplot.ylabel('run time (s)')
bgneal@21: 
bgneal@21:     colors = ['blue', 'orange', 'green']
bgneal@21:     for func, color in zip(funcs, colors):
bgneal@21:         data = test(func)
bgneal@21:         plot(*data, label=func, color=color, exp=exp)
bgneal@21: 
bgneal@21:     pyplot.legend(loc=4)
bgneal@21: 
bgneal@21:     if filename:
bgneal@21:         save(filename)
bgneal@21:     else:
bgneal@21:         pyplot.show()
bgneal@21: 
bgneal@21: 
bgneal@21: def main(script):
bgneal@21:     make_fig(['LinearMap', 'BetterMap', 'HashMap'], scale='log', exp=1.0)
bgneal@21: 
bgneal@21: 
bgneal@21: if __name__ == '__main__':
bgneal@21:     import sys
bgneal@21:     main(*sys.argv)
bgneal@21: