캐시 시스템을 설계할 때 어떤 데이터를 먼저 내보낼지 결정하는 기준은 전체 성능에 큰 영향을 미칩니다. 이번 글에서는 LFU(Least Frequently Used, 최소 빈도 사용) 방식의 캐시를 Python으로 직접 설계하고 구현하는 방법을 단계별로 살펴보겠습니다.
LFU 캐시가 지원해야 할 연산
LFU 캐시용 자료구조는 다음 두 가지 연산을 지원해야 합니다.
- get(key) – 키가 캐시에 존재하면 해당 키의 값을 반환하고, 존재하지 않으면 -1을 반환합니다.
- put(key, value) – 키가 아직 캐시에 없다면 새로운 키-값 쌍을 설정하거나 삽입합니다.
캐시가 최대 용량(capacity)에 도달한 상태에서 새로운 요소를 삽입해야 할 때는, 그전에 사용 빈도가 가장 낮은 요소를 먼저 제거해야 합니다. 사용 빈도가 같은 요소가 여러 개라면, 일반적으로 가장 먼저 삽입된(FIFO 순서상 앞선) 요소를 제거합니다.
동작 예시
용량이 2인 LFUCache를 생성한 뒤 다음 메서드를 순서대로 호출한다고 가정해 보겠습니다.
cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(2); cache.put(4, 4); cache.get(1); cache.get(3); cache.get(4)
이때 출력 결과는 차례대로 1, -1, 1, -1, 4가 됩니다. 각 단계를 자세히 살펴보면 다음과 같습니다.
put(1, 1),put(2, 2)→ 캐시에 키 1과 2가 각각 빈도 1로 저장됩니다.get(1)→ 1을 반환하며, 키 1의 빈도가 2로 증가합니다.put(3, 3)→ 용량이 가득 찼으므로 빈도가 가장 낮은 키 2를 제거한 뒤 키 3을 삽입합니다.get(2)→ 키 2는 이미 제거되었으므로 -1을 반환합니다.put(4, 4)→ 빈도가 가장 낮은 키 3을 제거한 뒤 키 4를 삽입합니다.get(1)→ 1을 반환합니다.get(3)→ 키 3은 제거되었으므로 -1을 반환합니다.get(4)→ 4를 반환합니다.
구현 전략
이 문제의 핵심은 두 개의 맵(map)을 함께 운영하는 것입니다. 하나는 키를 기준으로 값을 추적하고, 다른 하나는 빈도별로 항목을 삽입 순서대로 관리합니다. 해결 절차는 다음과 같습니다.
- 생성자(
__init__)는 용량(capacity) 값을 받습니다. remain := capacity– 남은 저장 공간을 나타냅니다.least_freq := 1– 현재 최소 빈도 값을 추적합니다.node_for_freq– 빈도별로 데이터를 삽입 순서에 따라 관리하는 맵입니다.node_for_key– 키를 기준으로 (값, 빈도) 정보를 저장하는 새로운 맵입니다.
_update() 함수
_update()는 key와 value를 인자로 받아 기존 항목의 빈도를 1 증가시키고 위치를 갱신합니다.
x, freq := node_for_key[key]– 현재 빈도를 조회합니다.node_for_freq[freq]에서 해당 키를 삭제합니다.- 만약
node_for_freq[least_freq]의 크기가 0이 되면least_freq를 1 증가시킵니다. node_for_freq[freq+1][key] := (value, freq+1)node_for_key[key] := (value, freq+1)
get() 함수
- 키가
node_for_key에 존재하지 않으면 -1을 반환합니다. value := node_for_key[key][0]으로 값을 가져옵니다._update(key, value)를 호출해 빈도를 갱신합니다.- value를 반환합니다.
put() 함수
- 키가 이미
node_for_key에 있으면_update(key, value)를 호출합니다. - 그렇지 않은 경우:
node_for_key[key] := (value, 1)node_for_freq[1][key] := (value, 1)remain == 0이라면node_for_freq[least_freq]에서 FIFO 순서로 한 요소를 제거(removed)하고,node_for_key에서 removed[0]에 해당하는 키를 삭제합니다.- 그렇지 않으면
remain := remain - 1로 감소시킵니다. least_freq := 1로 초기화합니다.
Python 구현 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
import collections
class LFUCache:
def __init__(self, capacity):
self.remain = capacity
self.least_freq = 1
self.node_for_freq = collections.defaultdict(collections.OrderedDict)
self.node_for_key = dict()
def _update(self, key, value):
_, freq = self.node_for_key[key]
self.node_for_freq[freq].pop(key)
if len(self.node_for_freq[self.least_freq]) == 0:
self.least_freq += 1
self.node_for_freq[freq+1][key] = (value, freq+1)
self.node_for_key[key] = (value, freq+1)
def get(self, key):
if key not in self.node_for_key:
return -1
value = self.node_for_key[key][0]
self._update(key, value)
return value
def put(self, key, value):
if key in self.node_for_key:
self._update(key, value)
else:
self.node_for_key[key] = (value,1)
self.node_for_freq[1][key] = (value,1)
if self.remain == 0:
removed = self.node_for_freq[self.least_freq].popitem(last=False)
self.node_for_key.pop(removed[0])
else:
self.remain -= 1
self.least_freq = 1
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3)
print(cache.get(2))
cache.put(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))
입력
cache.put(1, 1) cache.put(2, 2) cache.get(1) cache.put(3, 3) cache.get(2) cache.put(4, 4) cache.get(1) cache.get(3) cache.get(4)
출력
1 -1 1 -1 4
정리
이 구현에서 get과 put 연산은 모두 평균 O(1) 시간 복잡도로 동작합니다. collections.OrderedDict는 삽입 순서를 유지하면서 pop과 popitem 연산을 상수 시간에 수행할 수 있기 때문입니다. 또한 defaultdict를 활용하면 아직 존재하지 않는 빈도 그룹에 접근할 때도 별도의 초기화 없이 바로 사용할 수 있어 코드가 간결해집니다. LRU가 '최근 사용 여부'에 초점을 둔다면, LFU는 '누적 사용 빈도'를 기준으로 캐시를 교체한다는 점이 핵심적인 차이입니다.