LFU(最近最不常用)实现(python)
2024-10-21 18:52:54
from collections import defaultdict, OrderedDict class Node:
__slots__ = 'key', 'val', 'cnt' def __init__(self, key, val, cnt=0):
self.key, self.val, self.cnt = key, val, cnt class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # type {key: node}
self.cnt2node = defaultdict(OrderedDict)
self.mincnt = 0 def get(self, key, default=-1):
if key not in self.cache:
return default node = self.cache[key]
del self.cnt2node[node.cnt][key] if not self.cnt2node[node.cnt]:
del self.cnt2node[node.cnt] node.cnt += 1
self.cnt2node[node.cnt][key] = node if not self.cnt2node[self.mincnt]:
self.mincnt += 1
return node.val def put(self, key, value):
if key in self.cache:
self.cache[key].val = value
self.get(key)
return
if len(self.cache) >= self.capacity:
pop_key, _pop_node = self.cnt2node[self.mincnt].popitem(last=False)
del self.cache[pop_key] self.cache[key] = self.cnt2node[1][key] = Node(key, value, 1)
self.mincnt = 1 def test():
c = LFUCache(2)
c.put(1, 1)
c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)
assert c.get(2) == -1
assert c.get(3) == 3
c.put(4, 4)
assert c.get(1) == -1
assert c.get(3) == 3
assert c.get(4) == 4 if __name__ == '__main__':
test()
最新文章
- Sublime Text 全程指引 by Lucida
- asp.net core 1.1 升级后,操作mysql出错的解决办法。
- 笔记:xubuntu下如何让系统默认使用nvidia显卡,而不是intel集显
- 循序渐进Python3(十)-- 4 -- paramiko
- [CoreOS 转载] CoreOS实践指南(六):分布式数据存储Etcd(下)
- mysql 出现错误Incorrect file format
- 【转】微信Android SDK示例代码及运行方法
- LeetCode之Min Stack
- python包
- python 13 常用模块 一
- Python开发【第七篇】:面向对象二
- 《转载》python爬虫实践之模拟登录
- 安全测试5_服务端的安全漏洞(SQL注入、命令注入、文件操作类)
- JFinal -基于Java 语言的MVC极速 web 开发框架
- 实现单台测试机6万websocket长连接
- PHP正则表达式匹配俄文字符
- [ IOS ] iOS-控制器View的创建和生命周期
- 基于Cocos2d-x学习OpenGL ES 2.0系列——初识MVP(3)
- Dekker算法在多核处理器下的失效
- 用Word2007写CSDN博客