在第一节中已经实现了双向链表DoubleLinkedList类，本节我们基于双向链表实现LRU（Least Recently Used最近最少使用）缓存置换算法。Redis的淘汰机制就包括LRU算法，用来淘汰那些最近最少使用的数据，具体怎么使用可在redis的配置文件中设置。
一、LRU算法的实现
逻辑很简单，get和put两种操作，其中get时如果元素存在则将节点从当前位置移到链表头部，表示最近被访问到的节点；put时也是，不管节点之前存不存在都要移动到链表头部。同样通过一个map来实现查找时的O(1)复杂度。
|
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
|
class LRUCache(object): def __init__(self, capacity=0xffffffff): """ LRU缓存置换算法 最近最少使用 :param capacity: """ self.capacity = capacity self.size = 0 self.map = {} self.list = DoubleLinkedList(capacity) def get(self, key): """ 获取元素 获取元素不存在 返回None 获取元素已存在 将节点从当前位置删除并添加至链表头部 :param key: :return: """ # 元素不存在 if key not in self.map: return None node = self.map.get(key) self.list.remove(node) self.list.append_front(node) return node.value def put(self, key, value): """ 添加元素 被添加的元素已存在 更新元素值并已到链表头部 被添加的元素不存在 链表容量达到上限 删除尾部元素 链表容量未达上限 添加至链表头部 :param key: :param value: :return: """ if key in self.map: node = self.map.get(key) node.value = value self.list.remove(node) self.list.append_front(node) else: if self.size >= self.capacity: old_node = self.list.remove() del self.map[old_node.key] self.size -= 1 node = Node(key, value) self.map[key] = node self.list.append_front(node) self.size += 1 return node def print(self): """ 打印当前链表 :return: """ self.list.print() |
二、测试逻辑
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
if __name__ == '__main__': lru_cache = LRUCache(3) lru_cache.put(1, 1) lru_cache.print() lru_cache.put(2, 2) lru_cache.print() print(lru_cache.get(1)) lru_cache.print() lru_cache.put(3, 3) lru_cache.print() lru_cache.put(1, 100) lru_cache.print() lru_cache.put(4, 4) lru_cache.print() print(lru_cache.get(1)) lru_cache.print() |
测试结果:
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/wang_xiaowang/article/details/105911679
