对于web开发而言,缓存必不可少,也是提高性能最常用的方式,无论是浏览器缓存(如果是chrome浏览器,可以通过chrome:://缓存查看),还是服务端的缓存(通过memcached或者复述等内存数据库)。缓存不仅可以加速用户的访问,同时也可以降低服务器的负载和压力。那么,了解常见的缓存淘汰算法的策略和原理就显得特别重要。
常见的缓存算法
LRU(最近最少使用)最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。
<李>LFU(最常用)最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。
<李>FIFO(先出拳头)先进先出,如果一个数据最先进入缓存中,则应该最早淘汰掉。
LRU缓存
像浏览器的缓存策略,memcached的缓存策略都是使用LRU这个算法,LRU算法会将近期最不会访问的数据淘汰掉.LRU如此流行的原因是实现比较简单,而且对于实际问题也很实用,良好的运行时性能,命中率较高。下面谈谈如何实现LRU缓存:
新数据插入到链表头部
<李>每当缓存命中(即缓存数据被访问),则将数据移到链表头部
<李>当链表满的时候,将链表尾部的数据丢弃
LRU缓存具备的操作:
设置(键,值):如果关键在hashmap中存在,则先重置对应的价值值,然后获取对应的节点曲率,将坏蛋节点从链表删除,并移动到链表的头部;若果关键在hashmap不存在,则新建一个节点,并将节点放到链表的头部。当缓存中存满的时候,将链表最后一个节点删除即可。
<李>(关键):如果关键在hashmap中存在,则把对应的节点放到链表头部,并返回对应的价值值;如果不存在,则返回1 .
LRU的c++实现
LRU实现采用双向链表+地图来进行实现。这里采用双向链表的原因是:如果采用普通的单链表,则删除节点的时候需要从表头开始遍历查找,效率为O (n),采用双向链表可以直接改变节点的前驱的指针指向进行删除达到O(1)的效率。使用地图来保存节点的键,值值便于能在O (logN)的时间查找元素,对应得到操作。
双链表节点的定义:
struct CacheNode {int 才能;关键;,,,,,,//,键
int 才能;价值;,,,,//值
CacheNode *前,才能,*下,,,//,节点的前驱,后继指针
CacheNode才能(int k, int v),:,关键(k),价值(v), pre (NULL),下一个(NULL), {}
}; 对于LRUCache这个类而言,构造函数需要指定容量大小
LRUCache (int 能力)
{
时间=size 才能;能力;,,,,,,//,容量
head 才能=,零,,,,,,,,,,,//,链表头指针
tail 才能=,零,,,,,,,,,,,//,链表尾指针} 双链表的节点删除操作:
void 删除(CacheNode *节点){if 才能;(node →, pre !=, NULL)
{才能
,,,node →, pre →, next =, node →,下一个;
,,},其他
{才能
,,,head =, node →,下一个;
,,},if (node →, next !=, NULL)
{才能
,,,node →, next →, pre =, node →,前;
,,},其他
{才能
,,,tail =, node →,前;
,,}
} 将节点插入到头部的操作:
void setHead (CacheNode *节点){
,,node →next =,头;
,,node →pre =,零;,,if (head !=, NULL)
{才能
,,,head →, pre =,节点;
,,}
时间=head 才能;节点;,,if (==tail 空)
{才能
,,,tail =,头;
,,}
} get(键)操作的实现比较简单,直接通过判断地图是否含有键值即可,如果查找到键,则返回对应的价值,否则返回1;
int 得到(int 键){map<才能,int, CacheNode *祝辞::iterator it =, mp.find(关键);,,if (it !=, mp.end ())
{才能
,,,CacheNode * node =, it →,第二;
,,,删除(节点);
,,,setHead(节点),,,,,return node →,价值;
,,},其他
{才能,,,return 1;
,,}
} 设置(键值)操作需要分情况判断。如果当前的键值对应的节点已经存在,则将这个节点取出来,并且删除节点所处的原有的位置,并在头部插入该节点,如果节点不存在节点中,这个时候需要在链表的头部插入新节点,插入新节点可能导致容量溢出,如果出现溢出的情况,则需要删除链表尾部的节点。
