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