Cache replacement policies（缓存替换策略）/ LRU 和 LFU等算法
缓存是一个计算机思维，对于重复的计算，缓存其结果，下次再算这个任务的时候，不去真正的计算，而是直接返回结果，能加快处理速度。当然有些会随时间改变的东西，缓存会失效，得重新计算。
在计算中，缓存算法（通常也称为缓存替换算法或缓存替换策略）是优化指令或算法，计算机程序或硬件维护的结构可以利用这些指令或算法来管理存储在计算机上的信息缓存。高速缓存通过将最近或经常使用的数据项保存在比普通内存存储区更快或更便宜的存储位置中来提高性能。当缓存已满时，算法必须选择要丢弃的项目，以便为新项目腾出空间。
比如缓存空间只有2个，要缓存的数据有很多，1，2，3，4，5，那么当缓存空间满了，需要淘汰一个缓存出去，其中淘汰算法有 LRU，LFU，FIFO，SC二次机会，老化算法，时钟工作集算法等等。
Least recently used (LRU)
LRU：最近最少使用，把数据加入一个链表中，按访问时间排序，发生淘汰的时候，把访问时间最旧的淘汰掉。属于时间维度优化。
此算法需要跟踪何时使用了什么，如果要确保算法始终丢弃最近最少使用的商品，这将非常昂贵。该技术的一般实现方式需要为缓存行保留 “age bits (年龄位)” ，并根据年龄位跟踪“最近最少使用”的缓存行。在这样的实现中，每次使用高速缓存行时，所有其他高速缓存行的寿命都会改变。
比如有数据ABCDEDF，一旦将ABCD安装到具有***的块中（每个新Access的增量为1），并且当访问E时，它是未命中的，因此需要将其安装在其中一个块中。根据LRU算法，由于A具有最低的，因此E将替换A。
Most recently used (MRU)
与LRU相比，发生淘汰的时候，把访问时间最新的淘汰掉。对于随机访问模式和对大型数据集的重复扫描（有时称为循环访问模式），由于MRU缓存算法倾向于保留较旧的数据，因此它们比LRU命中率高。MRU算法在一项项目越旧，访问该项目的可能性越大的情况下最有用。
Pseudo-LRU (PLRU)
这种技术在使用CPU高速缓存中的英特尔486和在很多处理器的PowerPC家族，如飞思卡尔 的PowerPC G4通过使用苹果电脑。
对于具有较大关联性的CPU缓存（通常> 4种方式），LRU的实现成本变得过高。在许多CPU缓存中，几乎总是丢弃最近使用最少的一项的方案就足够了，因此许多CPU设计人员选择了PLRU算法，该算法每个缓存项只需要一位即可工作。与LRU相比，PLRU通常具有稍差的未命中率，稍稍更好的等待时间，比LRU消耗更少的功率以及更低的开销。
该算法的工作方式如下：考虑一个二叉搜索树（BST）为所讨论的项目。树的每个节点具有一位标志，该标志指示“向左查找伪LRU元素”或“向右查找伪LRU元素”。要查找伪LRU元素，请根据标志的值遍历树。要使用对项N的访问来更新树，请遍历树以找到N，并在遍历期间将节点标志设置为表示与所取方向相反的方向。
访问顺序为ABCDE。如果只看箭头，这里的原理很容易理解。当可以访问值时，说A，我们无法在缓存中找到它，然后从内存中加载它，并将其放置在箭头所指的块上，从上到下，并在放置该块时使箭头指向远离该块的底部和顶部。在上面的示例中，我们看到如何放置A，然后放置B，C和D。然后，当缓存已满时，E替换为A，因为那是箭头所指的时间。下次访问时，将替换保存B的块。
该算法可能是次优的，因为它是近似值。例如，在上图中具有A，C，B，D缓存行的情况下，如果访问模式为：C，B，D，A则在逐出时我们选择B而不是C。这是因为A和C在同一部分，访问A会将算法定向到不包含高速缓存行C的另一部分。
Least-frequently used (LFU)
LFU最近不经常使用，把数据加入到链表中，按频次排序 ，一个数据被访问过，把它的频次+1，发生淘汰的时候，把频次低的淘汰掉。属于统计维度优化。
比如有数据 A，A，A，B，B，C
缓存中有
当C加入的时候，得把后面的B淘汰，变成
区别：LRU 是得把 A 淘汰,应为A最早被访问。
显然，LRU对于循环出现的数据，缓存命中不高
比如，这样的数据，A，A，A，B，B，B，C，D，A，A，A，B，B，B.....
当走到C，D的时候，A，B会被淘汰掉，但是后面还有很多A，B
LFU对于交替出现的数据，缓存命中不高
比如，A，A，A，B，B，C，D，C，D，C，D，C，D，C，D，C，D......
由于前面被C加入把B淘汰，D加入把C淘汰，C加入把D淘汰，然而C,D才是最需要缓存的，A出现了3次，谁也淘汰不了它了。
Low inter-reference recency set (LIRS)
LIRS（低相互参照新近度集）是一种页面替换算法，其性能优于LRU和许多其他更新的替换算法。这是通过使用重用距离作为对访问页面进行动态排名以做出替换决定的指标来实现的。该算法由宋江和张晓东开发。
LIRS组织缓存页面和一些未缓存页面的元数据，并执行其替换操作，如下所述，这些操作也以示例在图中进行了说明。
在上图中，x表示在时间t访问一个块。
假设如果在时间1访问块A1，则由于这是第一个被访问的块，因此最近度将变为0，由于IRR预测将在时间3再次访问A1，因此IRR将为1。
自访问A4以来的时间2中，由于A4是最近访问的对象，并且IRR变为4，它将继续，因此A4的新近度将变为0，A1的新近度将变为1。
在时间10，LIRS算法将具有两组LIR集= {A1，A2}和HIR集= {A3，A4，A5}。现在在时间10，如果可以访问A4，则会发生未命中。LIRS算法由于其最大的新近性，现在将逐出A5而不是A2。
实现
leetcode上有两个题目:
- LRU：https://leetcode.com/problems/lru-cache/description/
- LFU：https://leetcode.com/problems/lfu-cache/description/
参考资料：