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
| #!/usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):
"""节点包含前后指针和键值"""
def __init__(self, key, value, pre=None, post=None):
self.key = key
self.value = value
self.pre = pre
self.post = post
def __repr__(self):
return 'Node({},{})'.format(self.key, self.value)
__str__ = __repr__
class LRUCache(object):
def __init__(self, capacity=10):
"""容量大小，初始化头尾节点"""
self.size = 0
self.capacity = capacity
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.post = self.tail
self.tail.pre = self.head
self.key_map = dict()
def set(self, k, v):
node = self.key_map.get(k)
if node is not None:
self.key_map[k] = v
self._move_node(node)
else:
node = Node(k, v)
self._add_node(node)
self.key_map[k] = node
self.size += 1
if self.size >= self.capacity:
node = self._pop_node()
self.key_map.pop(node.key)
self.size -= 1
def get(self, k):
"""获取操作"""
node = self.key_map.get(k)
if node is not None:
self._move_node(node)
return node.value
else:
print('miss key')
return -1
# raise KeyError('key not exist')
def _add_node(self, node):
"""增加node至head后"""
node.pre = self.head
node.post = self.head.post
self.head.post.pre = node
self.head.post = node
def _remove_node(self, node):
"""删除node"""
node.pre.post = node.post
node.post.pre = node.pre
def _move_node(self, node):
"""移动至头部"""
self._remove_node(node)
self._add_node(node)
def _pop_node(self):
"""弹出尾节点"""
node = self.tail.pre
self._remove_node(node)
return node
def print_node(self):
node = self.head
while node.post != self.tail:
yield node.post
node = node.post
if __name__ == '__main__':
import random
cache = LRUCache()
for i in range(20):
k = random.randint(0, 5)
if k % 2 == 0:
cache.set(i, i)
print('set {}'.format(i))
else:
v = cache.get(k)
print('get {}, value {}'.format(k, v))
print('->'.join(str(i) for i in cache.print_node()))
|