Python算法题集_LRU 缓存

这篇具有很好参考价值的文章主要介绍了Python算法题集_LRU 缓存。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文为Python算法题集之一的代码示例

题146:LRU 缓存

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 ,则应该 逐出 最久未使用的关键字。

    函数 getput 必须以 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); // 缓存是 {1=1}
    lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
    lRUCache.get(1);    // 返回 1
    lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
    lRUCache.get(2);    // 返回 -1 (未找到)
    lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
    lRUCache.get(1);    // 返回 -1 (未找到)
    lRUCache.get(3);    // 返回 3
    lRUCache.get(4);    // 返回 4
    

    提示:

    • 1 <= capacity <= 3000
    • 0 <= key <= 10000
    • 0 <= value <= 105
    • 最多调用 2 * 105getput

2. 题目解析

- 题意分解

  1. 本题为设计一个整形缓存类,可以指定缓存大小
  2. 基本的设计思路是采用队列控制使用次序,字典进行缓存【哈希】

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 可以考虑采用有序字典设计缓存类

    2. 可以考虑采用双向链表设计使用队列,缓存还是采用字典


- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见【最优算法章节】

3. 代码展开

1) 标准求解【队列+字典】

队列控制使用次序,字典保存键值对

勉强通关,超过05%Python算法题集_LRU 缓存,Python,python,算法,缓存,LRU,leetcode

import CheckFuncPerf as cfp

class 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 += 1
   self.queue.append(key)
   self.dict[key] = valu

tmpLRUCache = LRUCache_base(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 testLRUCache 的运行时间为 561.12 ms;内存使用量为 4.00 KB 执行结果 = 99

2) 改进版一【有序字典】

采用有序字典【Python3.6之后支持】,同时支持使用顺序和保存键值对

性能卓越,超越93%Python算法题集_LRU 缓存,Python,python,算法,缓存,LRU,leetcode

import CheckFuncPerf as cfp

class LRUCache_ext1:
 def __init__(self, capacity):
     self.data = dict()
     self.capacity = capacity
 def get(self, key):
     keyval = self.data.get(key, -1)
     if keyval != -1:
         self.data.pop(key)
         self.data[key] = keyval
     return keyval
 def put(self, key, value)
     if key in self.data:
         self.data.pop(key)
         self.data[key] = value
     else:
         if len(self.data) < self.capacity:
             self.data[key] = value
         else:
             firstpop = next(iter(self.data))
             self.data.pop(firstpop)
             self.data[key] = value

tmpLRUCache = LRUCache_ext1(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 testLRUCache 的运行时间为 420.10 ms;内存使用量为 0.00 KB 执行结果 = 99

3) 改进版二【双向链表+字典】

采用双向链表维护使用顺序,字典保存键值对,要首先定义双向链表类

性能卓越,超过92%Python算法题集_LRU 缓存,Python,python,算法,缓存,LRU,leetcode

import CheckFuncPerf as cfp

class ListNodeDouble:
 def __init__(self, key=None, value=None):
     self.key = key
     self.value = value
     self.prev = None
     self.next = None
class LRUCache_ext2:
 def __init__(self, capacity):
     self.capacity = capacity
     self.dict = {}
     self.head = ListNodeDouble()
     self.tail = ListNodeDouble()
     self.head.next = self.tail
     self.tail.prev = self.head
 def move_to_tail(self, key):
     tmpnode = self.dict[key]
     tmpnode.prev.next = tmpnode.next
     tmpnode.next.prev = tmpnode.prev
     tmpnode.prev = self.tail.prev
     tmpnode.next = self.tail
     self.tail.prev.next = tmpnode
     self.tail.prev = tmpnode
 def get(self, key: int):
     if key in self.dict:
         self.move_to_tail(key)
     result = self.dict.get(key, -1)
     if result == -1:
         return result
     else:
         return result.value
 def put(self, key, value):
     if key in self.dict:
         self.dict[key].value = value
         self.move_to_tail(key)
     else:
         if len(self.dict) == self.capacity:
             self.dict.pop(self.head.next.key)
             self.head.next = self.head.next.next
             self.head.next.prev = self.head
         newkeyval = ListNodeDouble(key, value)
         self.dict[key] = newkeyval
         newkeyval.prev = self.tail.prev
         newkeyval.next = self.tail
         self.tail.prev.next = newkeyval
         self.tail.prev = newkeyval

tmpLRUCache = LRUCache_ext2(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 testLRUCache 的运行时间为 787.18 ms;内存使用量为 0.00 KB 执行结果 = 99

4. 最优算法

根据本地日志分析,最优算法为第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 += 1
    if 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 ~文章来源地址https://www.toymoban.com/news/detail-832017.html

到了这里,关于Python算法题集_LRU 缓存的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-中等题】146. LRU 缓存

    LRU缓存是什么:LRU缓存机制,你想知道的这里都有 实现 LRU 缓存算法 map —key存 integer value存链表节点 ListNode 存 next 和prev 引用 以及 存 key 和value 具体值 图解:官方图解 步骤: 定义一个自定义的双向链表节点类 DLinkedNode,该类包含 key 和 value 字段,并且具有 prev 和 next 指针

    2024年02月10日
    浏览(48)
  • 【LeetCode刷题-链表】--146.LRU缓存

    方法一:哈希表+双向链表 使用一个哈希表和一个双向链表维护所有在缓存中的键值对 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久使用的 哈希表即为普通的哈希映射,通过缓存数据的键映射到其在双向链表中的

    2024年02月05日
    浏览(44)
  • leetcode做题笔记146. LRU 缓存

    请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现  LRUCache  类: LRUCache(int capacity)  以  正整数  作为容量  capacity  初始化 LRU 缓存 int get(int key)  如果  key  存在于缓存中,则返回的值,否则返回  -1  。 void put(int key, int value)  如果

    2024年02月07日
    浏览(36)
  • Leetcode 146. LRU 缓存(Hashmap+双链表)

    请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: ● LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 ● int get(int key) 如果 key 存在于缓存中,则返回的值,否则返回 -1 。 ● void put(int key, int value) 如果 key 已

    2024年02月16日
    浏览(47)
  • Python算法题集_两数之和

    本文为Python算法题集之一的代码示例 题目1:两数之和 说明:给定一个整数列表(数值不重复) nums 和一个整数目标值 target,请在该数组中找出和为目标值 target 的整数对,并返回数组下标对 简单版【只有一个两数和等于目标值】 加强版【有多个两数和等于目标值】 一日练

    2024年01月23日
    浏览(43)
  • Python算法题集_字母异位词分组

    本文为Python算法题集之一的代码示例 题目49:字母异位词分组 说明:给你一个字符串数组,请你将 字母异位词 组合在一起,可以按任意顺序返回结果列表 字母异位词 :是由重新排列原单词所有字母得到的新单词 使用同步数组 list 和检索集合 set 使用同步数组 list 和结果数

    2024年01月20日
    浏览(37)
  • 【leetcode100-035】【链表/哈希链表】LRU缓存

    【题干】 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现  LRUCache  类: LRUCache(int capacity)  以  正整数  作为容量  capacity  初始化 LRU 缓存 int get(int key)  如果  key  存在于缓存中,则返回的值,否则返回  -1  。 void put(int key, in

    2024年02月01日
    浏览(43)
  • 二刷LeetCode--146.LRU缓存(C++版本),必会题目

    本题思路:因为需要记录元素的出入顺序,并且每次访问之后需要将该节点提到最前面,因此需要使用双向链表(单链表不方便删除操作),而为了可以在常量时间复杂度内找到对应的元素,我们需要使用哈希表,将每一个插入的元素在哈希表中进行记录.哈希表的key就是插入的key,而哈希

    2024年02月13日
    浏览(37)
  • LeetCode讲解篇之面试题 16.25. LRU 缓存

    设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。 它应该支持以下操作: 获取数据 get 和 写入数据 put 。

    2024年02月09日
    浏览(48)
  • [力扣146. LRU 缓存 ](https://leetcode.cn/problems/lru-cache/description/)

    力扣146. LRU 缓存 使用LinkedHashmap(HashMap的子类,能够记住插入数据的顺序). LRU是Lease Recently User的缩写,意思是最近 最少使用。比如设计一个文件缓存系统,每个文件有自己的大小和访问时间,文件缓存系统有总的大小,当往这个文件系统中放入新的文件时,如果发现超出文件

    2024年02月11日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包