[캐시 알고리즘] LRU (Least Recently Used Algorithm)

캐시(Cache)란 무엇인가?

• 캐시는 데이터나 값을 미리 복사해 놓는 임시 저장소를 가리킨다.

캐시(Cache)의 특징

• 사용했던 데이터가 임시 저장소에 담겨있기 때문에 다시 사용할 때 빠르게 접근하여 데이터를 불러올 수 있다.
• 계산된 값이 저장되어 있어 다시 계산하는 시간을 줄일 수 있다.

LRU(Least Recently Used Algorithm)란 무엇인가?

• 가장 오랬동안 참조되지 않은 페이지를 교체하는 알고리즘 기법이다.
• 캐시에 공간이 부족할 때 가장 오랫동안 참조되지 않은 항목을 제거하고 새로운 항목을 삽입하는 형식으로 동작된다.

LRU 동작 과정

1. 빈 캐시안에 순차적으로 캐시를 채워준다.
2. 4번째 값인 8을 사용할때 참조할 수 있는 캐시가 없으므로 가장 오랫동안 참조되지 않은 값인 1을 삭제 후 맨 뒤에 8을 추가한다.
3. 7번째 값인 3을 사용할때 참조할 수 있는 캐시가 2번째에 있으므로 해당 값을 참조하여 맨 뒤로 옮겨준다.

Python 코드

• cache hit(캐시 적중): 참조할 데이터가 존재한다.
• cache miss(캐시 부적중): 참조할 데이터가 존재하지 않는다.

Number = [1, 4, 5, 8, 3, 4, 3]
cache_size = 3
cache = []
for data in Number:
    if data not in cache:	# 참조할 데이터가 없는 경우
        # cache miss
        if len(cache) < cache_size:	# 빈 캐시가 존재할 경우
            cache.append(data)
        else:		# 빈 캐시가 존재하지 않을 경우
            cache.pop(0)		# 가장 오래된 데이터 삭제
            cache.append(data)		# 새로운 데이터 추가
    # cache hit
    else:		# 참조할 데이터가 있는 경우
        cache.remove(data)		# 참조된 데이터를 삭제
        cache.append(data)		# 참조된 데이터를 맨 뒤로 이동
        
# [1]
# [1, 4]
# [1, 4, 5]
# [4, 5, 8]
# [5, 8, 3]
# [8, 3, 4]
# [8, 4, 3]

응용문제

https://programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

참고자료

• 위키백과: https://ko.wikipedia.org/wiki/%EC%BA%90%EC%8B%9C
• https://gingerkang.tistory.com/26#