[250302] LFU Cache

An O(1) algorithm for implementing the LFU cache eviction scheme

논문은 모든 연산(삽입, 조회, 삭제)을 O(1) 시간 복잡도로 수행하는 LFU 알고리즘을 제시한다. 이를 위해 다음 데이터 구조를 사용한다:

빈도 리스트(Frequency List): 이중 연결 리스트로, 각 노드가 특정 접근 빈도(예: 1, 2, 3…)를 나타냅니다. 노드 리스트(Node List): 동일한 빈도를 가진 항목들을 연결하는 이중 연결 리스트. 해시 테이블: 키를 통해 항목에 O(1)로 접근. 구현 방식:

각 항목은 키, 값, 빈도, 그리고 빈도 리스트와 노드 리스트 내 포인터를 가짐. 항목 접근 시 빈도를 증가시키고, 해당 항목을 새 빈도 그룹으로 이동(O(1)). 캐시가 가득 차면 최소 빈도 리스트에서 항목을 제거(O(1)). 의사 코드(NEW-FREQ-NODE, NEW-LFU-ITEM, ACCESS, INSERT, GET-LFU-ITEM 등)를 통해 초기화, 빈도 업데이트, 항목 관리 과정을 상세히 설명. 시간 복잡도:

삽입, 조회, 삭제가 모두 이중 연결 리스트와 해시 테이블의 O(1) 연산으로 수행되므로 전체 복잡도가 O(1)이다.