c++구현 되 는 일반적인 캐 시 알고리즘 과 LRU

머리말
웹 개발 에 있어 서 캐 시가 없어 서 는 안 되 며,성능 을 향상 시 키 는 데 가장 자주 사용 되 는 방식 이기 도 하 다.브 라 우 저 캐 시(chrome 브 라 우 저 라면 chrome:/cache 를 통 해 볼 수 있 습 니 다)든 서버 캐 시(memcached 나 redis 등 메모리 데이터 베 이 스 를 통 해 볼 수 있 습 니 다)든.캐 시 는 사용자 의 접근 을 가속 화 할 뿐만 아니 라 서버 의 부하 와 압력 도 낮 출 수 있다.그렇다면 흔히 볼 수 있 는 캐 시 탈락 알고리즘 의 전략 과 원 리 를 이해 하 는 것 이 중요 하 다.
일반적인 캐 시 알고리즘
LRU(Least recently used)는 최근 에 가장 적 게 사용 하고 있 으 며,데이터 가 최근 에 방 문 된 적 이 있다 면 앞으로 방 문 될 확률 도 높다

LFU(Least frequently used)는 가장 자주 사용 되 지 않 는 다.만약 에 하나의 데이터 가 최근 에 사용 되 는 횟수 가 적 으 면 앞으로 한 동안 사 용 될 가능성 도 적다

FIFO(Fist in first out)가 먼저 나 오고 한 데이터 가 캐 시 에 가장 먼저 들 어가 면 가장 먼저 탈락 해 야 합 니 다.

LRU 캐 시
브 라 우 저의 캐 시 정책,memcached 와 같은 캐 시 정책 은 모두 LRU 라 는 알고리즘 을 사용 합 니 다.LRU 알고리즘 은 최근 에 가장 접근 하지 않 을 데 이 터 를 삭제 합 니 다.LRU 가 이렇게 유행 하 는 이 유 는 실현 이 비교적 간단 하고 실제 문제 에 도 실 용적 이 며 잘 작 동 할 때 성능 이 좋아 명중률 이 높 기 때문이다.LRU 캐 시 를 어떻게 실현 하 는 지 에 대해 이야기 합 니 다.

새 데 이 터 를 링크 머리 에 삽입 합 니 다

캐 시 명중(즉 캐 시 데이터 가 접근 할 때마다)데 이 터 를 링크 머리 로 옮 깁 니 다

4.567917.링크 가 가득 찼 을 때 링크 끝의 데 이 터 를 버 립 니 다.
LRU Cache 가 갖 춘 동작:

set(key,value):key 가 hashmap 에 존재 하면 해당 하 는 value 값 을 리 셋 한 다음 에 해당 하 는 노드 cur 를 가 져 와 cur 노드 를 링크 에서 삭제 하고 링크 의 머리 로 이동 합 니 다.만약 에 키 가 hashmap 에 존재 하지 않 는 다 면 노드 를 새로 만 들 고 노드 를 링크 의 머리 에 놓 습 니 다.Cache 가 가득 찼 을 때 링크 의 마지막 노드 를 삭제 하면 됩 니 다

get(key):key 가 hashmap 에 존재 하면 해당 하 는 노드 를 링크 머리 에 놓 고 해당 하 는 value 값 을 되 돌려 줍 니 다.존재 하지 않 으 면-1 로 돌아 갑 니 다.

LRU 의 c++구현
LRU 는 양 방향 링크+Map 으로 이 루어 집 니 다.여기 서 양 방향 링크 를 사용 하 는 이 유 는 일반적인 단일 링크 표를 사용 하면 노드 를 삭제 할 때 표 머리 부터 옮 겨 다 니 며 찾 아야 하기 때 문 입 니 다.효율 은 O(n)이 고 양 방향 링크 를 사용 하면 노드 의 전구 지침 방향 을 직접 바 꾸 어 O(1)의 효율 에 이 를 수 있 습 니 다.맵 을 사용 하여 노드 의 key,value 값 을 저장 하면 O(logN)의 시간 에 요 소 를 찾 을 수 있 고 get 작업 에 대응 할 수 있 습 니 다.
더 블 링크 노드 의 정의:

struct CacheNode {
 int key;  //  
 int value; //  
 CacheNode *pre, *next; //      、    
 CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

LRUCache 클래스 의 경우 구조 함 수 는 용량 크기 를 지정 해 야 합 니 다.

LRUCache(int capacity)
{
 size = capacity;  //   
 head = NULL;   //      
 tail = NULL;   //      
}

더 블 링크 의 노드 삭제 작업:

void remove(CacheNode *node)
{
 if (node -> pre != NULL)
 {
 node -> pre -> next = node -> next;
 }
 else
 {
 head = node -> next;
 }
 if (node -> next != NULL)
 {
 node -> next -> pre = node -> pre;
 }
 else
 {
 tail = node -> pre;
 }
}

노드 를 머리 에 삽입 하 는 동작:

void setHead(CacheNode *node)
{
 node -> next = head;
 node -> pre = NULL;

 if (head != NULL)
 {
 head -> pre = node;
 }
 head = node;
 if (tail == NULL)
 {
 tail = head;
 }
}

4.567914.작업 의 실현 이 비교적 간단 하 므 로 맵 에 key 값 이 있 는 지 직접 판단 하면 됩 니 다.key 를 찾 으 면 해당 하 는 value 를 되 돌려 줍 니 다.그렇지 않 으 면-1 을 되 돌려 줍 니 다.

int get(int key)
{
 map<int, CacheNode *>::iterator it = mp.find(key);
 if (it != mp.end())
 {
 CacheNode *node = it -> second;
 remove(node);
 setHead(node);
 return node -> value;
 }
 else
 {
 return -1;
 }
}

4.567914.조작 은 상황 에 따라 판단 해 야 한다.현재 key 값 에 대응 하 는 노드 가 존재 한다 면 이 노드 를 꺼 내 고 노드 가 있 는 원래 의 위 치 를 삭제 하 며 머리 에 이 노드 를 삽입 합 니 다.만약 에 노드 가 노드 에 존재 하지 않 는 다 면 이때 링크 의 머리 에 새로운 노드 를 삽입 해 야 한다.새로운 노드 를 삽입 하면 용량 이 넘 칠 수 있 고 넘 치 는 상황 이 발생 하면 링크 끝의 노드 를 삭제 해 야 한다.

void set(int key, int value)
{
 map<int, CacheNode *>::iterator it = mp.find(key);
 if (it != mp.end())
 {
 CacheNode *node = it -> second;
 node -> value = value;
 remove(node);
 setHead(node);
 }
 else
 {
 CacheNode *newNode = new CacheNode(key, value);
 if (mp.size() >= size)
 {
  map<int, CacheNode *>::iterator iter = mp.find(tail -> key);
  remove(tail);
  mp.erase(iter);
 }
 setHead(newNode);
 mp[key] = newNode;
 }
}

총결산
자,이로써 LRU 알고리즘 의 실현 작업 이 완성 되 었 습 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 면 댓 글 을 남 겨 주 십시오.