LRU Cache

캐시란 속도가 빠른 장치와 속도가 느린 장치 간의 병목현상을 줄이기 위한 범용 메모리로, 지역성을 이용해 사용할 데이터를 예측해 저장한다

 

쉽게 말하면 사용했던 데이터를 속도가 빠른 저장장치에 저장해놓고, 다음에 참조할때 캐시 메모리를 이용해 빠르게 참조하는 방식이다

 

LRU는 Least Recently Used의 약자로 가장 최근에 참조되지 않은 데이터가 교체시점에서 먼저 나가는 방식이다.

 

컴퓨터 구조 전공 수업에서 배운 내용은 아래와 같았다 

 

A, B, C, D 순으로 데이터가 참조되었다면 참조비트는 아래와 같고

A	B	C	D
1	2	3	4

 

캐시 메모리가 가득 찬 상태에서 캐시 메모리에 있는 데이터 A를 다시 참조할 경우

A	B	C	D
4	1	2	3

 

캐시 메모리에 없는 데이터 E가 참조될 경우 교체가 일어나는데 이때는 참조비트가 가장 작은 데이터 B가 먼저 제거되고, 나머지 데이터들의 참조비트는 1씩 감소하는 방식이다

A	E	C	D
3	4	1	2

 

배열이나 단순 우선 순위 큐, 트리맵를 사용하게 되면 삽입, 삭제 과정에서 효율성이 좋지 못하다.

 

LRU를 효율적으로 구현하는 방법은 해시맵과 Double Linked List를 사용해서 구현하는 방법이 있다.

 

head에 가장 최근에 참조된 데이터를 저장하고 tail에 가장 최근에 참조되지 않은 데이터를 저장해 교체가 일어나야하는  시점에 tail에 있는 데이터가 교체가 일어나는 방식이다

 

데이터가 3, 2, 1 순서로 캐시에 저장되었다면 아래와 같다

 

 

만약 캐시 미스가 발생한다면 tail이 가르키는 데이터 3이 삭제되고 tail은 2를 가르킨다. 

또한, 새로 저장된 데이터는 head가 가르키는 1과 연결되고 head는 새로저장된 데이터를 가르키게 된다

 

 

캐시 히트가 발생한다면 해당하는 데이터(2)를 head가 가르키는 데이터(4)와 연결하고 head는 해당 데이터(2)를 가르키게 된다

 

 

해시맵을 사용함으로써 검색은 O(1)의 시간 복잡도를 가지고 삽입, 삭제는 이중 포인터를 사용함으로써 마찬가지로 시간 복잡도는 O(1)이 된다.

 

package algorithm;

import java.util.*;

public class LRU {
	private HashMap<Integer, Node> map;
	private int capacity;
	private Node head;
	private Node tail;
	
	private class Node{
		private int key;
		private int value;
		private Node prev;
		private Node next;
		
		public Node(int key, int value) {
			this.key = key;
			this.value = value;
			this.next = null;
			this.prev = null;
		}
	}
	
	// initialize
	public LRU(int capacity) {
		this.map = new HashMap<>();
		this.capacity = capacity;
		head = new Node(0, 0);
		tail = new Node(0, 0);
		head.next = tail;
		tail.prev = head;
	}
	
	// put to head
	// time complexity O(1)
	private void insertToHead(Node node) {
		this.head.next.prev = node;
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next = node;
		
		map.put(node.key, node);
	}
	
	// remove
	// time complexity O(1)
	private void remove(Node node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
		
		map.remove(node.key);
	}
		
	// put to tail
	// time complexity O(1)
	public void put(int key, int value) {
		Node node = new Node(key, value);
		if(map.containsKey(key)) {
			Node old = map.get(key);
			remove(old);
		}
		else {
			if(map.size() >= this.capacity) {
				Node del = tail.prev;
				remove(del);
			}
		}
		insertToHead(node);
	}
	
	
	// get value 
	// time complexity O(1)
	public int get(int key) {
		if(!map.containsKey(key)) return -1;
		Node node = map.get(key);
		remove(node);
		insertToHead(node);
		return node.value;
	}
}