做网站信息,坪山住房和建设局网站,汉中市建设工程招投标信息网官网,百度一下网页版浏览器Python算法题集_LRU 缓存 题146#xff1a;LRU 缓存1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【队列字典】2) 改进版一【有序字典】3) 改进版二【双向链表字典】 4. 最优算法 本文为Python算法题集之一的代码示例
题146#xff1a;LRU … Python算法题集_LRU 缓存 题146LRU 缓存1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【队列字典】2) 改进版一【有序字典】3) 改进版二【双向链表字典】 4. 最优算法 本文为Python算法题集之一的代码示例
题146LRU 缓存
1. 示例说明 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例 输入
[LRUCache, put, put, get, put, get, put, get, get, get]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示 1 capacity 30000 key 100000 value 105最多调用 2 * 105 次 get 和 put 2. 题目解析
- 题意分解
本题为设计一个整形缓存类可以指定缓存大小基本的设计思路是采用队列控制使用次序字典进行缓存【哈希】
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 可以考虑采用有序字典设计缓存类 可以考虑采用双向链表设计使用队列缓存还是采用字典 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大因此需要本地化测试解决这个问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题本地化超时测试用例自己生成详见【最优算法章节】 3. 代码展开
1) 标准求解【队列字典】
队列控制使用次序字典保存键值对
勉强通关超过05%
import CheckFuncPerf as cfpclass LRUCache_base:
def __init__(self, capacity):self.queue, self.dict, self.capacity, self.queuelen [], {}, capacity, 0
def get(self, key):if key in self.queue:self.queue.remove(key)self.queue.append(key)return self.dict[key]else:return -1
def put(self, key, value):if key in self.queue:self.queue.remove(key)else:if self.queuelen self.capacity:self.dict.pop(self.queue.pop(0))else:self.queuelen 1self.queue.append(key)self.dict[key] valutmpLRUCache LRUCache_base(5)
result cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 testLRUCache 的运行时间为 561.12 ms内存使用量为 4.00 KB 执行结果 992) 改进版一【有序字典】
采用有序字典【Python3.6之后支持】同时支持使用顺序和保存键值对
性能卓越超越93%
import CheckFuncPerf as cfpclass LRUCache_ext1:def __init__(self, capacity):self.data dict()self.capacity capacitydef get(self, key):keyval self.data.get(key, -1)if keyval ! -1:self.data.pop(key)self.data[key] keyvalreturn keyvaldef put(self, key, value)if key in self.data:self.data.pop(key)self.data[key] valueelse:if len(self.data) self.capacity:self.data[key] valueelse:firstpop next(iter(self.data))self.data.pop(firstpop)self.data[key] valuetmpLRUCache LRUCache_ext1(5)
result cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 testLRUCache 的运行时间为 420.10 ms内存使用量为 0.00 KB 执行结果 993) 改进版二【双向链表字典】
采用双向链表维护使用顺序字典保存键值对要首先定义双向链表类
性能卓越超过92%
import CheckFuncPerf as cfpclass ListNodeDouble:def __init__(self, keyNone, valueNone):self.key keyself.value valueself.prev Noneself.next None
class LRUCache_ext2:def __init__(self, capacity):self.capacity capacityself.dict {}self.head ListNodeDouble()self.tail ListNodeDouble()self.head.next self.tailself.tail.prev self.headdef move_to_tail(self, key):tmpnode self.dict[key]tmpnode.prev.next tmpnode.nexttmpnode.next.prev tmpnode.prevtmpnode.prev self.tail.prevtmpnode.next self.tailself.tail.prev.next tmpnodeself.tail.prev tmpnodedef get(self, key: int):if key in self.dict:self.move_to_tail(key)result self.dict.get(key, -1)if result -1:return resultelse:return result.valuedef put(self, key, value):if key in self.dict:self.dict[key].value valueself.move_to_tail(key)else:if len(self.dict) self.capacity:self.dict.pop(self.head.next.key)self.head.next self.head.next.nextself.head.next.prev self.headnewkeyval ListNodeDouble(key, value)self.dict[key] newkeyvalnewkeyval.prev self.tail.prevnewkeyval.next self.tailself.tail.prev.next newkeyvalself.tail.prev newkeyvaltmpLRUCache LRUCache_ext2(5)
result cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 testLRUCache 的运行时间为 787.18 ms内存使用量为 0.00 KB 执行结果 994. 最优算法
根据本地日志分析最优算法为第2种方式【有序字典】LRUCache_ext1
def testLRUCache(lrucache, actiions):for act in actiions:if len(act) 1:lrucache.put(act[0], act[1])else:lrucache.get(act[0])return 99
import random
actions []
iLen 1000000
for iIdx in range(10):actions.append([iIdx, random.randint(1, 10)])
iturn 0
for iIdx in range(iLen):if iturn 2:actions.append([random.randint(1,10)])else:actions.append([random.randint(1,10), random.randint(1, 1000)])iturn 1if iturn 3:iturn 0
tmpLRUCache LRUCache_base(5)
result cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 算法本地速度实测比较
函数 testLRUCache 的运行时间为 561.12 ms内存使用量为 4.00 KB 执行结果 99
函数 testLRUCache 的运行时间为 420.10 ms内存使用量为 0.00 KB 执行结果 99
函数 testLRUCache 的运行时间为 787.18 ms内存使用量为 0.00 KB 执行结果 99一日练一日功一日不练十日空
may the odds be ever in your favor ~
