LRU算法–缓存淘汰算法

本文介绍 LRU 算法的含义，算法思想，算法分析，案例及应用等。

1. 什么是 LRU

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也很高”，反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”，两种理解是一样的；常用于页面置换算法，是为虚拟页式存储管理服务的。

2. LRU 算法思想

达到这样一种情形的算法是最理想的：每次调换出的页面是所有内存页面中最迟将被使用的；这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。
为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。

3. LRU 算法 — 算法分析

命中率：
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。
复杂度：
实现起来较为简单。
存储成本：
几乎没有空间上浪费。
代价：
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

4. LRU 算法 — 案例

假定缓存容量为4，顺序访问数据项：4，3，4，1，5，2，4，1，2；过程如下：
4 调入内存: 4
3 调入内存: 3 4
4 调入内存: 4 3 （命中 4，更新次序）
1 调入内存: 1 4 3
5 调入内存: 5 1 4 3
2 调入内存: 2 5 1 4 （3 最久未使用，淘汰3）
4 调入内存: 4 2 5 1 （命中 4，更新次序）
1 调入内存: 1 4 2 5 （命中 1，更新次序）
2 调入内存: 2 1 4 5 （命中 2，更新次序）

5. LRU 算法 — 应用

LRU 算法也可以用于一些实际的应用中，如你要做一个浏览器，或类似于淘宝客户端的应用的就要用到这个原理。浏览器在浏览网页的时候会把下载的图片临时保存在本机的一个文件夹里，下次再访问时，直接从本机临时文件夹里读取。但保存图片的临时文件夹是有一定容量限制的，如果你浏览的网页太多，就会有一些你最不常使用的图像删除掉，只保留最近最久使用的一些图片。这时就可以用到 LRU 算法了，这时上面算法里的这个特殊的栈就不是保存页面的序号了，而是每个图片的序号或大小。

最后更新： 2017年11月19日 20:17

原始链接： http://blog.minhow.com/articles/algorithm/lru-algorithm/

赏