Mercurial > public > think_complexity

annotate ch3ex4.py @ 12:b75bf8bfa2cf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Adding author's Map.py as ch3ex4.py to represent the original version before working on the exercise.
author Brian Neal <bgneal@gmail.com>
date Mon, 10 Dec 2012 19:36:47 -0600
parents
children be7f2cd15faf
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@12 45 def find_map(self, k):
bgneal@12 46 """Finds the right LinearMap for key (k)."""
bgneal@12 47 index = hash(k) % len(self.maps)
bgneal@12 48 return self.maps[index]
bgneal@12 49
bgneal@12 50 def add(self, k, v):
bgneal@12 51 """Adds a new item to the appropriate LinearMap for key (k)."""
bgneal@12 52 m = self.find_map(k)
bgneal@12 53 m.add(k, v)
bgneal@12 54
bgneal@12 55 def get(self, k):
bgneal@12 56 """Finds the right LinearMap for key (k) and looks up (k) in it."""
bgneal@12 57 m = self.find_map(k)
bgneal@12 58 return m.get(k)
bgneal@12 59
bgneal@12 60
bgneal@12 61 class HashMap(object):
bgneal@12 62 """An implementation of a hashtable using a BetterMap
bgneal@12 63 that grows so that the number of items never exceeds the number
bgneal@12 64 of LinearMaps.
bgneal@12 65
bgneal@12 66 The amortized cost of add should be O(1) provided that the
bgneal@12 67 implementation of sum in resize is linear."""
bgneal@12 68
bgneal@12 69 def __init__(self):
bgneal@12 70 """Starts with 2 LinearMaps and 0 items."""
bgneal@12 71 self.maps = BetterMap(2)
bgneal@12 72 self.num = 0
bgneal@12 73
bgneal@12 74 def get(self, k):
bgneal@12 75 """Looks up the key (k) and returns the corresponding value,
bgneal@12 76 or raises KeyError if the key is not found."""
bgneal@12 77 return self.maps.get(k)
bgneal@12 78
bgneal@12 79 def add(self, k, v):
bgneal@12 80 """Resize the map if necessary and adds the new item."""
bgneal@12 81 if self.num == len(self.maps.maps):
bgneal@12 82 self.resize()
bgneal@12 83
bgneal@12 84 self.maps.add(k, v)
bgneal@12 85 self.num += 1
bgneal@12 86
bgneal@12 87 def resize(self):
bgneal@12 88 """Makes a new map, twice as big, and rehashes the items."""
bgneal@12 89 new_maps = BetterMap(self.num * 2)
bgneal@12 90
bgneal@12 91 for m in self.maps.maps:
bgneal@12 92 for k, v in m.items:
bgneal@12 93 new_maps.add(k, v)
bgneal@12 94
bgneal@12 95 self.maps = new_maps
bgneal@12 96
bgneal@12 97
bgneal@12 98 def main(script):
bgneal@12 99 m = HashMap()
bgneal@12 100 s = string.ascii_lowercase
bgneal@12 101
bgneal@12 102 for k, v in enumerate(s):
bgneal@12 103 m.add(k, v)
bgneal@12 104
bgneal@12 105 for k in range(len(s)):
bgneal@12 106 print k, m.get(k)
bgneal@12 107
bgneal@12 108
bgneal@12 109 if __name__ == '__main__':
bgneal@12 110 import sys
bgneal@12 111 main(*sys.argv)