Mercurial > public > think_complexity

annotate ch3ex4.py @ 13:be7f2cd15faf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Completing Ch 3.4 exercise 4.1.
author Brian Neal <bgneal@gmail.com>
date Mon, 10 Dec 2012 19:42:38 -0600
parents b75bf8bfa2cf
children bc2c07a059be
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@12 64
bgneal@12 65 class HashMap(object):
bgneal@12 66 """An implementation of a hashtable using a BetterMap
bgneal@12 67 that grows so that the number of items never exceeds the number
bgneal@12 68 of LinearMaps.
bgneal@12 69
bgneal@12 70 The amortized cost of add should be O(1) provided that the
bgneal@12 71 implementation of sum in resize is linear."""
bgneal@12 72
bgneal@12 73 def __init__(self):
bgneal@12 74 """Starts with 2 LinearMaps and 0 items."""
bgneal@12 75 self.maps = BetterMap(2)
bgneal@12 76 self.num = 0
bgneal@12 77
bgneal@12 78 def get(self, k):
bgneal@12 79 """Looks up the key (k) and returns the corresponding value,
bgneal@12 80 or raises KeyError if the key is not found."""
bgneal@12 81 return self.maps.get(k)
bgneal@12 82
bgneal@12 83 def add(self, k, v):
bgneal@12 84 """Resize the map if necessary and adds the new item."""
bgneal@13 85 if self.num == len(self.maps):
bgneal@12 86 self.resize()
bgneal@12 87
bgneal@12 88 self.maps.add(k, v)
bgneal@12 89 self.num += 1
bgneal@12 90
bgneal@12 91 def resize(self):
bgneal@12 92 """Makes a new map, twice as big, and rehashes the items."""
bgneal@12 93 new_maps = BetterMap(self.num * 2)
bgneal@12 94
bgneal@12 95 for m in self.maps.maps:
bgneal@12 96 for k, v in m.items:
bgneal@12 97 new_maps.add(k, v)
bgneal@12 98
bgneal@12 99 self.maps = new_maps
bgneal@12 100
bgneal@12 101
bgneal@12 102 def main(script):
bgneal@12 103 m = HashMap()
bgneal@12 104 s = string.ascii_lowercase
bgneal@12 105
bgneal@12 106 for k, v in enumerate(s):
bgneal@12 107 m.add(k, v)
bgneal@12 108
bgneal@12 109 for k in range(len(s)):
bgneal@12 110 print k, m.get(k)
bgneal@12 111
bgneal@12 112
bgneal@12 113 if __name__ == '__main__':
bgneal@12 114 import sys
bgneal@12 115 main(*sys.argv)