python实现LRU置换算法、LFU置换算法（补充self.map的使用和字典的方法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python实现LRU置换算法、LFU置换算法（补充self.map的使用和字典的方法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5320字，纯文字阅读大概需要8分钟。
内容图文
关于本地存放的映射关系map：
本质上是一个空字典：self.map={}
每次新增一个节点node，都会把node的key, value放入map中： self.map[key] = node ==> self.map的样子应该是{key1:node1, key2:node2} （注意：node是一个自定义的新的类，详见：https://www.cnblogs.com/marvintang1001/p/11125619.html ）
取出字典一个键值对（返回的是值）： node = self.map[key] （这是非安全方法，如果没有这个key会报错。安全方法：value = my_dict.get("key") 如果没有这个键就返回None。）
删除字典一对键值的方法： self.map.pop(key) 或者是 del self.map[key]
for k, v in self.freq_map.items(): 字典的items方法：返回可遍历的(键, 值) 元组数组
*关于字典的应用：https://www.cnblogs.com/lowmanisbusy/p/9142199.html
LRU（最近最少使用）算法：
每次使用，把使用的节点放到链表最前面
淘汰缓存时，把链表尾部的节点淘汰
#! -*- encoding=utf-8 -*-
from computer_principle.doublelinkedlist import DoubleLinkedList, Node
class LRUCache(object):
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # 保存key和value的映射关系
self.list = DoubleLinkedList(self.capacity)
# 每次使用，把使用的节点放到链表最前面，返回值
def get(self, key):
if key in self.map:
node = self.map[key] # 取出这个key和它的值
self.list.remove(node)
self.list.append_front(node) #把这个缓存放到最前面
return node.value
else:
return -1
#添加一个缓存
def put(self, key, value):
# 先判断key是否已经在缓存里:
if key in self.map: #是在缓存里：更新value，放入最前面
node = self.map.get(key)
self.list.remove(node)
node.value = value
self.list.append_front(node)
else:
node = Node(key, value)
#缓存已经满了的话需要先删掉最后一个再往head增加新的：
if self.list.size >= self.list.capacity-1:
old_node = self.list.remove()
self.map.pop(old_node.key) #删除节点同时要删除本地映射
self.list.append_front(node)
self.map[key] = node
def print(self):
self.list.print()
# test:
if __name__ == '__main__':
cache = LRUCache(2)
cache.put(2, 2)
cache.print()
cache.put(1, 1)
cache.print()
cache.put(3, 3) # 淘汰了（1，1）
cache.print()
print(cache.get(1))
cache.print()
print(cache.get(2))
cache.print()
print(cache.get(3))
cache.print()
结果：
{2: 2}
{1: 1}=>{2: 2}
{3: 3}=>{1: 1}
1
{1: 1}=>{3: 3}
-1
{1: 1}=>{3: 3}
3
{3: 3}=>{1: 1}
LFU（最不经常使用）算法：
淘汰缓存时，把使用频率最小的淘汰
存在相同频率的情况：每个频率单独做一个双向链表，淘汰时把最低频率的head节点淘汰掉（FIFO）
#! -*- encoding=utf-8 -*-
from computer_principle.doublelinkedlist import DoubleLinkedList, Node
class LFUNode(Node):
def __init__(self, key, value):
self.freq = 0 # 新增一个freq属性
super(LFUNode, self).__init__(key, value) # 这是python2的写法。python3：super().__init__(key, value)
class LFUCache():
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # 保存key和value的映射关系
# key: 频率， value：频率对应的双向链表
self.freq_map = {}
self.list = DoubleLinkedList(self.capacity)
self.size = 0
# 更新节点频率的操作
def __update_freq(self, node):
freq = node.freq # 这个节点之前所在的频率的双向链表
# 删除:
node = self.freq_map[freq].remove(node)
if self.freq_map[freq].size == 0:
del self.freq_map[freq]
# 更新:
freq = freq+1
node.freq = freq
if freq not in self.freq_map:
self.freq_map[freq] = DoubleLinkedList()
self.freq_map[freq].append(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
# 缓存命中：
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) #freq_map里的key都是数字
node = self.freq_map[min_freq].pop() #默认pop是head
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].append(node)
self.size += 1
def print(self):
print('****************************')
for k, v in self.freq_map.items(): # 字典的items方法：返回可遍历的(键, 值) 元组数组
print('Freq = {}'.format(k))
self.freq_map[k].print()
print('****************************')
print()
# test:
if __name__ == '__main__':
cache = LFUCache(2)
cache.put(1, 1)
cache.print()
cache.put(2, 2)
cache.print()
print(cache.get(1))
cache.print()
cache.put(3, 3)
cache.print()
print(cache.get(2))
cache.print()
print(cache.get(3))
cache.print()
cache.put(4, 4)
cache.print()
print(cache.get(1))
cache.print()
# print(cache.get(2))
print(cache.get(3))
cache.print()
print(cache.get(4))
cache.print()
结果：
****************************
Freq = 1
{1: 1}
****************************
****************************
Freq = 1
{1: 1}=>{2: 2}
****************************
1
****************************
Freq = 1
{2: 2}
Freq = 2
{1: 1}
****************************
****************************
Freq = 1
{3: 3}
Freq = 2
{1: 1}
****************************
-1
****************************
Freq = 1
{3: 3}
Freq = 2
{1: 1}
****************************
3
****************************
Freq = 2
{1: 1}=>{3: 3}
****************************
****************************
Freq = 2
{3: 3}
Freq = 1
{4: 4}
****************************
-1
****************************
Freq = 2
{3: 3}
Freq = 1
{4: 4}
****************************
3
****************************
Freq = 1
{4: 4}
Freq = 3
{3: 3}
****************************
4
****************************
Freq = 3
{3: 3}
Freq = 2
{4: 4}
****************************
内容总结
以上是互联网集市为您收集整理的python实现LRU置换算法、LFU置换算法（补充self.map的使用和字典的方法）全部内容，希望文章能够帮你解决python实现LRU置换算法、LFU置换算法（补充self.map的使用和字典的方法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。