本文实例为大家分享了python实现LFU算法的具体代码,供大家参考,具体内容如下
在第一节中实现了双向链表DoubleLinkedList类,上一节中基于双向链表实现了LRU算法,本节课我们继续基于双向链表实现LFU(Least frequently used 最不经常使用)算法。
一、重写Node节点类
构建LFUNode类 继承自第一节中的Node类,添加freq属性用来表示节点使用频率
1
2
3
4
5
6
7
8
9
10
|
class LFUNode(Node): def __init__( self , key, value): """ LFU节点 增加频率属性 :param key: :param value: """ self .freq = 0 super (LFUNode, self ).__init__(key, value) |
二、LFU实现
LFU的实现除了get和put之外还有一个私有的__update_freq更新节点频率方法,读写某节点时都需要对该节点的频率属性进行更新。除了map之外新增加一个freq_map来存储每个频率下的双向链表,当达到最大容量时移除最小频率下的头部的节点。
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
|
class LFUCache( object ): def __init__( self , capacity = 0xffffffff ): """ LFU缓存置换算法 最不经常使用 :param capacity: """ self .capacity = capacity self .size = 0 self . map = {} self .freq_map = {} def __update_freq( self , node): """ 更新节点频率 :param node: :return: """ freq = node.freq # 当前节点所在频率存在 在当前频率链表中移除当前节点 if freq in self .freq_map: 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].append(node) return node def get( self , key): """ 获取元素 :return: """ # 节点不存在 if key not in self . map : return None # 节点存在 更新使用频率 old_node = self . map .get(key) new_node = self .__update_freq(old_node) self . map [key] = new_node return new_node.value def put( self , key, value): """ 设置元素 :param key: :param value: :return: """ # 节点已存在 更新频率 if key in self . map : old_node = self . map .get(key) old_node.value = value new_node = self .__update_freq(old_node) self . map [key] = new_node else : # 节点容量达到上限 移除最小频率链表头部的节点 if self .size > = self .capacity: min_freq = min ( self .freq_map) node = self .freq_map[min_freq].pop() del self . map [node.key] self .size - = 1 # 构建新的节点 更新频率 new_node = LFUNode(key, value) new_node = self .__update_freq(new_node) self . map [key] = new_node self .size + = 1 return new_node def print ( self ): """ 打印当前链表 :return: """ for freq, link in self .freq_map.items(): print ( "frequencies: %d" % freq) link. print () |
三、测试逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
if __name__ = = '__main__' : lfu_cache = LFUCache( 4 ) lfu_cache.put( 1 , 1 ) lfu_cache. print () lfu_cache.put( 2 , 2 ) lfu_cache. print () print (lfu_cache.get( 1 )) lfu_cache. print () lfu_cache.put( 3 , 3 ) lfu_cache. print () lfu_cache.put( 4 , 4 ) lfu_cache. print () lfu_cache.put( 5 , 5 ) lfu_cache. print () print (lfu_cache.get( 2 )) lfu_cache.put( 4 , 400 ) lfu_cache. print () |
测试结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/wang_xiaowang/article/details/105911715