链表(上):如何实现LRU缓存淘汰算法?
链表(上):如何实现LRU缓存淘汰算法?
我们都知道缓存可以提高数据读取的性能,但是缓存的大小有限,当缓存被填满时,哪些数据应该被清理出去?哪些数据应该被保留?这就需要缓存淘汰策略来决定。
常见的策略有三种(基本上见名知意了):
- 先进先出策略 FIFO(First In,First Out)
- 最少使用策略 LFU (Least Frequently Used)
- 最近最少使用策略 LRU (Least Recently Used)
那么如何使用 链表 来实现LRU缓存淘汰算法呢?
1. 五花八门的链表结构
先来看看数组与链表的区别。
底层的存储结构的区别
image注意数组需要的是一块 连续的内存空间
,比如说数组需要 100m 的存储空间,而内存中的闲置空间可以达到 100m 但却不是连续的,那么就很尴尬了,此时数组申请内存会失败。
而链表并不需要一块连续的内存空间,它通过 指针
将一组 零散的内存块
串联起来使用,上述情况下使用链表就不会有问题。
常见的三种链表:单链表
循环链表
双向链表
2. 单链表
通过指针将一组零散的内存块串联在一起就成为了链表。其中,内存块就被称为链表的 结点
。为了将所有的结点串起来,每个链表的结点除了存储数据外,还要记录链上的下一个结点的地址。将这个记录下一个结点地址的指针叫做 后继指针 next
。
- 头结点:记录链表的基地址,通过它我们可以遍历得到整条链表
- 尾结点:后继指针指向一个 空地址 NULL ,表示这是链表上最后一个结点
链表也支持数据的查找、插入和删除操作。
在执行数组的插入、删除操作时,为了保持内存数据的连续性,需要做大量的数据搬移,所以时间复杂度为:○(n)
在链表中插入或删除一个数据,并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的。(所以才会说链表的插入或删除一个数据是非常快速的)
可以自己画一下删除是什么样的。
利弊皆存。链表要随机访问第 k 个元素,是没有数组那么高效的,因为 链表中的数据并非连续存储,所以无法像数组那样根据首地址和下标,通过寻址公式直接计算出对于元素的内存地址,而是需要根据指针一个结点一个结点地依次遍历,知道找到相应的结点。
因为单链表只有后继指针,都是一个接着一个的,也就是前一个能找到后一个,只有这么一个一个找下去,才能找到我们要的第 k 个值,所以链表的随机访问性能没有数组好,需要 ○(n) 复杂度。
3. 循环链表
循环链表是一种特殊的单链表。 它与单链表唯一的区别就在于,它的尾结点指针指向了它的头结点,如下图:
与单链表相比 循环链表 的优点是从链尾到链头比较方便,当要处理的数据具有环形结构特点时,就特别适合采用循环链表。比如注明的 维基百科:约瑟夫问题 百度百科:约瑟夫问题
4. 实际开发中最常用的链表:双向链表
双向链表,支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点。
image从上图可以看到,双向链表需要两个空间来存储后继结点和前驱结点的地址。
所以,存储同样多的数据,双向链表要比单链表占用更多的内存空间。可因为双向链表支持双向遍历,提高了其灵活性。从结构上来看,双向链表可以支持 ○(1) 时间复杂度的情况下找到前驱结点(根据前驱指针 prev),这样的话,在某些情况下的插入、删除都会比单链表简单、高效。
删除操作
- 删除结点中
值等于某个给定值
的结点;① - 删除给定指针指向的结点;②
对于 ① ,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个一次遍历对比。尽管单词的删除操作的时间复杂度是 ○(1),但是遍历查找才是主要的耗时点,对应的时间复杂度为 ○(n),(时间复杂度分析中的加法法则)总时间复杂度为 ○(n)
对于 ② ,已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表并不支持直接后去前驱结点,所以为了找到前驱结点,还是要从头开始遍历链表,知道 p 的 next 结点是 q ,说明 p 是 q 的前驱结点。
但是对于双向链表来说,就不需要像单链表那样遍历了,因为双向链表中的结点已经保存了前驱结点的指针 prev ,所以单链表删除操作需要 ○(n),但是双向链表只需要在 ○(1) 的时间复杂度内就搞定了。
插入操作
同样的双向链表的插入操作需要 ○(1) 而单链表需要 ○(n)。
5. 双向链表比单链表应用更加广泛的原因
用空间换时间
的设计思想。当内存空间充足的时候,可以选择空间复杂度较高的,但时间复杂度相对很低的算法和数据结构来追求代码的执行速度。相反,如果内存空间比较紧缺,就要反过来使用 时间换空间
的设计思路。
双向链表比单链表每个结点多存储了一个 prev ,虽然所需存储空间增大了,但是效率可以提高很多。java 中的 LinkedHashMap 容器,其实现原理中就用到了 双向链表 这种数据结构。
6. 缓存就是一种以时间换空间的典型案例
如果把数据存储到硬盘上,会比较省农村,但是每次查找数据都要询问一次硬盘,会比较慢。但如果我们通过缓存技术,事先将数据加载在内存中,虽然会比较耗费内存空间,但每次查询的书读就大大提高了。
将 循环链表 和 双向链表 合起来就是 双向循环链表
:
7. 链表 VS 数组性能大比拼
数组和链表是两种截然不同的内存组织方式,因为内存存储的问题,他们插入、删除、随机访问操作的时间复杂度正好相反:
image
注意: 在实际的软件开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据!
数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。
数组的缺点是大小固定,一经声明就要占用整块连续内存空间,如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致 内存不足
。而声明的数组过小,则不够用时只能再申请一个更大的内存空间,把原数组拷贝过去,非常费事。
链表本身没有大小的限制,支持动态扩容,这也是它与数组最大的区别。
8. 如何基于链表实现 LRU 缓存淘汰算法?
思路:维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的,当有一个新数据被访问时,我们从链表头开始顺序遍历链表。
- 如果此数据之前就已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。(表示这条数据是最近使用的)
- 如果此数据没有被缓存在链表中,又可以分为两种情况
- 如果缓存未满,则将此数据直接插入到链表的头部。
- 如果缓存已满,则删除链表的尾结点,将新的数据插入链表的头部。
计算一下时间复杂度:因为不管存不存在,都是一定要遍历一次链表的,所以时间复杂度为 ○(n)
可以使用散列表继续优化,以后会学到的
9. 如何使用数组实现 LRU 缓存淘汰策略?
- 遍历数组中是否含有该数据
- 有:假设该数据所在下标为 x ,则将数组 从 0~(x-1) 的数据右移一位,将该数据放在 下标=0 的位置
- 没有:则将数组 从 0~(n-1) 右移一位,将该元素放在 下标=0 的位置
- 数组的初始容量 n 就是该缓存的大小
计算一下时间复杂度:
- 最好时间复杂度:有该数据且该数据所在下标正好是 0:○(1)
- 最坏时间复杂度:无该数据或该数据的下标正好是 n:○(n)
- 平均时间复杂度: image
所以时间复杂度为:○(n)
10. 课后思考
如何判断一个字符串是否是回文字符串?
(回文串:正读反读都是一个意思:level,noon,12321等等
)
思路:假设字符串长度为n,循环 n/2 次,i 初始为 0,每次判断 str[i] 与 str[n-i-1] 是否相等即可。
时间复杂度:○(n)
如果字符串是通过 单链表
来存储的,那该如何来判断是一个回文串呢?
我的思考:
将该链表遍历取值,反向取,从尾结点取值取到首结点。(需要双层循环,复杂度为 ○(n²))
每次取到的值都放在一个新的链表中,按正常的先后顺序存放即可。
判断原链表的前一半与新链表的前一半是否都相等(复杂度为 ○(n))
最后时间复杂度为 ○(n²)
看该文章下面的评论学习到的解决方式:
- 通过快慢指针定位中间节点
- 从中间节点对后半部分逆序
- 前后半部分比较,判断是否为回文
- 后半部分逆序复原
本篇篇幅过长,上述问题解析在下一篇中。