이번 글에서는 LFU(Least Frequently Used, 최소 사용 빈도) 캐시 시스템을 Python으로 구현하는 방법을 알아보겠습니다. LFU 캐시는 사용 빈도가 가장 낮은 데이터를 우선적으로 제거하는 캐시 교체 정책으로, 데이터베이스나 웹 서버 등 다양한 시스템에서 활용됩니다.
LFU 캐시의 주요 연산
구현해야 할 자료구조는 다음 두 가지 연산을 지원해야 합니다.
- get(key) – 키가 캐시에 존재하면 해당 값을 반환하고, 존재하지 않으면
-1을 반환합니다. - set(key, value) – 키가 아직 캐시에 없다면 새로운 키-값 쌍을 삽입합니다.
캐시가 최대 용량에 도달한 상태에서 새로운 요소를 삽입할 때는, 사용 빈도가 가장 낮은 요소를 먼저 제거해야 합니다. 만약 사용 빈도가 같은 요소가 여러 개라면, 가장 오래전에 삽입된 요소(FIFO 순서)를 제거합니다.
동작 예시
용량이 2인 LFUCache를 생성하고 다음과 같이 연산을 수행한다고 가정해 보겠습니다.
cache.set(1, 1); cache.set(2, 2); cache.get(1); cache.set(3, 3); cache.get(2); cache.set(4, 4); cache.get(1); cache.get(3); cache.get(4)
이때 출력 결과는 순서대로 1, -1, 1, -1, 4입니다. 각 단계에서 get 호출 시 해당 키의 빈도가 증가하고, 용량 초과 시 빈도가 가장 낮은 항목부터 제거되기 때문입니다.
구현 전략
효율적인 구현을 위해 두 개의 해시 맵을 활용합니다.
- node_for_freq: 사용 빈도(freq)를 기준으로 데이터를 그룹화하여 저장하는 맵입니다. 각 빈도 그룹 내에서는 삽입 순서를 유지하기 위해 OrderedDict를 사용합니다.
- node_for_key: 키를 기준으로 값과 빈도 정보를 함께 저장하는 맵입니다.
핵심 로직은 다음과 같습니다.
- 초기화 시 용량(capacity), 남은 공간(remain), 최소 빈도(least_freq = 1)를 설정합니다.
- _update(key, value): 기존 키의 빈도를 조회한 뒤 해당 빈도 그룹에서 제거하고, 빈도를 1 증가시켜 상위 그룹으로 이동시킵니다. 이때 최소 빈도 그룹이 비어 있으면 least_freq를 1 증가시킵니다.
- get(key): 키가 없으면 -1을 반환하고, 있으면 _update()를 호출해 빈도를 갱신한 후 값을 반환합니다.
- set(key, value): 기존 키라면 _update()로 갱신하고, 새 키라면 빈도 1 그룹에 추가합니다. 이때 remain이 0이면 최소 빈도 그룹에서 FIFO 순서로 요소를 제거하고, 그렇지 않으면 remain을 1 감소시킵니다. 마지막으로 least_freq를 1로 초기화합니다.
Python 코드 예제
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.remain = capacity
self.least_freq = 1
self.node_for_freq = defaultdict(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 set(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.set(1, 1)
cache.set(2, 2)
print(cache.get(1))
cache.set(3, 3)
print(cache.get(2))
cache.set(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1 -1 1 -1 4
정리
이 구현은 defaultdict와 OrderedDict를 조합하여 각 연산을 평균 O(1) 시간 복잡도로 처리합니다. OrderedDict의 popitem(last=False) 메서드를 활용하면 삽입 순서대로 가장 오래된 항목을 손쉽게 제거할 수 있어, LFU 정책에서 동일 빈도 항목 간의 FIFO 제거 규칙까지 깔끔하게 처리할 수 있습니다.