Mercurial > public > think_complexity

annotate ch4ex2.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
children
rev   line source
bgneal@22 1 """Section 4.2, exercise 2.
bgneal@22 2
bgneal@22 3 "The following implementation of a BFS contains two performance errors. What are
bgneal@22 4 they? What is the actual order of growth for this algorithm?
bgneal@22 5
bgneal@22 6 def bfs(top_node, visit):
bgneal@22 7 'Breadth-first search on a graph, starting at top_node.'
bgneal@22 8 visited = set()
bgneal@22 9 queue = [top_node]
bgneal@22 10 while len(queue):
bgneal@22 11 curr_node = queue.pop(0) # Dequeue
bgneal@22 12 visit(curr_node) # Visit the node
bgneal@22 13 visited.add(curr_node)
bgneal@22 14
bgneal@22 15 # Enqueue non-visited and non-enqueued children
bgneal@22 16 queue.extend(c for c in curr_node.children
bgneal@22 17 if c not in visited and c not in queue)
bgneal@22 18
bgneal@22 19 Test this code with a range of graph sizes and check your analysis. Then use
bgneal@22 20 a FIFO implementation to fix the errors and confirm that your algorithm is
bgneal@22 21 linear."
bgneal@22 22
bgneal@22 23 ----
bgneal@22 24
bgneal@22 25 I think the 2 performance errors are:
bgneal@22 26 1) Using a list as the queue, and popping element 0.
bgneal@22 27 2) Doing a linear search to see if the child node is already in the queue.
bgneal@22 28
bgneal@22 29 To characterize this bfs, I'll inherit from my Graph class and add
bgneal@22 30 a flawed_bfs() method which implements the above. I'll then plot both the
bgneal@22 31 flawed_bfs and the bfs method I wrote earlier.
bgneal@22 32
bgneal@22 33 This program tests complete graphs. The flawed_bfs is plotted along with a curve
bgneal@22 34 of slope 3, which fits well, and shows that this search is O(|V|^3). Next, the bfs
bgneal@22 35 method is plotted with a curve of slope 2, which fits well. This shows that bfs
bgneal@22 36 is quadratic, or O(|V|^2), on a complete graph, which is what we expect.
bgneal@22 37
bgneal@22 38 """
bgneal@22 39 import timeit
bgneal@22 40 import matplotlib.pyplot as pyplot
bgneal@22 41
bgneal@22 42 from Graph import Graph, Vertex
bgneal@22 43
bgneal@22 44
bgneal@22 45 class FlawedGraph(Graph):
bgneal@22 46
bgneal@22 47 def flawed_bfs(self, start, visit=None):
bgneal@22 48 """A breadth-first search with performance problems."""
bgneal@22 49 visited = set()
bgneal@22 50 queue = [start]
bgneal@22 51 while len(queue):
bgneal@22 52 curr_node = queue.pop(0)
bgneal@22 53 if visit:
bgneal@22 54 visit(curr_node)
bgneal@22 55 visited.add(curr_node)
bgneal@22 56
bgneal@22 57 queue.extend(c for c in self.out_vertices(curr_node)
bgneal@22 58 if c not in visited and c not in queue)
bgneal@22 59
bgneal@22 60 GRAPH = None
bgneal@22 61 METHOD = None
bgneal@22 62 V = None
bgneal@22 63
bgneal@22 64
bgneal@22 65 def test_graph_search():
bgneal@22 66
bgneal@22 67 if METHOD == 'flawed_bfs':
bgneal@22 68 GRAPH.flawed_bfs(V)
bgneal@22 69 else:
bgneal@22 70 GRAPH.bfs(V)
bgneal@22 71
bgneal@22 72
bgneal@22 73 def test_func():
bgneal@22 74
bgneal@22 75 elapsed = timeit.timeit('test_graph_search()',
bgneal@22 76 setup='from __main__ import test_graph_search', number=1)
bgneal@22 77 return elapsed
bgneal@22 78
bgneal@22 79
bgneal@22 80 def test(method):
bgneal@22 81 """Tests the given function with a range of values for n.
bgneal@22 82
bgneal@22 83 Returns a list of ns and a list of run times.
bgneal@22 84 """
bgneal@22 85 global GRAPH, METHOD, V
bgneal@22 86
bgneal@22 87 METHOD = method
bgneal@22 88 factor = 10
bgneal@22 89
bgneal@22 90 # test (f) over a range of values for (n)
bgneal@22 91 ns = []
bgneal@22 92 ts = []
bgneal@22 93 for i in range(10, 50):
bgneal@22 94 n = factor * i
bgneal@22 95
bgneal@22 96 GRAPH = FlawedGraph()
bgneal@22 97 V = None
bgneal@22 98 # Add n vertices and connect them
bgneal@22 99 for i in range(n):
bgneal@22 100 v = Vertex()
bgneal@22 101 if not V:
bgneal@22 102 V = v
bgneal@22 103 GRAPH.add_vertex(v)
bgneal@22 104
bgneal@22 105 GRAPH.add_all_edges() # make g a complete graph
bgneal@22 106
bgneal@22 107 t = test_func()
bgneal@22 108
bgneal@22 109 print n, t
bgneal@22 110 ns.append(n)
bgneal@22 111 ts.append(t)
bgneal@22 112
bgneal@22 113 return ns, ts
bgneal@22 114
bgneal@22 115
bgneal@22 116 def plot(ns, ts, label, color='blue', exp=1.0):
bgneal@22 117 """Plots data and a fitted curve.
bgneal@22 118
bgneal@22 119 ns: sequence of n (problem size)
bgneal@22 120 ts: sequence of t (run time)
bgneal@22 121 label: string label for the data curve
bgneal@22 122 color: string color for the data curve
bgneal@22 123 exp: exponent (slope) for the fitted curve
bgneal@22 124 """
bgneal@22 125 tfit = fit(ns, ts, exp)
bgneal@22 126 pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed')
bgneal@22 127 pyplot.plot(ns, ts, label=label, color=color, linewidth=3)
bgneal@22 128
bgneal@22 129
bgneal@22 130 def fit(ns, ts, exp=1.0, index=-1):
bgneal@22 131 """Fits a curve with the given exponent.
bgneal@22 132
bgneal@22 133 Use the given index as a reference point, and scale all other
bgneal@22 134 points accordingly.
bgneal@22 135 """
bgneal@22 136 nref = ns[index]
bgneal@22 137 tref = ts[index]
bgneal@22 138
bgneal@22 139 tfit = []
bgneal@22 140 for n in ns:
bgneal@22 141 ratio = float(n) / nref
bgneal@22 142 t = ratio**exp * tref
bgneal@22 143 tfit.append(t)
bgneal@22 144
bgneal@22 145 return tfit
bgneal@22 146
bgneal@22 147
bgneal@22 148 def make_fig(funcs):
bgneal@22 149 pyplot.clf()
bgneal@22 150 pyplot.xscale('log')
bgneal@22 151 pyplot.yscale('log')
bgneal@22 152 pyplot.title('')
bgneal@22 153 pyplot.xlabel('n')
bgneal@22 154 pyplot.ylabel('run time (s)')
bgneal@22 155
bgneal@22 156 colors = ['red', 'green']
bgneal@22 157
bgneal@22 158 for func, color in zip(funcs, colors):
bgneal@22 159 data = test(func)
bgneal@22 160 exp = 3.0 if func == 'flawed_bfs' else 2.0
bgneal@22 161 plot(*data, label=func, color=color, exp=exp)
bgneal@22 162
bgneal@22 163 pyplot.legend(loc=4)
bgneal@22 164
bgneal@22 165 pyplot.show()
bgneal@22 166
bgneal@22 167
bgneal@22 168 def main(script):
bgneal@22 169 make_fig(['flawed_bfs', 'bfs'])
bgneal@22 170
bgneal@22 171
bgneal@22 172 if __name__ == '__main__':
bgneal@22 173 import sys
bgneal@22 174 main(*sys.argv)