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