[Algorithm] LRU cache

[Algorithm] LRU Cache

Latest Recently Used Cache

Cache

• 데이터나 값을 미리 복사해 놓은 임시 장소.
• 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하는 경우 사용.
• 미리 데이터를 복사해 놓으면 계산이나 접근 시간 없이 빠르게 데이터에 접근 가능.
• 사용 가능한 리소스 양 제한 있음.

LRU Cache

• OS의 페이지 교체 알고리즘의 하나.
• 가장 오래 사용하지 않은 페이지를 교체하는 알고리즘.
• 공간이 부족하면 가장 최근에 사용하지 않은 항목을 제거.

구현 방법

• Doubly Linked List로 구현.
• head에 가까운 데이터일수록 최근에 사용한 데이터.
• tail에 가까울수록 사용하지 않은 데이터.
• 사용 가능한 리소스를 다 쓴 상태에서 새로운 데이터를 추가할 때 tail의 데이터를 제거한다.