Mercurial > public > think_complexity

annotate ch3ex4.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 bc2c07a059be
children
rev   line source
bgneal@12 1 """ Code example from Complexity and Computation, a book about
bgneal@12 2 exploring complexity science with Python. Available free from
bgneal@12 3
bgneal@12 4 http://greenteapress.com/complexity
bgneal@12 5
bgneal@12 6 Copyright 2011 Allen B. Downey.
bgneal@12 7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
bgneal@12 8 """
bgneal@12 9
bgneal@12 10 import string
bgneal@12 11
bgneal@12 12
bgneal@12 13 class LinearMap(object):
bgneal@12 14 """A simple implementation of a map using a list of tuples
bgneal@12 15 where each tuple is a key-value pair."""
bgneal@12 16
bgneal@12 17 def __init__(self):
bgneal@12 18 self.items = []
bgneal@12 19
bgneal@12 20 def add(self, k, v):
bgneal@12 21 """Adds a new item that maps from key (k) to value (v).
bgneal@12 22 Assumes that they keys are unique."""
bgneal@12 23 self.items.append((k, v))
bgneal@12 24
bgneal@12 25 def get(self, k):
bgneal@12 26 """Looks up the key (k) and returns the corresponding value,
bgneal@12 27 or raises KeyError if the key is not found."""
bgneal@12 28 for key, val in self.items:
bgneal@12 29 if key == k:
bgneal@12 30 return val
bgneal@12 31 raise KeyError
bgneal@12 32
bgneal@12 33
bgneal@12 34 class BetterMap(object):
bgneal@12 35 """A faster implementation of a map using a list of LinearMaps
bgneal@12 36 and the built-in function hash() to determine which LinearMap
bgneal@12 37 to put each key into."""
bgneal@12 38
bgneal@12 39 def __init__(self, n=100):
bgneal@12 40 """Appends (n) LinearMaps onto (self)."""
bgneal@12 41 self.maps = []
bgneal@12 42 for i in range(n):
bgneal@12 43 self.maps.append(LinearMap())
bgneal@12 44
bgneal@13 45 def __len__(self):
bgneal@13 46 """Returns the number of LinearMap buckets in the map."""
bgneal@13 47 return len(self.maps)
bgneal@13 48
bgneal@12 49 def find_map(self, k):
bgneal@12 50 """Finds the right LinearMap for key (k)."""
bgneal@12 51 index = hash(k) % len(self.maps)
bgneal@12 52 return self.maps[index]
bgneal@12 53
bgneal@12 54 def add(self, k, v):
bgneal@12 55 """Adds a new item to the appropriate LinearMap for key (k)."""
bgneal@12 56 m = self.find_map(k)
bgneal@12 57 m.add(k, v)
bgneal@12 58
bgneal@12 59 def get(self, k):
bgneal@12 60 """Finds the right LinearMap for key (k) and looks up (k) in it."""
bgneal@12 61 m = self.find_map(k)
bgneal@12 62 return m.get(k)
bgneal@12 63
bgneal@14 64 def iteritems(self):
bgneal@14 65 """Generator function to yield items in the map."""
bgneal@14 66 for lm in self.maps:
bgneal@14 67 for t in lm.items:
bgneal@14 68 yield t
bgneal@14 69
bgneal@12 70
bgneal@12 71 class HashMap(object):
bgneal@12 72 """An implementation of a hashtable using a BetterMap
bgneal@12 73 that grows so that the number of items never exceeds the number
bgneal@12 74 of LinearMaps.
bgneal@12 75
bgneal@12 76 The amortized cost of add should be O(1) provided that the
bgneal@12 77 implementation of sum in resize is linear."""
bgneal@12 78
bgneal@12 79 def __init__(self):
bgneal@12 80 """Starts with 2 LinearMaps and 0 items."""
bgneal@12 81 self.maps = BetterMap(2)
bgneal@12 82 self.num = 0
bgneal@12 83
bgneal@12 84 def get(self, k):
bgneal@12 85 """Looks up the key (k) and returns the corresponding value,
bgneal@12 86 or raises KeyError if the key is not found."""
bgneal@12 87 return self.maps.get(k)
bgneal@12 88
bgneal@12 89 def add(self, k, v):
bgneal@12 90 """Resize the map if necessary and adds the new item."""
bgneal@13 91 if self.num == len(self.maps):
bgneal@12 92 self.resize()
bgneal@12 93
bgneal@12 94 self.maps.add(k, v)
bgneal@12 95 self.num += 1
bgneal@12 96
bgneal@12 97 def resize(self):
bgneal@12 98 """Makes a new map, twice as big, and rehashes the items."""
bgneal@12 99 new_maps = BetterMap(self.num * 2)
bgneal@12 100
bgneal@14 101 for k, v in self.maps.iteritems():
bgneal@14 102 new_maps.add(k, v)
bgneal@12 103
bgneal@12 104 self.maps = new_maps
bgneal@12 105
bgneal@12 106
bgneal@12 107 def main(script):
bgneal@12 108 m = HashMap()
bgneal@12 109 s = string.ascii_lowercase
bgneal@12 110
bgneal@12 111 for k, v in enumerate(s):
bgneal@12 112 m.add(k, v)
bgneal@12 113
bgneal@12 114 for k in range(len(s)):
bgneal@12 115 print k, m.get(k)
bgneal@12 116
bgneal@12 117
bgneal@12 118 if __name__ == '__main__':
bgneal@12 119 import sys
bgneal@12 120 main(*sys.argv)