LRU 캐시의 복잡도

해시 맵과 이중 연결 리스트를 묶은 설계는 모든 연산을 평균 상수 시간에 처리합니다. 이 장에서는 그 한계가 어디서 나오는지, 메모리는 얼마나 드는지, 더 단순한 설계와 어떻게 다른지, 그리고 왜 Big-O만큼 적중률이 중요한지 살펴봅니다.

연산별 시간

리스트 연산은 포인터를 많아야 네 개 바꾸므로 최악의 경우에도 O(1)입니다. 해시 맵은 평균 O(1)이며, 충돌이 극단적이면 조회가 O(n)까지 나빠질 수 있고 크기 재조정 때문에 삽입은 엄밀한 상수가 아니라 분할 상환 상수입니다. 쓸 만한 해시 함수를 쓰면 실제로는 연산마다 메모리 접근 몇 번이면 끝납니다.

공간

캐시는 최대 capacity개의 항목을 담으므로 공간은 O(capacity)입니다. 다만 일반 딕셔너리보다 상수 배가 큽니다. 항목마다 맵 슬롯, 노드 객체, 포인터 두 개, 키에 대한 두 번째 참조가 필요합니다. Python에서 차이를 직접 볼 수 있습니다.

import sys

class Node:
    __slots__ = ("key", "value", "prev", "next")

class FatNode:
    def __init__(self):
        self.key = self.value = self.prev = self.next = None

slim, fat = Node(), FatNode()
print(sys.getsizeof(slim))                            # 예: 64바이트
print(sys.getsizeof(fat) + sys.getsizeof(fat.__dict__))  # 눈에 띄게 큼

정확한 숫자는 Python 버전마다 다르지만, __slots__는 노드당 메모리를 꾸준히 줄여 줍니다. OrderedDict와 functools.lru_cache는 연결 정보를 C로 관리하므로 더 가볍습니다.

단순한 설계가 느린 이유

처음 시도할 때는 흔히 키를 일반 리스트에 넣고 옮겨 다닙니다. Python 리스트에서 키를 찾아 지우는 데 O(n)이 들기 때문에 연산마다 선형 시간이 됩니다.

class NaiveLRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.order = []          # 가장 오래전 항목이 앞
        self.data = {}

    def get(self, key):
        if key not in self.data:
            return None
        self.order.remove(key)   # O(n) 탐색과 이동
        self.order.append(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.order.remove(key)
        elif len(self.data) >= self.capacity:
            del self.data[self.order.pop(0)]  # O(n) 이동
        self.order.append(key)
        self.data[key] = value

용량이 커질수록 차이가 커지는 모습을 작은 벤치마크로 확인할 수 있습니다.

import random
import timeit
from collections import OrderedDict

def ordered_ops(capacity, keys):
    cache = OrderedDict()
    for k in keys:
        if k in cache:
            cache.move_to_end(k)
        else:
            cache[k] = k
            if len(cache) > capacity:
                cache.popitem(last=False)

def naive_ops(capacity, keys):
    order, data = [], set()
    for k in keys:
        if k in data:
            order.remove(k)
        elif len(order) >= capacity:
            data.discard(order.pop(0))
        order.append(k)
        data.add(k)

keys = [random.randrange(4000) for _ in range(20000)]
for name, fn in [("OrderedDict", ordered_ops), ("list", naive_ops)]:
    seconds = timeit.timeit(lambda: fn(2000, keys), number=1)
    print(f"{name:12} {seconds:.3f}s")

다른 정책과 비교

CLOCK이나 표본 추출 LRU가 있는 이유는, 진짜 LRU는 읽을 때마다 공유 포인터를 고쳐야 해서 하드웨어나 동시성이 높은 소프트웨어에서는 비싸기 때문입니다. 정확한 최근 순서를 포기하는 대신 적중 비용을 줄입니다.

Big-O보다 적중률

좋은 설계는 모두 O(1)이므로, 실제로 차이를 만드는 것은 적중률입니다. LRU는 스택 알고리즘이라는 유용한 성질이 있습니다. 같은 요청 순서라면 더 큰 LRU 캐시가 더 작은 캐시보다 실패가 많아지는 일은 없습니다. FIFO에는 이 성질이 없습니다(벨레이디의 모순, Belady's anomaly). 용량을 정하기 전에 실제와 비슷한 작업량으로 적중률을 측정해 봅니다.

정리

• get과 put은 평균 O(1)이고, 리스트 부분은 최악에도 O(1)입니다.
• 공간은 O(capacity)이며, 노드와 포인터 때문에 항목당 부가 비용이 있습니다.
• 리스트나 전체 탐색 기반 설계는 O(n), 힙 기반 설계는 O(log n)입니다.
• 용량과 정책은 복잡도만이 아니라 측정한 적중률로 고릅니다.