目前替换策略有四种算法：
随机算法
双向链表python实现
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
| class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
def __str__(self):
val = f'{{{self.key} : {self.value}}}'
return val
def __repr__(self):
val = f'{{{self.key} : {self.value}}}'
return val
class DoubleLinkedList:
def __init__(self, capaity=0xffff):
self.capaity = capaity
self.head = None
self.tail = None
self.size = 0
def add_head(self, node: Node):
if not self.head:
self.head = node
self.tail = node
self.head.next = None
self.head.prev = None
else:
node.next = self.head
self.head.prev = node
self.head = node
self.head.prev = None
self.size += 1
return node
def add_tail(self, node: Node):
if not self.tail:
self.tail = node
self.head = node
self.tail.next = None
self.tail.prev = None
else:
self.tail.next = node
node.prev = self.tail
self.tail = node
self.tail.next = None
self.size += 1
return node
def del_tail(self):
if not self.tail:
return
node = self.tail
if node.prev:
self.tail = node.prev
self.tail.next = None
else:
self.tail = self.head = None
self.size -= 1
return node
def del_head(self):
if not self.head:
return
node = self.head
if node.next:
self.head = node.next
self.head.prev = None
else:
self.tail = self.head = None
self.size -= 1
return node
def remove(self, node: Node):
if not node:
node = self.tail
if node == self.tail:
self.__del_tail()
elif node == self.head:
self.__del_head()
else:
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
return node
def print(self):
p = self.head
line = ""
while p:
line += "%s" % p
p = p.next
if p:
line += "=>"
print(line)
|
先进先出算法（FIFO）
✦把缓存看作是一个先进先出的队列
✦优先替换最先进入队列的字块
python 实现代码
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
| from DoubleLinkedList import DoubleLinkedList, Node
class FIFOCache():
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.map = {}
self.list = DoubleLinkedList(self.capacity)
def get(self, key):
if key not in self.map:
return -1
else:
node: Node = self.map.get(key)
return node.value
def put(self, key, value):
if self.capacity == 0:
return "容量为0"
if key in self.map:
node: Node = self.map.get(key)
self.list.remove(node)
node.value = value
self.list.add_tail(node)
else:
if self.size == self.capacity:
node = self.list.del_tail()
del self.map[node.key]
self.size -= 1
node = Node(key, value)
self.list.add_tail(node)
self.map[key] = node
self.size += 1
def print(self):
return self.list.print()
|
最不经常使用算法（LFU）
✦优先淘汰最不经常使用的字块
✦需要额外的空间记录字块的使用频率
✦ 同频率节点按FIFO算法淘汰
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
| from DoubleLinkedList import DoubleLinkedList, Node
class LFUNode(Node):
def __init__(self, key, value):
self.freq = 0
super(LFUNode, self).__init__(key, value)
class LFUCache():
def __init__(self, capacity):
self.capacity = capacity
self.map = {}
self.freq_map = dict()
self.size = 0
def update_freq(self, node: LFUNode):
freq = node.freq
node = self.freq_map[freq].remove(node)
if self.freq_map[freq].size == 0:
del self.freq_map[freq]
freq += 1
node.freq = freq
if freq not in self.freq_map:
self.freq_map[freq] = DoubleLinkedList()
self.freq_map[freq].add_tail(node)
def get(self, key):
if key not in self.map:
return -1
node = self.map.get(key)
self.update_freq(node)
return node.value
def put(self, key, value):
if self.capacity == 0:
return "容量为0"
if key in self.map:
node = self.map.get(key)
node.value = value
self.update_freq(node)
else:
if self.capacity == self.size:
min_freq = min(self.freq_map)
node = self.freq_map[min_freq].del_tail()
del self.map[node.key]
self.size -= 1
node = LFUNode(key, value)
node.freq = 1
self.map[key] = node
if node.freq not in self.freq_map:
self.freq_map[node.freq] = DoubleLinkedList()
node = self.freq_map[node.freq].add_tail(node)
self.size += 1
def print(self):
print("***************")
for k, v in self.freq_map.items():
print(f"频率= {k}")
self.freq_map[k].print()
|
最近最少使用算法（LRU）
✦优先淘汰一段时间内没有使用的字块
✦有多种实现方法，一般使用双向链表
✦把当前访问节点置于链表前面（保证链表头部节点是最近使用的）
✦缓存淘汰时，把链表尾部的节点淘汰即可
python 代码实现
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
| from DoubleLinkedList import DoubleLinkedList, Node
class LRUCache():
def __init__(self, capacity):
self.capacity = capacity
self.map = {}
self.list = DoubleLinkedList(self.capacity)
def get(self, key):
if key in self.map:
node: Node = self.map[key]
self.list.remove(node)
self.list.add_head(node)
return node.value
else:
return -1
def put(self, key, value):
if key in self.map:
node: Node = self.map.get(key)
self.list.remove(node)
node.value = value
self.list.add_head(node)
else:
node = Node(key, value)
if self.list.capacity <= self.list.size:
old_node = self.list.del_tail()
self.map.pop(old_node.key)
self.list.add_head(node)
self.map[key] = node
def print(self):
self.list.print()
|
LRU 问题：时间复杂度？ 多线程下怎么优化?
