O(1) 시간 복잡도로 구현하는 LFU 캐시 설계 전략

Context

빈도 기반의 데이터 삭제가 필요한 LFU 캐시 구현의 복잡성. 단순 정렬 방식 사용 시 데이터 갱신과 삭제에 과도한 시간 소요. 동일 빈도 내에서 최근 사용 데이터를 관리해야 하는 추가 요구사항.

Technical Solution

• 빠른 데이터 접근을 위해 Key-Node 매핑 구조의 unordered_map 활용
• 빈도별로 노드를 그룹화하여 관리하는 freq 기반 Doubly Linked List 구조 설계
• 최소 빈도 데이터를 즉시 식별하여 삭제하기 위한 minFreq 추적 변수 도입
• 빈도 증가 시 기존 리스트에서 노드를 제거하고 상위 빈도 리스트의 전면에 삽입하는 전이 로직 구현
• 빈도 리스트가 비어있을 경우 minFreq 값을 1 증가시켜 Eviction 대상 리스트를 최신화하는 동적 관리 방식
• Doubly Linked List를 통해 노드 삭제와 삽입 작업을 모두 O(1) 시간 복잡도로 처리하는 구조

Key Takeaway

서로 다른 속성(빈도와 시간)을 동시에 관리해야 하는 경우, 다중 데이터 구조를 결합하여 각 속성의 최적 시간 복잡도를 달성하는 설계 원칙.