오늘 알아볼 알고리즘은 LRU 알고리즘이다.
문제에서 LRU알고리즘에 대한 언급은 있었으나 설명이 나와있지 않아 처음으로 알아보게 되었다.
💡 참고 문제
[프로그래머스] 캐시
알고리즘에 대해서 숙지만 하고 있다면 코드를 작성하는 것은 어렵지 않게 할 수 있으므로 오늘 포스팅에서는 문제풀이 보다는 알고리즘 설명을 중심으로 써보려고 한다.
📌 캐시(Cache)란?
LRU 알고리즘은 캐시를 활용해서 푸는 캐시 교체 알고리즘의 한 종류이다.
그렇다면 캐시는 뭘까?
캐시란 데이터나 값을 복사해 놓는 저장소라고 할 수 있다!
하지만 캐시도 곧 저장소이기 때문에 용량이 정해져 있다. 즉, 모든 데이터를 캐시에 저장할 수는 없기 때문에 몇 가지 알고리즘에 따라서 캐시에 데이터가 저장된다. 그게 바로 캐시 교체 알고리즘이다!
캐시 교체 알고리즘에는 3종류가 있다.
1. FIFO (First In First Out)
2. LFU (Least Frequently Used)
3. LRU (Least Recently Used)
FIFO는 한마디로 선입선출 방식으로 스택과 큐를 공부할 때 보고 넘어갔으므로 이번 포스팅에서는 패스!
LRU를 중점으로 알아보고 추가로 LFU에 대해서도 간략하게 알아볼 예정이다.
📌 LRU란?
LRU는 (Least Recently Used) 의 약자로 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이다.
LRU는 사용된 지 가장 오래된 데이터는 앞으로도 사용 확률이 낮다고 판단해 만들어진 알고리즘이라고 한다.
📌 LRU의 원리
LRU를 구현하기 위해서는 캐시가 가득 차서 더이상 공간이 없을 때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애주는 작업이 필요하다.
즉, 참조하는 값이 캐시 안에 없다면 가장 오래 전에 참조한 값은 없애고 현재의 값을 캐시에 새로 넣어준다.
참조하는 값이 이미 캐시에 존재한다면 해당 값을 캐시의 가장 최근 위치로 넣어준다.
예를 들어,
- 캐시의 크기가 3인데 이미 3개의 페이지가 캐시에 들어가 더이상 빈 공간이 없다면 맨 뒤에 페이지번호 node를 지우고 새로운 페이지번호 node를 앞에 연결해주는 방식이다.
- 여기서 알 수 있는 건 LRU를 구현할 때는 더블 링크드 리스트를 사용하고 head에 가까울 수록 최근에 참조한, tail에 가까울수록 오랫동안 참조되지 않은 노드라는 것을 알 수 있다.
💡 Cache Hit & Cache Miss
LRU 알고리즘에서는 Cache Hit과 Cache Miss라는 용어에 대해서도 알아야 한다.
- Cache Hit: CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우
- Cache Miss: CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우
👩🏻💻 문제 설명
문제를 보면 단순 LRU를 구현하며 소요되는 총 시간을 구하면 된다.
cache hit이라면 +1의 시간을, cache miss라면 +5의 시간을 주면서 알고리즘을 구현해보면 쉽게 풀 수 있다.
# 캐시 교체 알고리즘 LRU(Least Recently Used)
# 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식
# cache hit : cpu가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우 캐시에 먼저 들어와 있던 데이터를 맨위로 올리는 방법 - 실행시간 1
# cache miss : cpu가 ,,, 캐시에 존재하지 않을 경우 - 실행시간 5
# 총 실행시간을 출력하기
from collections import deque
def solution(cacheSize, cities):
# maxlen 값을 지정해주면 큐에 빈 공간이 없을 때 데이터가 들어올 경우
# 가장 왼쪽에 위치한 값을 알아서 삭제
buffer = deque(maxlen=cacheSize)
total = 0
# 캐시 크기가 0인 경우 모두 cache miss
if cacheSize == 0:
return len(cities) * 5
for i in cities:
# 대소문자 구분 x => 소문자로 통일
i = i.lower()
# cache hit
if i in buffer:
total += 1
buffer.remove(i)
buffer.append(i)
else:
# cache miss
total += 5
buffer.append(i)
return total
🧐 LFU (Least Frequently Used) 알고리즘
위에서 알아본 LRU 알고리즘에서는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이었다면 LFU 알고리즘은 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
교체할 수 있는 대상이 여러 개라면 그 중에서 가장 오랫동안 사용하지 않은 페이지를 교체한다.
LRU알고리즘에 비해서 전체적인 횟수와 시간 규모까지 볼 수 있기 때문에 성능을 더 향상시킬 수 있다는 장점이 있다.
하지만 각 데이터의 참조 횟수를 비교해야 하기 때문에 구현 방법이 LRU에 비해서는 어렵다는 단점이 있다.
한 마디로 정리하면 페이지를 교체해야 하는 상황에서 LRU는 시간만을 비교한다면 LFU는 참조 횟수와 시간 모두를 보는 알고리즘이라고 생각하면 간단하다!
예제가 있으면 함께 보면 좋을텐데 아쉽게도 운영체제와 관련된 내용이다 보니 예제를 찾기가 힘들다,,🥲
다음에 예제를 찾으면 다시 한 번 포스팅으로 남겨야겠다!
-그럼 끝-
