人工智能视频教程 ai vip技术 人工智能数学基础 爬虫 python机器学习 tensorflow深度学习 20+个企业AI实战项目

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 51|回复: 0

[学习笔记] 06、链表(上):如何实现LRU缓存淘汰算法?

[复制链接]

862

主题

1074

帖子

1万

积分

管理员

Rank: 10Rank: 10Rank: 10

积分
10261
QQ
发表于 2019-10-8 22:53:45 | 显示全部楼层 |阅读模式
06、链表(上):如何实现LRU缓存淘汰算法?


缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常
见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要
缓存淘汰策略来决定。常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使
用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)



单链表、双向链表和循环链表

在进行数组的插入、删除操作时,为了保持内存数据的连续性,需要做大量的数据搬
移,所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据,我们并不需要为了保持内存
的连续性而搬移结点,因为链表的存储空间本身就不是连续的。所以,在链表中插入和删除一个
数据是非常快速的。
但是,有利就有弊。链表要想随机访问第 k 个元素,就没有数组那么高效了。因为链表中的数据
并非连续存储的,所以无法像数组那样,根据首地址和下标,通过寻址公式就能直接计算出对应
的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点
循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结
点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结
点指针是指向链表的头结点
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所
以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费
存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性


如何基于链表实现 LRU 缓存淘汰算法?

我的思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有
一个新的数据被访问时,我们从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的
位置删除,然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此结点直接插入到链表的头部;
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
这样我们就用链表实现了一个 LRU 缓存



设计思想
时空替换思想:“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对
较高,时间复杂度小相对较低的算法和数据结构,缓存就是空间换时间的例子。如果内存比较
紧缺,比如代码跑在手机或者单片机上,这时,就要反过来用时间换空间的思路。


01.png
02.png
03.png
04.png
05.png
06.png
让天下人人学会人工智能!人工智能的前景一片大好!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|人工智能工程师的摇篮 ( 湘ICP备18018285号-1 )

GMT+8, 2019-10-23 07:37 , Processed in 0.196142 second(s), 22 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表