LRU数据结构

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

LRU缓存是非常经典的数据结构设计,本文重点在于设计出get、put方法时间复杂度都为O(1)的LRU缓存

LRU缓存特征是当超出容量时会将最近最少使用的元素逐出

第一次的失败尝试——记录有效区间

记录有效区间的方法是通过计数器counter为每一个最近使用的元素记录最新计数,在每次访问的时候更新有效区间

比如对于容量为2的lru而已,先put(1,1),然后put(2,2),那么1的counter就会是0,2的counter是1,此时有效区间是[0,1]。那么当2再次被访问的时候,2的counter便会变为2,此时有效区间是[0,2],所以访问的1、2都是有效

当再次put(3,3)的时候,3的counter便为3,有效区间的右边界变为3;但因为已经超出容量此时有效区间就会在原来基础上缩小范围,所以最终的有效区间变成[1,3],那么1已经被排除有效区间之外了

然而这种做法的问题是一旦有效元素被多次访问,且put新元素的时候,就难以搞清楚有效区间在哪里,这需要更高的时间复杂度才可能做到

通过测试用例的尝试——双向链表+hash表

从第一次失败的尝试我找到的瓶颈是无法在O(1)复杂度将最近使用的元素从任意逐出顺序中置为最后,而能做到这点的只有双向链表。然而双向链表找到元素复杂度确是O(1),那么便只能用上hash表从而使得时间复杂度优化到O(1)文章来源地址https://www.toymoban.com/news/detail-555303.html

type quickLinkedTable struct {
	head, tail *qlt
	cap        int
	m          map[int]*qlt
}

func newQLT(cap int) *quickLinkedTable {
	return &quickLinkedTable{
		cap: cap,
		m:   make(map[int]*qlt, cap),
	}
}

func (t *quickLinkedTable) push(key, value int) {
	// 若当前key存在,则更新,并置于头部
	if q, ok := t.m[key]; ok {
		q.value = value
		t.moveToHead(q)
		return
	}

	// 创建新链表元素,使head指向该元素,并更新hash表
	q := newQlt(key, value)
	if t.head != nil {
		t.head.next = q
	}
	q.pre = t.head
	t.head = q
	t.m[key] = q
	if t.tail == nil {
		t.tail = q
	}

	// 当超出容量时,删除尾部
	if len(t.m) > t.cap {
		tail := t.tail
		t.tail = t.tail.next
		t.tail.pre = nil
		delete(t.m, tail.key)
	}
}

func (t *quickLinkedTable) get(key int) int {
	if q, ok := t.m[key]; ok {
		t.moveToHead(q)
		return q.value
	}
	return -1
}

func (t *quickLinkedTable) moveToHead(q *qlt) {
	// q本身是head就直接返回(仅有head next为nil)
	if q.next == nil {
		return
	}

	// 若q是tail,则更新q next为新tail
	// 若q不是tail,则将q移出去,使q前后元素相连
	if q.pre == nil {
		t.tail = q.next
		t.tail.pre = nil
	} else {
		q.pre.next = q.next
	}
	q.next.pre = q.pre

	// 使原head next指向q,并更新q为head,
	q.pre = t.head
	t.head.next = q
	q.next = nil
	t.head = q
}

type qlt struct {
	key       int
	pre, next *qlt
	value     int
}

func newQlt(key, value int) *qlt {
	return &qlt{key: key, value: value}
}

type LRUCache struct {
	t *quickLinkedTable
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		t: newQLT(capacity),
	}
}

func (this *LRUCache) Get(key int) int {
	return this.t.get(key)
}

func (this *LRUCache) Put(key int, value int) {
	this.t.push(key, value)
}

Ref

  1. https://leetcode.cn/problems/lru-cache/description/

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

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

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

相关文章

  • 数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

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

    2024年02月06日
    浏览(53)
  • 【数据结构】LRU缓存的简单模拟实现(leetcode力扣146LRU缓存)

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

    2024年02月03日
    浏览(42)
  • [算法与数据结构]:LRU Cache 的原理与C++实现

    ​ LRU全称是Least Recently Used,即 最近最久未使用,是一种简单的缓存策略。顾名思义,LRU 算法会选出最近最少使用的数据进行淘汰。 ​ 那么什么是缓存(Cache)呢?缓存是一种提高数据读取性能的技术,可以有效解决存储器性能和容量的矛盾,是一种空间换时间的设计思想,比

    2024年01月20日
    浏览(46)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月24日
    浏览(43)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月21日
    浏览(55)
  • 数据结构英文习题解析-第一章 算法复杂度分析Algorithm Analysis

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW1 1. The major task of algorithm analysis is to an

    2024年03月12日
    浏览(68)
  • go专业数据结构与算法

    2.数组概念 3.golang实现数组结构 4.golang实现数组迭代器 5.数组栈的高级实现 6.栈模拟低级递归 7.斐波那契数列栈模拟递归 8.递归实现文件夹遍历 9.栈模拟文件递归 10.层级展示文件夹 11.数组队列的实现 12.队列实现遍历文件夹 13.循环队列 14.链式栈 15.链式队列 16.作业 17.为什么需

    2024年02月13日
    浏览(49)
  • 【Go基础】加密算法和数据结构

    加密过程的每一步都是可逆的 加密和解密用的是同一组密钥 异或是最简单的对称加密算法 DES(Data Encryption Standard)数据加密标准,是目前最为流行的加密算法之一 对原始数据(明文)进行分组,每组64位,最后一组不足64位时按一定规则填充,每一组上单独施加DES算法 DES子

    2024年02月02日
    浏览(30)
  • go数据结构(二叉树的遍历)

      用数组来存储二叉树如何遍历的呢? 如果父节点的数组下表是i,那么它的左孩子就是i * 2 + 1,右孩子就是 i * 2 + 2。  二叉树的遍历方式: 二叉树有 三种基本遍历方式 ,分别是 前序遍历、中序遍历和后序遍历 。遍历的原理是从根节点开始,按照特定方式递归遍历左子树

    2023年04月15日
    浏览(38)
  • Go语言数据结构(一)双向链表

    Go语言中list容器定义在\\\"container/list\\\"包中,实现了一个双向链表。本文第一部分总结源码包中的方法,第二部分展示使用list包的常见示例用法以及刷题时的用法。 食用指南:先看第二部分的常用示例用法然后再用到时在第一部分找对应的方法。 更多内容以及其他Go常用数据结

    2024年01月19日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包