forked from HuichuanLI/play-with-data-structure-python
-
Notifications
You must be signed in to change notification settings - Fork 1
/
LinkedListMap.py
91 lines (73 loc) · 2.43 KB
/
LinkedListMap.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
from base import MapBase
class LinkedListMap(MapBase):
class _Node:
def __init__(self, key=None, value=None, node_next=None):
self.key = key
self.value = value
self.next = node_next
def __str__(self):
return "Key: {}, Value: {}".format(str(self.key), str(self.value))
def __repr__(self):
return self.__str__()
def __init__(self):
self._dummy_head = self._Node()
self._size = 0
def get_size(self):
return self._size
def is_empty(self):
return self.get_size() == 0
def get_node(self, key):
curr = self._dummy_head.next
while curr:
if curr.key == key:
return curr
curr = curr.next
return None
def contains(self, key):
return self.get_node(key) is not None
def getter(self, key):
node = self.get_node(key)
return node.value if node is not None else None
def add(self, key, value):
node = self.get_node(key)
if not node:
self._dummy_head.next = self._Node(key, value, self._dummy_head.next)
self._size += 1
else:
node.value = value
def setter(self, key, value):
node = self.get_node(key)
if not node:
raise ValueError('Key "{}" doesn\'t exist!'.format(str(key)))
node.value = value
def remove(self, key):
prev = self._dummy_head
while not prev.next:
if prev.next.key == key:
break
prev = prev.next
if not prev.next:
delNode = prev.next
prev.next = delNode.next
delNode.next = None
self._size -= 1
return delNode.value
return None
if __name__ == '__main__':
words = ''
with open('./shakespeare.txt', 'r') as f:
words = f.read()
words = words.split()
from time import time
start_time = time()
linkedlist_map = LinkedListMap()
for word in words:
if linkedlist_map.contains(word):
linkedlist_map.setter(word, linkedlist_map.getter(word) + 1)
else:
linkedlist_map.add(word, 1)
print('Total words: ', len(words))
print('Unique words: ', linkedlist_map.get_size())
print('Contains word "they": ', linkedlist_map.contains('they'))
## 耗时290秒左右
print('Total time: {} seconds'.format(time() - start_time))