ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > 如何实现一个LRU缓存机制

如何实现一个LRU缓存机制

原创 Python 作者：mingtian66 时间：2024-09-04 22:02:58 0 删除 编辑

问题‌：‌ 实现一个LRU（‌最近最少使用）‌缓存机制。‌它应该支持以下操作：‌获取数据 get 和 写入数据 put。‌

获取数据 get(key) - 如果密钥（‌key）‌存在于缓存中，‌则获取密钥的值（‌总是正数）‌，‌否则返回 -1。‌
写入数据 put(key, value) - 如果密钥不存在，‌请设置或插入值。‌当缓存容量达到上限时，‌它应该在写入新数据之前使最近最少使用的数据无效。‌
‌ 进阶‌：‌
你是否可以在 O(1) 时间复杂度内完成这两种操作？‌
‌ 示例‌：‌

pythonCopy CodeLRUCache cache = new LRUCache(2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3cache.get(4);       // 返回  4

‌ 解答思路‌：‌
使用Python中的 OrderedDict可以方便地实现这个LRU缓存，‌因为它维护了元素的插入顺序，‌当容量满时，‌可以通过 popitem(last=False)删除最早插入的元素。‌

pythonCopy Codefrom collections import OrderedDictclass LRUCache:    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity    def get(self, key: int) -> int:        if key not in self.cache:            return -1
        else:
            self.cache.move_to_end(key)  # 将访问的key移到最末端表示最近使用
            return self.cache[key]    def put(self, key: int, value: int) -> None:        if key in self.cache:
            self.cache.move_to_end(key)  # 将已存在的key移到最末端表示最近使用
        self.cache[key] = value        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 删除最久未使用的元素# 测试代码cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)print(cache.get(1))       # 返回  1cache.put(3, 3)           # 该操作会使得密钥 2 作废print(cache.get(2))       # 返回 -1 (未找到)cache.put(4, 4)           # 该操作会使得密钥 1 作废print(cache.get(1))       # 返回 -1 (未找到)print(cache.get(3))       # 返回  3print(cache.get(4))       # 返回  4

这个问题结合了数据结构（‌哈希表+双向链表）‌和算法（‌LRU算法）‌的知识，‌是解决实际应用中缓存问题的常见方法。‌

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3026862/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： java开发中容易忽略的安全因素
下一篇： java怎样修复损坏的.class文件？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    602803

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593