Mercurial > public > think_complexity

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