Mercurial > public > think_complexity

annotate ch3ex4.py @ 14:bc2c07a059be

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Completing Ch 3.3, exercise 4.2.
author Brian Neal <bgneal@gmail.com>
date Mon, 10 Dec 2012 19:58:03 -0600
parents be7f2cd15faf
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)