FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
ThinkRubyBuild/code/Map.py at master · learnbyexample/ThinkRubyBuild · GitHub
learnbyexample
/
ThinkRubyBuild
Public
Notifications
You must be signed in to change notification settings
Fork
2
Star
32
Code
Issues
7
Pull requests
0
Actions
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Security and quality
Insights
Expand file tree
Breadcrumbs
ThinkRubyBuild
/
code
/
Map.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
114 lines (82 loc) · 2.89 KB
Breadcrumbs
ThinkRubyBuild
/
code
/
Map.py
Copy path
File metadata and controls
114 lines (82 loc) · 2.89 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
"""This module contains a code example related to
Think Python, 2nd Edition
by Allen Downey
http://thinkpython2.com
Copyright 2015 Allen Downey
License: http://creativecommons.org/licenses/by/4.0/
"""
from
__future__
import
print_function
,
division
class
LinearMap
:
"""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
class
BetterMap
:
"""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
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
:
"""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
.
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_map
=
BetterMap
(
self
.
num
*
2
)
for
m
in
self
.
maps
.
maps
:
for
k
,
v
in
m
.
items
:
new_map
.
add
(
k
,
v
)
self
.
maps
=
new_map
def
main
():
import
string
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__'
:
main
()
Back
|
FazBrowse Home
|
New Git URL