算法设计与分析课件 59 LRU缓存算法

算法设计与分析本节要点CONTENTSLRU缓存算法LRU缓存算法缓存是一种提高数据读取性能的技术，我们常用缓存提升数据查询速度，由于缓存容量有限，当缓存容量到达上限，又有新数据需要添加进缓存时，就需要删除部分数据腾出空间，这样新数据才可以添加进来。缓存数据不能随机删除，一般情况下根据某种算法策略删除（淘汰）缓存数据。常用缓存淘汰算法有最近最少使用算法（LRU）、最少使用算法（LFU）、先进先出算法（FIFO）等。LRU是LeastRecentlyUsed的缩写，该算法基于“局部性原理”，认为最近使用的数据是热门数据，下一次大概率会再次被使用，而最近很少被使用的数据，下一次大概率不再用到。当缓存容量已满时，优先淘汰最近很少使用的数据。LRU缓存淘汰算法在CPU缓存、数据库缓存和浏览器缓存中广泛应用。LRU缓存算法假设缓存容量capacity=5，最近访问的数据在缓存头部，LRU算法的简化模拟过程如下。LRU缓存算法存入1访问5存入8LRU算法有两个基本操作：访问get(key)：如果关键字key在缓存中，返回关键字的值，否则返回-1。将该数据移动到缓存头部。存入put(key,val)：如果关键字key已经存在，则变更其值为val，并将该数据移动到缓存头部。如果关键字不存在，若缓存已满，则先删除缓存尾部；将新数据放入缓存头部。LRU缓存算法（1）将数据移动到缓存头部，实际上分为两步：先删除该数据，再将该数据放入缓存头部。采用什么数据结构更好？（2）还有一个关键的问题，如何快速找到数据？LRU缓存算法双向链表和哈希表完美结合，形成一个新的数据结构—哈希链表。LRU缓存算法的核心数据结构是哈希链表。LRU缓存算法LRU缓存算法存入key=1，val=50假设缓存容量capacity=5，最近访问的数据在缓存头部。LRU缓存算法访问key=5LRU缓存算法存入key=8，val=25LRU缓存算法存入key=2，val=68如果采用封装好的数据结构，只需要几行代码就可以实现。例如，Python语言中的OrderedDict，Java语言中的LinkedHashMap，都是结合了哈希表与双向链表的数据结构。直接调用封装好的数据结构不符合考试或面试的要求，在此设计一个哈希链表实现LRU算法。LRU缓存算法哈希表可以采用C++STL中的unordered_map，其内部实现为哈希表，无序，增删改查的时间复杂度可达O(1)，最坏为O(n)。也可以采用C++STL中的map，其内部实现为红黑树，有序，增删改查的时间复杂度为O(logn)。双向链表采用自定义实现，包括添加、删除等基本操作。LRU缓存算法双向链表包括4种基本操作：添加p节点到链表头部，删除p节点，移动p节点到链表头部，删除尾节点。（1）添加p节点到链表头部LRU缓存算法（2）删除p节点LRU缓存算法（3）移动p节点到链表头部

先删除p节点，然后将p节点添加到链表的头部。（4）删除尾节点

先找到尾节点tail->pre，然后删除尾节点。LRU缓存算法LRU缓存包括3种基本操作：初始化，访问，存入。（1）初始化初始化缓存的容量为参数_capacity，实际数据量size=0，双向链表的头节点和尾节点不存储数据。LRU缓存算法（2）访问如果关键字key在缓存中，返回关键字的值，否则返回-1。将该数据移动到链表头部。（3）存入如果关键字key已经存在，则变更其值为val，并将该数据移动到链表头部。如果关键字不存在，判断如果缓存已满，则先删除缓存尾部；将新数据放入缓存头部。LRU缓存算法LRU缓存算法算法实现LRU缓存算法算法分析时间复杂度：在哈希表中执行查找和添加操作的时间复杂度为O(1)，双向链表