设计一个LRU(最近最少使用)缓存

这篇具有很好参考价值的文章主要介绍了设计一个LRU(最近最少使用)缓存。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

约束和假设

  • 我们正在缓存什么?
    我们正在缓存Web Query的结果
  • 我们可以假设输入是有效的,还是需要对其验证?
    假设输入是有效的
  • 我们可以假设它适应内存吗?

编码实现

class Node(object):
	def __init__(self, results):
		self.results = results
		self.prev = None
		self.next = None

class LinkedList(object):
	del __init__(self):
		self.head = None
		self.tail = None
	
	def move_to_front(self, node): # ...
	def append_to_front(self, node): # ...
	def remove_from_tail(self): # ...

class Cache(obejct):
	def __init__(self, MAX_SIZE):
		self.MAX_SIZE = MAX_SIZE
		self.size = 0
		self.lookup = {}
		self.linked_list = LinkedList()

	def get(self, query)
	'''
		Get the stored query result from the cache
		Accsssing a node updates its position to the front of the LRU list
	'''
	node = self.lookup.get(query)
	if node is None:
		return None
	self.linked_list.move_to_front(node)
	return node.results


	def set(self, resuts, query):
		'''Set the results for the given query key in the cache.
		When updating an entry, updates its position to the front of the LRU list
		If the entry is new and the cache is at capacity, remove the oldest entry before the new entry is added '''
		node = self.lookup.get(query)
		if node is not None:	
			node.results = results
			self.linked_list.move_to_front(node)
		else:
			if self.size == self.MAX_SIZE
				self.lookup.pop(self.linked_list.tail.query, None)
				self.linked_list.remove_from_tail()
			else:
				self.size += 1
			new_node = Node(results)
			self.linked_list.append_to_front(new_node)
			self.lookup[query] = new_node

文章来源地址https://www.toymoban.com/news/detail-819908.html

到了这里,关于设计一个LRU(最近最少使用)缓存的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 孩子都能学会的FPGA:第二十八课——用FPGA实现最近最少使用(LRU)算法

    (原创声明:该文是 作者的原创 ,面向对象是 FPGA入门者 ,后续会有进阶的高级教程。宗旨是 让每个想做FPGA的人轻松入门 , 作者不光让大家知其然,还要让大家知其所以然 !每个工程作者都搭建了全自动化的仿真环境,只需要双击 top_tb.bat 文件就可以完成整个的仿真(前

    2024年02月19日
    浏览(40)
  • verilog实例-近期最少使用算法(LRU)

    LRU算法 用于cache管理或任何其他需要对访问权进行周期更新的场合。 基于时间和空间考虑,cache中存储着近期将会用到的数据项。当cache被用满后,如果有新的数据项到来,需要将某个现有的数据项从cache中清除,为新进入者提供空间。此时通常使用的算法被称为LRU(Least Rece

    2024年02月08日
    浏览(52)
  • 【算法训练-模拟 一】模拟设计LRU缓存结构

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是LRU缓存结构设计,这类题目出现频率还是很高的,几乎所有大厂都常考。 当然面对这道题,首先要讲清楚LRU是干什么的 LRU(Least Recently Used)缓存结构是一种常见的缓存管理策略, 用于

    2024年02月10日
    浏览(50)
  • Python算法题集_LRU 缓存

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

    2024年02月21日
    浏览(40)
  • 【算法】用JAVA代码实现LRU 【缓存】【LRU】

    LRU(Least Recently Used)是一种常见的缓存淘汰策略,用于在缓存空间不足时确定哪些数据应该被淘汰。其基本原则是淘汰最近最少被访问的数据。 工作原理 : 最近使用优先 : LRU算法基于这样的思想:最近被使用的数据很可能在短时间内还会被使用,因此保留这些数据有助于

    2024年01月23日
    浏览(45)
  • LRU 缓存淘汰算法

    Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。 接收一个参数 capacity 作为缓存的最大容量 实现一个函数 put() 添加数据到缓存 实现一个函数 get() 查询缓存中的数据 以上函数应该在 (O(1)) 的时间内完成 满足以上需求的数据结构 —

    2024年02月11日
    浏览(56)
  • rust里如何快速实现一个LRU 本地缓存?

    LRU是Least Recently Used(最近最少使用)的缩写,是一种常见的缓存淘汰算法。LRU算法的基本思想是,当缓存空间已满时,优先淘汰最近最少使用的数据,以保留最常用的数据。 在计算机系统中,LRU算法常用于缓存系统、页面置换算法等场景,以提高数据访问的效率和性能。 要

    2024年02月13日
    浏览(41)
  • 数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

    关于LRU缓存 LRU - Lease Recently Used 最近使用 如果内存优先,只缓存最近使用的,删除 ‘沉睡’ 数据 核心 api: get set 分析 使用哈希表来实现, O(1) 必须是有序的,常用放在前面,沉睡放在后面, 即:有序,可排序 这样 {} 不符合要求;Map是可以排序的,按照设置顺序 不用 Map 如何

    2024年02月06日
    浏览(53)
  • 面试遇到算法题:实现LRU缓存

    请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。 这是一道大厂面试高频出现的算法题,难度为⭐️⭐️⭐️,属于中等,老铁们来一起看看这个题该怎么解? 没有废话,翠花,上酸菜! 为了实现一个满足 LRU (最近最少使用)缓存约束的数据结构,我们需

    2024年04月25日
    浏览(40)
  • 二维网格划分 LRU缓存设计

    有大量的二维矩形需要存储 查看点在哪些矩形中 给定一个矩形 查看与哪些矩阵相交 项目背景与图形图像基本无关,只涉及大文件分块读取,所以不用实现游戏行业中的物理引擎 使用空间划分算法:二维栅格将整个空间划分为多个小区域。每个小区域中包含若干个矩形,以

    2024年02月14日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包