LRU 캐시제거 알고리즘✨
LRU 알고리즘이란?
캐시를 제거하는 것, 으로 원리는 어렵지 않다.
그러나 면접에서는 버그가 없는 알고리즘을 작성하려면 기법이 필요하다.
즉, 데이터 구조를 계층별로 추상화하고 분해해야한다.
필요성
컴퓨터의 캐시 용량은 제한적이으로 캐시가 가득 차면 일부 데이터를 삭제하여 새로운 데이터를 위해 공간을 마련해야 한다.
문제는 어떤 데이터를 삭제할 것인가 이다.
쓸모없는 캐시 데이터를 삭제하고 필요한 데이터만 남겨 이후에 다시 사용하고자 할 때, 어떤 데이터를 유용한 데이터로 볼 것인가?
LRU의 원리
LRU는 Least Recently Used의 약자로, 최근에 사용한 데이터가 유용하고 오랫동안 사용하지 않은 데이터는 불필요한 데이터로 생각할 수 있다. 따라서 메모리가 가득 차면 오랫동안 사용하지 않은 데이터를 먼저 삭제한다.
예시: 휴대폰
간단한 예로 휴대폰은 백그라운드에서 앱을 실행할 수 있다.
다음과 같은 순서로 앱을 연다고 가정하자.
1. 설정
2. 계산기
3. 캘린더
백그라운드에서 정렬되는 순서는 다음과 같다.
1.캘린더 > 2.계산기 > 3.설정
그러나 계산기를 누르면 계산기가 첫번째로 오게 되어 다음과 같은 상태가 된다 .
1. 계산기 > 2. 캘린더 > 3. 설정
다음과 같은 가정이 있다고 하자.
- 폰에서 동시에 3가지 앱만 열 수 있다.
- 이미 가득찬 상태이다.
만약, 위와 같은 상황에서 새로운 앱인 시계를 열면 시계를 실행하기 위해 하나의 앱을 닫아야 한다. 어떤 앱을 닫을까?
LRU는 가장 오랫동안 사용하지 않은 앱을 닫고 새로 실행하는 앱을 제일 위에 놓는다.
LRU 설명
LeetCode 146번 문제 'LRU 캐시'는 데이터 구조를 설계하는 문제이다.
capacity 매개변수를 캐시의 최대 용량으로 받고 두 API를 구현한다.
1. put(key, value)로 키와 값 세트를 저장하는 method
2. get(key), key에 대응하는 val을 가져오는 method
- 키가 존재하지 않으면 -1을 반환한다.
/*캐시 용량*/
LRUCache cache = new LRUCache(2);
//cache를 큐로 생각할 수 있음
// 왼쪽을 큐의 헤드, 오른쪽을 큐의 테일로 가정
//가장 최근에 사용한 것을 헤드에, 오랫동안 사용하지 않은 것을 테일에
//괄호는 키-값 세트(key, val)를 의미
cache.put(1,1);
// cache = [(1,1)]
cache.put(2,2);
// cache = [(2,2),(1,1)]
cache.get(1); // 1반환
//cache = [(1,1),(2,2)]
// 설명: 키1이 가장 최근에 엑세스되었으므로 헤드에 위치
//키1에 해당하는 값 1 반환
cache.put(3,3);
// cache = [(3,3),(1,1)]
// 설명: 캐시용량이 가득차면 공간 확보를 위해 데이터 삭제
// 오랫동안 사용하지 않은 데이터인 테일 데이터를 삭제
// 새로운 데이터를 헤드에 삽입
cache.get(2); //-1 반환 (찾을 수 없음)
// cache = [(3,3),(1,1)]
// 설명: 캐시에 키2 데이터 존재 X
cache.put(1,4);
// cache = [(1,4)(3,3)]
// 설명: 키1이 이미 존재하므로 원래 데이터1을 4로 덮어쓰기
// 키-값 세트를 헤드에 위치 시키는 것도 잊지 말아야 함
LRU 알고리즘 설계
put&&get메서드의 시간 복잡도를 O(1)로 만들기 위해서 cache 데이터 구조에 필요한 조건은 다음과 같다.
-
cache의 요소는 최근에 사용한 것과 오랫동안 사용하지 않은 데이터를 구분하기 위해
시간 순서대로 정렬해야 한다.
용량이 가득 차면 오랫동안 사용하지 않은 요소를 제거한다. -
cache에 키가 존재하는지 빠르게
탐색하고 해당val을 가져온다. -
cache에 있는 키를 엑세스할 때 마다 이 요소를 최근에 사용한 요소로 변경한다. cache는 어떤 위치의 요소라도 빠르게 삽입과 삭제를 지원해야한다.
위 조건을 만족하는 데이터 구조는 해시 연결 리스트(LinkedHashMap)이다.
해시 연결 리스트는 양방향 연결 리스트와 해시테이블의 조합이고 이다.
아래 각각의 데이터구조의 장단점을 보면 이 둘을 엮은 이유가 명확해진다.
- 해시테이블
- [장점] 검색이 빠르다.
- [단점] 데이터 순서가 고정되어 있지 않다. - 연결 리스트
- [장점] 순서대로 분류되어 있고 삽입과 삭제가 빠르다.
- [단점] 하지만 검색이 느리다.
♨ Live Documentation 👀
설계 && 코드구현 정리 (-ing)
