随笔- 221&
&&&&&&&&&&&
1. FIFO -- 先进先出
如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。
利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。
2. LFU -- 最近最少使用
基于&如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小&的思路。
LFU是基于访问次数的。
为了能够淘汰最少使用的数据，LFU算法最简单的一种设计思路就是利用一个数组存储数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。
　　另外还有一种实现思路就是利用小顶堆+hashmap，小顶堆插入、删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效。
3. LRU -- 最近最久未使用
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
（1）用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
思路简单，但是需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
（2）利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部；如果不存在，则新建一个节点，放到链表头部。若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
在已知要删除的节点的情况下，如何在O(1)时间复杂度内删除节点？
假如要删除的节点是cur，通过cur可以知道cur节点的后继节点curNext，如果交换cur节点和curNext节点的数据域，然后删除curNext节点（curNext节点是很好删除地），此时便在O(1)时间复杂度内完成了cur节点的删除。
如何使得删除末尾节点的复杂度也在O(1)？
利用双向链表，并提供head指针和tail指针，这样一来，所有的操作都是O(1)时间复杂度。
参考实现：
#include &iostream&
#include &map&
#include &algorithm&
using namespace
struct Node
class LRUCache{
map&int,Node *&
Node *cacheH
Node *cacheT
LRUCache(int capacity) {
cacheHead = NULL;
cacheTail = NULL;
count = 0;
int get(int key) {
if(cacheHead==NULL)
return -1;
map&int,Node *&::iterator it=mp.find(key);
if(it==mp.end())
//如果在Cache中不存在该key， 则返回-1
return -1;
Node *p = it-&
pushFront(p);
//将节点p置于链表头部
return cacheHead-&
void set(int key, int value) {
if(cacheHead==NULL)
//如果链表为空，直接放在链表头部
cacheHead = (Node *)malloc(sizeof(Node));
cacheHead-&key =
cacheHead-&value =
cacheHead-&pre = NULL;
cacheHead-&next = NULL;
mp[key] = cacheH
cacheTail = cacheH
//否则，在map中查找
map&int,Node *&::iterator it=mp.find(key);
if(it==mp.end())
//没有命中
if(count == size)
//cache满了
if(cacheHead==cacheTail&&cacheHead!=NULL)
//只有一个节点
mp.erase(cacheHead-&key);
cacheHead-&key =
cacheHead-&value =
mp[key] = cacheH
Node * p =cacheT
cacheTail-&pre-&next = cacheTail-&
cacheTail = cacheTail-&
mp.erase(p-&key);
p-&value =
p-&next = cacheH
p-&pre = cacheHead-&
cacheHead-&pre =
cacheHead =
mp[cacheHead-&key] = cacheH
Node * p = (Node *)malloc(sizeof(Node));
p-&value =
p-&next = cacheH
p-&pre = NULL;
cacheHead-&pre =
cacheHead =
mp[cacheHead-&key] = cacheH
Node *p = it-&
p-&value =
pushFront(p);
void pushFront(Node *cur)
//双向链表删除节点,并将节点移动链表头部，O(1)
if(count==1)
if(cur==cacheHead)
if(cur==cacheTail)
cacheTail = cur-&
cur-&pre-&next = cur-&
//删除节点
if(cur-&next!=NULL)
cur-&next-&pre = cur-&
cur-&next = cacheH
cur-&pre = NULL;
cacheHead-&pre =
cacheHead =
void printCache(){
Node *p = cacheH
while(p!=NULL)
cout&&p-&key&&" ";
int main(void)
LRUCache cache(3);
cache.set(1,1);
//cache.printCache();
cache.set(2,2);
//cache.printCache();
cache.set(3,3);
cache.printCache();
cache.set(4,4);
cache.printCache();
cout&&cache.get(4)&&
cache.printCache();
cout&&cache.get(3)&&
cache.printCache();
cout&&cache.get(2)&&
cache.printCache();
cout&&cache.get(1)&&
cache.printCache();
cache.set(5,5);
cache.printCache();
cout&&cache.get(1)&&
cout&&cache.get(2)&&
cout&&cache.get(3)&&
cout&&cache.get(4)&&
cout&&cache.get(5)&&
（2）用stl的list实现双向链表
#include &iostream&
#include &map&
#include &algorithm&
#include &list&
using namespace
struct Node
class LRUCache{
list&Node& cacheL
map&int, list&Node&::iterator &
LRUCache(int capacity) {
int get(int key) {
map&int, list&Node&::iterator &::iterator it = mp.find(key);
if(it==mp.end())
//没有命中
return -1;
//在cache中命中了
list&Node&::iterator listIt = mp[key];
newNode.key =
newNode.value = listIt-&
cacheList.erase(listIt);
//先删除命中的节点
cacheList.push_front(newNode);
//将命中的节点放到链表头部
mp[key] = cacheList.begin();
return cacheList.begin()-&
void set(int key, int value) {
map&int, list&Node&::iterator &::iterator it = mp.find(key);
if(it==mp.end())
//没有命中
if(cacheList.size()==maxSize)
//cache满了
mp.erase(cacheList.back().key);
cacheList.pop_back();
newNode.key =
newNode.value =
cacheList.push_front(newNode);
mp[key] = cacheList.begin();
list&Node&::iterator listIt = mp[key];
cacheList.erase(listIt);
//先删除命中的节点
newNode.key =
newNode.value =
cacheList.push_front(newNode);
//将命中的节点放到链表头部
mp[key] = cacheList.begin();
int main(void)
LRUCache cache(3);
cache.set(1,1);
cache.set(2,2);
cache.set(3,3);
cache.set(4,4);
cout&&cache.get(4)&&
cout&&cache.get(3)&&
cout&&cache.get(2)&&
cout&&cache.get(1)&&
cache.set(5,5);
cout&&cache.get(1)&&
cout&&cache.get(2)&&
cout&&cache.get(3)&&
cout&&cache.get(4)&&
cout&&cache.get(5)&&
阅读(...) 评论()缓存淘汰算法系列之2----LFU类
我的图书馆
缓存淘汰算法系列之2----LFU类
1.1.1.&原理
LFU（Least&Frequently&Used）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
1.1.2.&实现
LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。
具体实现如下：
1.&新加入数据插入到队列尾部（因为引用计数为1）；
2.&队列中的数据被访问后，引用计数增加，队列重新排序；
3.&当需要淘汰数据时，将已经排序的列表最后的数据块删除。
1.1.3.&分析
一般情况下，LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用。
需要维护一个队列记录所有数据的访问记录，每个数据都需要维护引用计数。
需要记录所有数据的访问记录，内存消耗较高；需要基于引用计数排序，性能消耗较高。
1.2.1.&原理
基于LFU的改进算法，其核心思想是“只淘汰访问过一次的数据”。
1.2.2.&实现
LFU*数据缓存实现和LFU一样，不同的地方在于淘汰数据时，LFU*只淘汰引用计数为1的数据，且如果所有引用计数为1的数据大小之和都没有新加入的数据那么大，则不淘汰数据，新的数据也不缓存。
1.2.3.&分析
和LFU类似，但由于其不淘汰引用计数大于1的数据，则一旦访问模式改变，LFU*无法缓存新的数据，因此这个算法的应用场景比较有限。
需要维护一个队列，记录引用计数为1的数据。
相比LFU要低很多，不需要维护所有数据的历史访问记录，只需要维护引用次数为1的数据，也不需要排序。
1.3.&LFU-Aging
1.3.1.&原理
基于LFU的改进算法，其核心思想是“除了访问次数外，还要考虑访问时间”。这样做的主要原因是解决LFU缓存污染的问题。
1.3.2.&实现
虽然LFU-Aging考虑时间因素，但其算法并不直接记录数据的访问时间，而是通过平均引用计数来标识时间。
LFU-Aging在LFU的基础上，增加了一个最大平均引用计数。当当前缓存中的数据“引用计数平均值”达到或者超过“最大平均引用计数”时，则将所有数据的引用计数都减少。减少的方法有多种，可以直接减为原来的一半，也可以减去固定的值等。
1.3.3.&分析
LFU-Aging的效率和LFU类似，当访问模式改变时，LFU-Aging能够更快的适用新的数据访问模式，效率要高。
在LFU的基础上增加平均引用次数判断和处理。
和LFU类似，当平均引用次数超过指定阈值（Aging）后，需要遍历访问列表。
1.4.&LFU*-Aging
1.4.1.&原理
LFU*和LFU-Aging的合成体。
1.4.2.&实现
1.4.3.&分析
和LFU-Aging类似。
比LFU-Aging简单一些，不需要基于引用计数排序。
比LFU-Aging少一些，不需要基于引用计数排序。
1.5.&Window-LFU
1.5.1.&原理
Windows-LFU是LFU的一个改进版，差别在于Window-LFU并不记录所有数据的访问历史，而只是记录过去一段时间内的访问历史，这就是Window的由来，基于这个原因，传统的LFU又被称为“Perfect-LFU”。
1.5.2.&实现
与LFU的实现基本相同，差别在于不需要记录所有数据的历史访问数据，而只记录过去一段时间内的访问历史。具体实现如下：
1）记录了过去W个访问记录；
2）需要淘汰时，将W个访问记录按照LFU规则排序淘汰
举例如下：
假设历史访问记录长度设为9，缓存大小为3，图中不同颜色代表针对不同数据块的访问，同一颜色代表针对同一数据的多次访问。
样例1：***访问3次，蓝色和橘色都是两次，橘色更新，因此缓存***、橘色、蓝色三个数据块
样例2：绿色访问3次，蓝色两次，暗红两次，蓝色更新，因此缓存绿色、蓝色、暗红三个数据块
1.5.3.&分析
Window-LFU的命中率和LFU类似，但Window-LFU会根据数据的访问模式而变化，能够更快的适应新的数据访问模式，”缓存污染“问题不严重。
需要维护一个队列，记录数据的访问流历史；需要排序。
Window-LFU只记录一部分的访问历史记录，不需要记录所有的数据访问历史，因此内存消耗和排序消耗都比LFU要低。
1.6.&LFU类算法对比
由于不同的访问模型导致命中率变化较大，此处对比仅基于理论定性分析，不做定量分析。
Window-LFU/LFU-Aging&&&LFU*-Aging&&&LFU&&&LFU*
LFU-Aging&&&LFU&&&LFU*-Aging&&&Window-LFU&&&LFU*
LFU-Aging&&&LFU&&&Window-LFU&&&LFU*-Aging&&&&LFU*
TA的最新馆藏[转]&LRU LFU FIFO - 简书
LRU LFU FIFO
LRU全称是Least Recently Used，即最近最久未使用的意思。如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。而用什么数据结构来实现LRU算法呢？
可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
那么有没有更好的实现办法呢？
那就是利用链表移动访问时间的数据顺序和hashmap查询是否是新数据项。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。参考
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。注意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)。
为了能够淘汰最少使用的数据，因此LFU算法最简单的一种设计思路就是 利用一个数组存储 数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。参考
FIFO（First in First out），先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。在FIFO Cache设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。
那么利用什么数据结构来实现呢？
下面提供一种实现思路：利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。参考