# HG changeset patch # User Brian Neal # Date 1357001901 21600 # Node ID 84e183b40c63b8db87fe14f34c3d26c28dfb2a27 # Parent 55880b29b4d4e01602aa4bae6db9fc7ce5be943e Added exercises 1 and 2 from chapter 4. diff -r 55880b29b4d4 -r 84e183b40c63 Graph.py --- a/Graph.py Sat Dec 29 22:16:11 2012 -0600 +++ b/Graph.py Mon Dec 31 18:58:21 2012 -0600 @@ -219,7 +219,7 @@ visit_func(v) # Add the adjacent neigbors to the node to the queue - queue.extend(self.out_vertices(v)) + queue.extend(c for c in self.out_vertices(v) if c not in visited) return visited diff -r 55880b29b4d4 -r 84e183b40c63 ch3ex6.py --- a/ch3ex6.py Sat Dec 29 22:16:11 2012 -0600 +++ b/ch3ex6.py Mon Dec 31 18:58:21 2012 -0600 @@ -16,7 +16,6 @@ behavior, but small enough to run quickly." """ -import os import random import timeit diff -r 55880b29b4d4 -r 84e183b40c63 ch4ex1.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ch4ex1.py Mon Dec 31 18:58:21 2012 -0600 @@ -0,0 +1,82 @@ +"""Section 4.2, exercise 1 of Allen Downey's Think Complexity book. + +"Write an implementation of a FIFO using either a doubly-linked list or +a circular buffer." + +""" + +class Node(object): + + def __init__(self, data): + self.prev = self.next = None + self.data = data + +class Fifo(object): + + def __init__(self): + self.first = None + self.last = None + + def append(self, val): + """Append a value onto the back of the queue.""" + + node = Node(val) + + if self.last: + self.last.next = node + node.prev = self.last + + self.last = node + + if not self.first: + self.first = node + + def pop(self): + """Remove and return the value at the front of the queue. + + Raises an IndexError if the queue is empty. + """ + if not self.first: + raise IndexError + + node = self.first + self.first = node.next + node.prev = node.next = None + + if self.last is node: + self.last = None + + return node.data + + def empty(self): + """Returns True if the queue is empty and False otherwise.""" + return self.first is None and self.last is None + + +if __name__ == '__main__': + import random + values = range(100) + random.shuffle(values) + + fifo = Fifo() + assert fifo.empty() + + for v in values: + fifo.append(v) + + got = [] + while not fifo.empty(): + got.append(fifo.pop()) + + assert got == values + + fifo.append(42) + assert fifo.pop() == 42 + assert fifo.empty() + + try: + fifo.pop() + except IndexError: + pass + else: + assert False diff -r 55880b29b4d4 -r 84e183b40c63 ch4ex2.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ch4ex2.py Mon Dec 31 18:58:21 2012 -0600 @@ -0,0 +1,174 @@ +"""Section 4.2, exercise 2. + +"The following implementation of a BFS contains two performance errors. What are +they? What is the actual order of growth for this algorithm? + +def bfs(top_node, visit): + 'Breadth-first search on a graph, starting at top_node.' + visited = set() + queue = [top_node] + while len(queue): + curr_node = queue.pop(0) # Dequeue + visit(curr_node) # Visit the node + visited.add(curr_node) + + # Enqueue non-visited and non-enqueued children + queue.extend(c for c in curr_node.children + if c not in visited and c not in queue) + +Test this code with a range of graph sizes and check your analysis. Then use +a FIFO implementation to fix the errors and confirm that your algorithm is +linear." + +---- + +I think the 2 performance errors are: + 1) Using a list as the queue, and popping element 0. + 2) Doing a linear search to see if the child node is already in the queue. + +To characterize this bfs, I'll inherit from my Graph class and add +a flawed_bfs() method which implements the above. I'll then plot both the +flawed_bfs and the bfs method I wrote earlier. + +This program tests complete graphs. The flawed_bfs is plotted along with a curve +of slope 3, which fits well, and shows that this search is O(|V|^3). Next, the bfs +method is plotted with a curve of slope 2, which fits well. This shows that bfs +is quadratic, or O(|V|^2), on a complete graph, which is what we expect. + +""" +import timeit +import matplotlib.pyplot as pyplot + +from Graph import Graph, Vertex + + +class FlawedGraph(Graph): + + def flawed_bfs(self, start, visit=None): + """A breadth-first search with performance problems.""" + visited = set() + queue = [start] + while len(queue): + curr_node = queue.pop(0) + if visit: + visit(curr_node) + visited.add(curr_node) + + queue.extend(c for c in self.out_vertices(curr_node) + if c not in visited and c not in queue) + +GRAPH = None +METHOD = None +V = None + + +def test_graph_search(): + + if METHOD == 'flawed_bfs': + GRAPH.flawed_bfs(V) + else: + GRAPH.bfs(V) + + +def test_func(): + + elapsed = timeit.timeit('test_graph_search()', + setup='from __main__ import test_graph_search', number=1) + return elapsed + + +def test(method): + """Tests the given function with a range of values for n. + + Returns a list of ns and a list of run times. + """ + global GRAPH, METHOD, V + + METHOD = method + factor = 10 + + # test (f) over a range of values for (n) + ns = [] + ts = [] + for i in range(10, 50): + n = factor * i + + GRAPH = FlawedGraph() + V = None + # Add n vertices and connect them + for i in range(n): + v = Vertex() + if not V: + V = v + GRAPH.add_vertex(v) + + GRAPH.add_all_edges() # make g a complete graph + + t = test_func() + + print n, t + ns.append(n) + ts.append(t) + + return ns, ts + + +def plot(ns, ts, label, color='blue', exp=1.0): + """Plots data and a fitted curve. + + ns: sequence of n (problem size) + ts: sequence of t (run time) + label: string label for the data curve + color: string color for the data curve + exp: exponent (slope) for the fitted curve + """ + tfit = fit(ns, ts, exp) + pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed') + pyplot.plot(ns, ts, label=label, color=color, linewidth=3) + + +def fit(ns, ts, exp=1.0, index=-1): + """Fits a curve with the given exponent. + + Use the given index as a reference point, and scale all other + points accordingly. + """ + nref = ns[index] + tref = ts[index] + + tfit = [] + for n in ns: + ratio = float(n) / nref + t = ratio**exp * tref + tfit.append(t) + + return tfit + + +def make_fig(funcs): + pyplot.clf() + pyplot.xscale('log') + pyplot.yscale('log') + pyplot.title('') + pyplot.xlabel('n') + pyplot.ylabel('run time (s)') + + colors = ['red', 'green'] + + for func, color in zip(funcs, colors): + data = test(func) + exp = 3.0 if func == 'flawed_bfs' else 2.0 + plot(*data, label=func, color=color, exp=exp) + + pyplot.legend(loc=4) + + pyplot.show() + + +def main(script): + make_fig(['flawed_bfs', 'bfs']) + + +if __name__ == '__main__': + import sys + main(*sys.argv)