LRU Cache 데이터 구조 안내

LRU Cache 가 뭐야?
LRU 는 Least Recently Used 의 줄 임 말로 최근 에 가장 적 게 사용 한 다 는 뜻 으로 Cache 교체 알고리즘 이다.캐 시가 뭐야?협의 적 인 Cache 는 CPU 와 메 인 메모리 사이 에 있 는 빠 른 RAM 을 말 하 는데 보통 시스템 메 인 메모리 처럼 D 램 기술 을 사용 하지 않 고 비 싸 지만 빠 른 SRAM 기술 을 사용한다.넓 은 의미 에서 Cache 는 속도 차이 가 비교적 큰 두 가지 하드웨어 사이 에 위치 하고 이들 의 데이터 전송 속도 차 이 를 조율 하 는 구 조 를 말한다.CPU 와 메 인 메모리 사이 에 Cache 가 있 는 것 을 제외 하고 메모리 와 하 드 디스크 사이 에 도 Cache 가 있 으 며 하 드 디스크 와 네트워크 사이 에 도 어떤 의미 의 Cache 가 있 습 니 다. 인터넷 임시 폴 더 나 네트워크 콘 텐 츠 캐 시 등 이 라 고 합 니 다.
Cache 의 용량 이 제한 되 어 있 기 때문에 Cache 의 용량 을 다 쓴 후에 새로운 내용 을 추가 해 야 할 때 원래 의 일부 내용 을 선택 하고 버 려 서 공간 을 비 워 새로운 내용 을 넣 어야 한다.LRU 캐 시의 교체 원칙 은 최근 가장 적 게 사용 한 콘 텐 츠 를 교체 하 는 것 이다.사실 LRU 를 으로 번역 하면 더욱 이미지 가 좋아 집 니 다. 이 알고리즘 은 매번 교체 할 때마다 한 동안 사용 하지 않 은 내용 이기 때 문 입 니 다.
데이터 구조
LRU 의 전형 적 인 실현 은 hash map + doubly linked list 이 고 양 방향 링크 는 데이터 노드 를 저장 하 는 데 사용 되 며 노드 가 최근 에 사 용 된 시간 에 따라 저장 된다.만약 하나의 결점 이 방문 된다 면, 우 리 는 그것 이 다음 시간 에 방문 할 확률 이 다른 결점 보다 높다 고 믿 을 이유 가 있다.그래서 우 리 는 그것 을 양 방향 링크 의 머리 에 놓 았 다.우리 가 양 방향 링크 에 결점 을 삽입 하면 우 리 는 곧 그것 을 사용 할 수도 있 고 똑 같이 머리 에 삽입 할 수도 있다.우 리 는 이런 방식 으로 양 방향 링크 를 계속 조정 하고 있 습 니 다. 링크 꼬리 의 결점 은 자 연 스 럽 게 최근 한 동안 가장 오랫동안 사용 하지 못 한 결점 입 니 다.그러면 우리 의 Cache 가 가득 차 면 교체 해 야 할 것 은 바로 양 방향 링크 의 마지막 점 (끝 점 이 아니 라 머리 끝 점 은 실제 내용 을 저장 하지 않 습 니 다) 입 니 다.
다음은 양 방향 링크 설명도 입 니 다. 머리 끝 에 있 는 노드 가 실제 내용 을 저장 하지 않도록 주의 하 세 요.

  -->   -->   -->   -->  
                         
   

만약 위의 그림 이 Cache 가 가득 찼 다 면, 우리 가 교체 해 야 할 것 은 결점 3 이다.
해시 표 의 역할 은 무엇 입 니까?만약 해시 표 가 없다 면, 우 리 는 어떤 결점 을 방문 하려 면 순서대로 하나씩 찾 아야 한다. 시간 복잡 도 는 O (n) 이다.해시 표를 사용 하면 O (1) 시간 에 접근 하고 싶 은 노드 를 찾 거나 찾 지 못 한 곳 으로 돌아 갈 수 있 습 니 다.
캐 시 인터페이스
T 형식의 데 이 터 를 키 로 접근 할 때 Get 함 수 를 호출 합 니 다.키 값 이 key 인 데이터 가 Cache 에 있 으 면 이 데 이 터 를 되 돌려 주 고 이 데 이 터 를 저장 하 는 노드 를 양 방향 링크 머리 로 옮 깁 니 다.만약 우리 가 조회 한 데이터 가 Cache 에 없다 면, 우 리 는 Put 인 터 페 이 스 를 통 해 데 이 터 를 양 방향 링크 에 삽입 할 수 있 습 니 다.만약 이때 의 Cache 가 채 워 지지 않 았 다 면, 우 리 는 새 노드 를 링크 머리 에 삽입 하 는 동시에 해시 표 로 노드 의 키 값 과 노드 주 소 를 저장 합 니 다.만약 Cache 가 가득 찼 다 면 우 리 는 링크 의 마지막 노드 (끝 점 이 아 닌 것 을 주의 하 세 요) 의 내용 을 새로운 내용 으로 바 꾼 다음 머리 로 이동 하여 해시 표를 업데이트 합 니 다.
C + + 코드
주의 하 세 요. hash map 는 C + 표준 의 일부분 이 아 닙 니 다. 저 는 Linux 에서 g + 4.6.1, hash 를 사용 합 니 다.map 는 / usr / include / c + / 4.6 / ext 에 놓 고 __gnu_cxx 명의 공간 을 사용 해 야 합 니 다. Linux 플랫폼 은 c + + 의 include 디 렉 터 리 로 전환 할 수 있 습 니 다. cd / usr / include / c + / 버 전 을 사용 한 다음 grep - ir "hash map". / 어떤 파일 에서 일반 헤더 파일 의 마지막 줄 은 이름 공간 을 알려 줍 니 다. 물론 C + + 11 을 패션 적 으로 사용 하고 있다 면 이런 작은 어려움 은 없 을 것 이다.
 

#include 
#include 
#include 

using namespace std;
using namespace stdext;

template
struct LRUCacheEntry
{
	K key;
	T data;
	LRUCacheEntry* prev;
	LRUCacheEntry* next;
};

template
class LRUCache
{
private:
	hash_map< K, LRUCacheEntry* >	_mapping;
	vector< LRUCacheEntry* >		_freeEntries;//          
	LRUCacheEntry *			head;
	LRUCacheEntry *			tail;
	LRUCacheEntry *			entries;//         
public:
	LRUCache(size_t size){
		entries = new LRUCacheEntry[size];
		for (int i=0; i;
		tail = new LRUCacheEntry;
		head->prev = NULL;
		head->next = tail;
		tail->next = NULL;
		tail->prev = head;
	}
	~LRUCache()
	{
		delete head;
		delete tail;
		delete [] entries;
	}
	void put(K key, T data)
	{
		LRUCacheEntry* node = _mapping[key];
		if(node)
		{
			// refresh the link list
			detach(node);
			node->data = data;
			attach(node);
		}
		else{
			if ( _freeEntries.empty() )
			{//       ， cache  
				node = tail->prev;
				detach(node);
				_mapping.erase(node->key);
				node->data = data;
				node->key = key;
				attach(node);
			}
			else{
				node = _freeEntries.back();
				_freeEntries.pop_back();
				node->key = key;
				node->data = data;
				_mapping[key] = node;
				attach(node);
			}
		}
	}

	T get(K key)
	{
		LRUCacheEntry* node = _mapping[key];
		if(node)
		{
			detach(node);
			attach(node);
			return node->data;
		}
		else return NULL;//   cache   ，  T    。 hashmap    
	}

private:
        //     
	void detach(LRUCacheEntry* node)
	{
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}
        //        
	void attach(LRUCacheEntry* node)
	{
		node->next = head->next;
		node->prev = head;
		head->next = node;
		node->next->prev = node;
	}
};

int main(){
    hash_map map;
    map[9]= 999;
    cout<

 
다음으로 전송:https://www.cnblogs.com/XP-Lee/p/3441555.html