Mercurial > public > think_complexity

annotate ch4ex2.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@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)