|
06、链表(上):如何实现LRU缓存淘汰算法?
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常
见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要
缓存淘汰策略来决定。常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使
用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)
单链表、双向链表和循环链表
在进行数组的插入、删除操作时,为了保持内存数据的连续性,需要做大量的数据搬
移,所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据,我们并不需要为了保持内存
的连续性而搬移结点,因为链表的存储空间本身就不是连续的。所以,在链表中插入和删除一个
数据是非常快速的。
但是,有利就有弊。链表要想随机访问第 k 个元素,就没有数组那么高效了。因为链表中的数据
并非连续存储的,所以无法像数组那样,根据首地址和下标,通过寻址公式就能直接计算出对应
的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点
循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结
点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结
点指针是指向链表的头结点
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所
以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费
存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性
如何基于链表实现 LRU 缓存淘汰算法?
我的思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有
一个新的数据被访问时,我们从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的
位置删除,然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此结点直接插入到链表的头部;
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
这样我们就用链表实现了一个 LRU 缓存
设计思想
时空替换思想:“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对
较高,时间复杂度小相对较低的算法和数据结构,缓存就是空间换时间的例子。如果内存比较
紧缺,比如代码跑在手机或者单片机上,这时,就要反过来用时间换空间的思路。
|
|