LRU、LFU、FIFO、ARC、MRU

概述

  • LRU (Least recently used) 最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面。

  • LFU (Least frequently used) 最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小,LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页。

  • FIFO (Fist in first out) 先进先出, 如果一个数据最先进入缓存中,则应该最早淘汰掉。

  • ARC 自适应缓存替换算法,这个缓存算法同时跟踪记录LFU和LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

  • MRU 这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久,越容易被访问的情况。

LRU

这个是目前常见的缓存方式,浏览器和memcached的缓存策略均为此项,LRU主要的方式如下图所示:

file

一般采用的是双向链表+Hash的方式,主要基于以下几个方面考虑:

  • 采用普通的单链表,则删除节点的时候需要从表头开始遍历查找,效率为O(n),采用双向链表可以直接改变节点的前驱的指针指向进行删除达到O(1)的效率

  • 使用Map来保存节点的key、value值便于能在O(logN)的时间查找元素

#include "stdio.h"
#include "stdlib.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int status;
typedef int ElemType;

typedef struct {
    ElemType data;
    int nums;
}Node;

typedef struct 
{
    Node *base;
    int length;
    int listsize;
}Cache;

status InitCache(Cache &L);
status ListInsert_Sq(Cache &L , int i, ElemType e);
status Push(Cache &L ,  ElemType e);
status Pop(Cache &L);
status EQ(ElemType a,ElemType b);
status LT(ElemType a,ElemType b);
status ShowCache(Cache L);
int LocateCache_nums(Cache L,ElemType e);
int LocateCache_data(Cache L,ElemType e);
status start(Cache &L , ElemType e);

int main(int argc, char const *argv[])
{
    Cache L;
    int arr[] = { 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};
    int count;
    int i;
    count = sizeof(arr)/sizeof(int);
    InitCache(L);
    for(i=0;i<count;i++){
        printf("-----%d\n",i+1);
        start(L,arr[i]);
        ShowCache(L);
    }
    return 0;
}

status InitCache(Cache &L){
    if(!L.base) exit(OVERFLOW);
    printf("please input cache nums:");
    scanf("%d",&L.listsize);
    L.base = (Node*)malloc(sizeof(Node)*L.listsize);
    L.length = 0;
    return OK;
}
/**
 * 1.先查找是否在缓存里面
 * 2.在找出位置,返回位置数
 * 3.然后查出的相同次数缓存的第一个位置
 * 4.把缓存调到该位置的前一个。:1.取出该元素,2该元素的原来位置到第一个元素的位置之间元素向后移一位,插入元素到第一个位置
 * 5.不在则判断是否已满
 * 6.不满直接插入元素到最后位置,否则删除最后元素,然后插入元素
 * @param  L [description]
 * @param  e [description]
 * @return   [description]
 */
status start(Cache &L , ElemType e){
    int site,nums,firstElem,temp;
    Node p;
    // 查找有该元素
    if((site=LocateCache_data(L,e))!=-1){
        nums = L.base[site].nums;
        firstElem = LocateCache_nums(L,nums);
        printf("%d %d\n",nums,firstElem );
        p = L.base[site];
        // 把顺序表的结点一个个向后移一位
        for(temp=firstElem;temp<site;temp++){
            L.base[temp+1] = L.base[temp];
            printf("fuckfuck\n");
        }
        // 顺序表该增加调用的改为第一个
        L.base[firstElem] = p;
        L.base[firstElem].nums++;
    }else{
        // 没有该元素,直接删除最后一位,增加新的元素
        if(L.length==L.listsize)
            Pop(L);
        Push(L,e);
    }
}

// 查找第一个出现的对应元素,折半查找元素(根据使用次数)
int LocateCache_nums(Cache L,int nums){
    int low,high,mid;
    low = L.length-1;
    high = 0;
    // printf("%d\n", mid);exit(-1);
    while(low >= high){
        mid = (high+low)/2;
        if(EQ(L.base[mid].nums,nums)){
            // 如果出现了相同的次数,查找第一个出现的次数
            while(mid!=0){
                // 查找前一个元素是否符合次数
                if(!EQ(L.base[--mid].nums,nums)){
                    mid++;
                    break;
                }
            }
            return mid;
        }else {
            if(LT(L.base[mid].nums,nums)) low = mid-1;
            else high = mid+1;
        }
    }
    return -1;
}

// 查找元素
int LocateCache_data(Cache L,ElemType e){
    int i=0;
    // 设置哨兵
    L.base[L.length].data = e;
    for(;!EQ(L.base[i].data,e);i++);
    if(i==L.length) return -1;
    else return i;
}

// 在尾部插入元素,调用次数为1
status Push(Cache &L , ElemType e){
    Node *p;
    if(L.length>=L.listsize) return ERROR;
    p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->nums = 1;
    L.base[L.length] = *p;
    L.length++;
}

// 删除尾部元素
status Pop(Cache &L){
    if(L.length<1) return ERROR;
    L.length--;
}

status ShowCache(Cache L){
    int i=0;
    while(i<L.length){
        printf("cache Id nums:%d %d\n",L.base[i].data,L.base[i].nums);
        i++;
    }   
}

status EQ(ElemType a,ElemType b){
    return a==b?OK:ERROR;
}
status LT(ElemType a,ElemType b){
    return a<b?OK:ERROR;
}

LFU

LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。一般实现有以下几步。

  • 新加入数据插入到队列尾部(因为引用计数为1)
  • 队列中的数据被访问后,引用计数增加,队列重新排序
  • 当需要淘汰数据时,将已经排序的列表最后的数据块删除

由于每个数据都需要维护引用计数,同时需要针对引用计数排序,所以性能消耗比较高。

#include "stdio.h"
#include "stdlib.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int status;
typedef int ElemType;

typedef struct {
    ElemType data;
    int nums;
}Node;

typedef struct 
{
    Node *base;
    int length;
    int listsize;
}Cache;

status InitCache(Cache &L);
status ListInsert_Sq(Cache &L , int i, ElemType e);
status Push(Cache &L ,  ElemType e);
status Pop(Cache &L);
status EQ(ElemType a,ElemType b);
status LT(ElemType a,ElemType b);
status ShowCache(Cache L);
int LocateCache_nums(Cache L,ElemType e);
int LocateCache_data(Cache L,ElemType e);
status start(Cache &L , ElemType e);

int main(int argc, char const *argv[])
{
    Cache L;
    int arr[] = { 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};
    int count;
    int i;
    count = sizeof(arr)/sizeof(int);
    InitCache(L);
    for(i=0;i<count;i++){
        printf("-----%d\n",i+1);
        start(L,arr[i]);
        ShowCache(L);
    }
    return 0;
}

status InitCache(Cache &L){
    if(!L.base) exit(OVERFLOW);
    printf("please input cache nums:");
    scanf("%d",&L.listsize);
    L.base = (Node*)malloc(sizeof(Node)*L.listsize);
    L.length = 0;
    return OK;
}
/**
 * 1.先查找是否在缓存里面
 * 2.在找出位置,返回位置数
 * 3.然后查出的相同次数缓存的第一个位置
 * 4.把缓存调到该位置的前一个。:1.取出该元素,2该元素的原来位置到第一个元素的位置之间元素向后移一位,插入元素到第一个位置
 * 5.不在则判断是否已满
 * 6.不满直接插入元素到最后位置,否则删除最后元素,然后插入元素
 * @param  L [description]
 * @param  e [description]
 * @return   [description]
 */
status start(Cache &L , ElemType e){
    int site,nums,firstElem,temp;
    Node p;
    // 查找有该元素
    if((site=LocateCache_data(L,e))!=-1){
        nums = L.base[site].nums;
        firstElem = LocateCache_nums(L,nums);
        printf("%d %d\n",nums,firstElem );
        p = L.base[site];
        // 把顺序表的结点一个个向后移一位
        for(temp=firstElem;temp<site;temp++){
            L.base[temp+1] = L.base[temp];
            printf("fuckfuck\n");
        }
        // 顺序表该增加调用的改为第一个
        L.base[firstElem] = p;
        L.base[firstElem].nums++;
    }else{
        // 没有该元素,直接删除最后一位,增加新的元素
        if(L.length==L.listsize)
            Pop(L);
        Push(L,e);
    }
}

// 查找第一个出现的对应元素,折半查找元素(根据使用次数)
int LocateCache_nums(Cache L,int nums){
    int low,high,mid;
    low = L.length-1;
    high = 0;
    // printf("%d\n", mid);exit(-1);
    while(low >= high){
        mid = (high+low)/2;
        if(EQ(L.base[mid].nums,nums)){
            // 如果出现了相同的次数,查找第一个出现的次数
            while(mid!=0){
                // 查找前一个元素是否符合次数
                if(!EQ(L.base[--mid].nums,nums)){
                    mid++;
                    break;
                }
            }
            return mid;
        }else {
            if(LT(L.base[mid].nums,nums)) low = mid-1;
            else high = mid+1;
        }
    }
    return -1;
}

// 查找元素
int LocateCache_data(Cache L,ElemType e){
    int i=0;
    // 设置哨兵
    L.base[L.length].data = e;
    for(;!EQ(L.base[i].data,e);i++);
    if(i==L.length) return -1;
    else return i;
}

// 在尾部插入元素,调用次数为1
status Push(Cache &L , ElemType e){
    Node *p;
    if(L.length>=L.listsize) return ERROR;
    p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->nums = 1;
    L.base[L.length] = *p;
    L.length++;
}

// 删除尾部元素
status Pop(Cache &L){
    if(L.length<1) return ERROR;
    L.length--;
}

status ShowCache(Cache L){
    int i=0;
    while(i<L.length){
        printf("cache Id nums:%d %d\n",L.base[i].data,L.base[i].nums);
        i++;
    }   
}

status EQ(ElemType a,ElemType b){
    return a==b?OK:ERROR;
}
status LT(ElemType a,ElemType b){
    return a<b?OK:ERROR;
}

FIFO

FIFO也是我们最常见的队列方式,如下图所示

file

一般开发步骤如下

  • 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动
  • 淘汰FIFO队列头部的数据
#include "stdio.h"
#include "stdlib.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int status;
typedef int ElemType;
typedef status (*fp)(ElemType a,ElemType b);

typedef struct QNode{
    ElemType data;
    QNode* next;
}QNode;

typedef struct Queue
{
    // 缓存个数
    int nums;
    // 当前个数
    int totals;
    // 头结点
    QNode *front;
    // 尾结点
    QNode *rear;
}Queue;

status InitQueue(Queue &Q);
status Locate_QNode(Queue Q,ElemType e,fp compare);
status equal(ElemType a,ElemType b);
status Add_QNode(Queue &Q,ElemType newQ,ElemType &oldQ);
status EnQueue(Queue &Q,ElemType e);
status DeQueue(Queue &Q,ElemType e);

status InitQueue(Queue &Q){
    int nums;
    printf("please input cache nums:");
    scanf("%d",&nums);
    if(nums<1) return ERROR;
    Q.nums = nums;
    Q.totals = 0;
    Q.front = (QNode*)malloc(sizeof(QNode));
    Q.front->next =  NULL;
    Q.rear = Q.front;
    return OK;
}

// 查找队列是否有对应的缓存
status Locate_QNode(Queue Q,ElemType e,fp compare){
    QNode *q1=Q.front;
    while(q1){
        if(compare(q1->data,e)) return OK;
        q1 = q1->next;
    }
    return ERROR;
}

status Add_QNode(Queue &Q,ElemType newQ,ElemType &oldQ){
    // 在尾部添加新的结点
    EnQueue(Q,newQ);
    // 缓存个数尚未满,个数增加
    if(Q.totals<Q.nums){
        Q.totals++;
    }else{
    // 缓存个数已满,去除头结点
        DeQueue(Q,oldQ);
    }
    return OK;
}

status EnQueue(Queue &Q,ElemType e){
    QNode *p;
    p = (QNode*)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

status DeQueue(Queue &Q,ElemType e){
    QNode *p;
    if(!Q.front->next) return ERROR;
    p = Q.front->next;
    Q.front->next = p->next;
    e = p->data;
    free(p);
    // 最后一个结点了
    if(!Q.front->next) Q.rear = Q.front;
    return OK;
}

status equal(ElemType a,ElemType b){
    return a==b?OK:ERROR;
}

int main(int argc, char const *argv[])
{
    // 测试缓存页面队列,不同数字代表不同的缓存页面
    ElemType a[] = { 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};
    int count = sizeof(a)/sizeof(a[0]);
    // j为置换次数,temp为置换出来的页面
    int i, j=0,temp;
    Queue Q;
    InitQueue(Q);
    for(i = 0; i < count;i++){
        if(!Locate_QNode(Q,a[i],equal)){
            Add_QNode(Q,a[i],temp);
            j++;
        }
    }
    printf("页面置换次数%d\n",j);
    return 0;
}

欢迎留言

avatar
  Subscribe  
Notify of