Mercurial > public > think_complexity
annotate ch4ex1.py @ 24:5c2c4ce095ef
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 1 of Allen Downey's Think Complexity book. |
| bgneal@22 | 2 |
| bgneal@22 | 3 "Write an implementation of a FIFO using either a doubly-linked list or |
| bgneal@22 | 4 a circular buffer." |
| bgneal@22 | 5 |
| bgneal@22 | 6 """ |
| bgneal@22 | 7 |
| bgneal@22 | 8 class Node(object): |
| bgneal@22 | 9 |
| bgneal@22 | 10 def __init__(self, data): |
| bgneal@22 | 11 self.prev = self.next = None |
| bgneal@22 | 12 self.data = data |
| bgneal@22 | 13 |
| bgneal@22 | 14 class Fifo(object): |
| bgneal@22 | 15 |
| bgneal@22 | 16 def __init__(self): |
| bgneal@22 | 17 self.first = None |
| bgneal@22 | 18 self.last = None |
| bgneal@22 | 19 |
| bgneal@22 | 20 def append(self, val): |
| bgneal@22 | 21 """Append a value onto the back of the queue.""" |
| bgneal@22 | 22 |
| bgneal@22 | 23 node = Node(val) |
| bgneal@22 | 24 |
| bgneal@22 | 25 if self.last: |
| bgneal@22 | 26 self.last.next = node |
| bgneal@22 | 27 node.prev = self.last |
| bgneal@22 | 28 |
| bgneal@22 | 29 self.last = node |
| bgneal@22 | 30 |
| bgneal@22 | 31 if not self.first: |
| bgneal@22 | 32 self.first = node |
| bgneal@22 | 33 |
| bgneal@22 | 34 def pop(self): |
| bgneal@22 | 35 """Remove and return the value at the front of the queue. |
| bgneal@22 | 36 |
| bgneal@22 | 37 Raises an IndexError if the queue is empty. |
| bgneal@22 | 38 """ |
| bgneal@22 | 39 if not self.first: |
| bgneal@22 | 40 raise IndexError |
| bgneal@22 | 41 |
| bgneal@22 | 42 node = self.first |
| bgneal@22 | 43 self.first = node.next |
| bgneal@22 | 44 node.prev = node.next = None |
| bgneal@22 | 45 |
| bgneal@22 | 46 if self.last is node: |
| bgneal@22 | 47 self.last = None |
| bgneal@22 | 48 |
| bgneal@22 | 49 return node.data |
| bgneal@22 | 50 |
| bgneal@22 | 51 def empty(self): |
| bgneal@22 | 52 """Returns True if the queue is empty and False otherwise.""" |
| bgneal@22 | 53 return self.first is None and self.last is None |
| bgneal@22 | 54 |
| bgneal@22 | 55 |
| bgneal@22 | 56 if __name__ == '__main__': |
| bgneal@22 | 57 import random |
| bgneal@22 | 58 values = range(100) |
| bgneal@22 | 59 random.shuffle(values) |
| bgneal@22 | 60 |
| bgneal@22 | 61 fifo = Fifo() |
| bgneal@22 | 62 assert fifo.empty() |
| bgneal@22 | 63 |
| bgneal@22 | 64 for v in values: |
| bgneal@22 | 65 fifo.append(v) |
| bgneal@22 | 66 |
| bgneal@22 | 67 got = [] |
| bgneal@22 | 68 while not fifo.empty(): |
| bgneal@22 | 69 got.append(fifo.pop()) |
| bgneal@22 | 70 |
| bgneal@22 | 71 assert got == values |
| bgneal@22 | 72 |
| bgneal@22 | 73 fifo.append(42) |
| bgneal@22 | 74 assert fifo.pop() == 42 |
| bgneal@22 | 75 assert fifo.empty() |
| bgneal@22 | 76 |
| bgneal@22 | 77 try: |
| bgneal@22 | 78 fifo.pop() |
| bgneal@22 | 79 except IndexError: |
| bgneal@22 | 80 pass |
| bgneal@22 | 81 else: |
| bgneal@22 | 82 assert False |