LRU Cache Algorithm(Least Recently Used)

LRU 알고리즘이란?

• 해석 그대로 가장 오래된 데이터를 없애고 새로운 데이터를 넣는 알고리즘이다.
• 캐시에서 사용되는 알고리즘
• 캐시는 많은 데이터를 담지 못하므로 이러한 페이지 교체 알고리즘이 필요하다.
• 이중연결리스트를 사용하여 node를 관리한다.

설명

1. ListNode로 사용할 클래스를 만든다.
2. 접근 성능 개선을 위해 Map을 사용하여 key의 존재 유무를 빠르게 찾을 수 있다.
3. head는 새로 들어올 node를 nodeList에 연결해 주기 위한 역할(next만 사용)
4. tail은 삭제될 node를 가리키기 위한 역할 (prev만 사용)
5. put 메서드
   • 새로운 노드 생성
   • 키 존재 여부확인
   • 존재하는 경우, Listnode에서 해당 키를 가진 노드를 삭제 후 inserToHead 호출
   • 존재하지 않은 경우, 또 Map사이즈 즉 캐시 사이즈보다 큰 경우 tail의 prev(삭제될 노드)를 가지고 remove 호출
6. insertToHead 메서드
   • head.next.prev(마지막에 들어간 노드의 prev)에 추가될 노드를 넣음
   • 추가될 노드의 next에 head.next(마지막에 들어간 노드)를 넣어주고 prev에 head를 넣음
   • head.next에 추가될 노드를 넣어주고 Map에 추가시켜주면 끝
7. remove 메서드
   • node.prev.next(삭제될 노드의 다음에 들어온 노드의 next)에 node.next(삭제될 노드보다 먼저 들어온 노드)를 넣음.
   • node.next.prev(삭제될 노드보다 먼저 들어온 노드의 prev)에 node.prev(삭제될 노드 다음으로 들어온 노드)를 넣음.
   • Map에서 삭제하면 끝

예시

코드(Java)

public class LRU {
	private class ListNode {
		private int key;
		private int val;
		private ListNode prev;
		private ListNode next;

		public ListNode(int key, int val) {
			this.key = key;
			this.val = val;
			this.prev = null;
			this.next = null;
		}
	}

	private Map<Integer, ListNode> nodeMap;
	private int capacity;
	private ListNode head;
	private ListNode tail;

	public LRU(int capacity) {
		this.nodeMap = new HashMap<>();
		this.capacity = capacity;
		head = new ListNode(0, 0);
		tail = new ListNode(0, 0);
		head.next = tail;
		tail.prev = head;
	}

	private void remove(ListNode node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
		nodeMap.remove(node.key);
	}

	private void insert(ListNode node) {
		this.head.next.prev = node;
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next = node;
		nodeMap.put(node.key, node);
	}

	public int get(int key) {
		if (!nodeMap.containsKey(key)) {
			return -1;
		}
		ListNode node = nodeMap.get(key);
		remove(node);
		insertToHead(node);
		return node.val;
	}

	public void put(int key, int value) {
		ListNode newNode = new ListNode(key, value);
		if (nodeMap.containsKey(key)) {
			ListNode oldNode = nodeMap.get(key);
			remove(oldNode);
		} else {
			if (nodeMap.size() >= capacity) {
				ListNode tailNode = tail.prev;
				remove(tailNode);
			}
		}
		insert(newNode);
	}
}

References

https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

Cache replacement policies - Wikipedia

https://jins-dev.tistory.com/entry/LRU-Cache-Algorithm-정리

불러오는 중입니다...