lru和lfu算法的区别,简述cache中数据替换时较常使用的替换算法有哪几种?各有何特点？ _生活知识

LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。

（1）新加入数据插入到队列尾部（因为引用计数为1）；

（2）队列中的数据被访问后，引用计数增加，队列重新排序；

（3）当需要淘汰数据时，将已经排序的列表最后的数据块删除。

注意LFU和下一小节要介绍的LRU算法之间存在的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子，假设缓存大小为3，数据访问序列为set(2,2)、set(1,1)、get(2)、get(1)、get(2)、set(3,3)、set(4,4)，则在set(4,4)时对于LFU算法应该淘汰(3,3)，而LRU应该淘汰(1,1) 。LRU关键是看页面最后一次被使用到发生调度的时间长短，而LFU关键是看一定时间段内页面被使用的频率。

那么基于LFU算法的Cache设计应该支持的操作如。

n get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；

n set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最少访问的数据。

文章插图
简述cache中数据替换时较常使用的替换算法有哪几种?各有何特点？
Cache替换算法是影响代理缓存系统性能的一个重要因素，一个好的Cache替换算法可以产生较高的命中率。
目前已经提出的算法可以划分为以下三类：（1）传统替换算法及其直接演化，其代表算法有：①LRU（Least Recently Used）算法：将最近最少使用的内容替换出Cache；②LFU（Lease Frequently Used）算法：将访问次数最少的内容替换出Cache；③Pitkow/Recker[10]提出了一种替换算法：如果Cache中所有内容都是同一天被缓存的，则将最大的文档替换出Cache，否则按LRU算法进行替换。
（2）基于缓存内容关键特征的替换算法，其代表算法有：①Size[10]替换算法：将最大的内容替换出Cache；②LRU— MIN[11]替换算法：该算法力图使被替换的文档个数最少。
【lru和lfu算法的区别,简述cache中数据替换时较常使用的替换算法有哪几种?各有何特点？】设待缓存文档的大小为S，对Cache中缓存的大小至少是S的文档，根据LRU算法进行替换；如果没有大小至少为S的对象，则从大小至少为S/2的文档中按照LRU算法进行替换；③LRU—Threshold[11] 替换算法：和LRU算法一致，只是大小超过一定阈值的文档不能被缓存 ...