LFU(최소 자주 사용됨) 캐시 시스템에 대한 데이터 구조를 구현하려고 한다고 가정합니다. 다음 작업을 지원해야 합니다.
-
get(key) - 키가 캐시에 있으면 키 값을 가져오는 데 도움이 됩니다. 그렇지 않으면 -1을 반환합니다.
-
set(key, value) - 키가 아직 없는 경우 값을 설정하거나 삽입하는 데 사용됩니다.
캐시가 최대 용량에 도달하면 새 요소를 삽입하기 전에 가장 적게 사용되는 요소를 무효화해야 합니다.
따라서 LFUCache가 용량 2로 초기화되고 이러한 메서드를 호출하면 cache.set(1, 1); 캐시.세트(2, 2); 캐시.get(1); 캐시.세트(3, 3); 캐시.get(2); 캐시.세트(4, 4); 캐시.get(1); 캐시.get(3); 캐시.get(4); 그러면 출력은 각각 1,−1,1,−1,4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
초기화 프로그램은 용량 값을 사용합니다.
-
남아 있음 :=용량
-
최소 주파수 :=1
-
node_for_freq :=삽입 주문에 따라 데이터를 보관할 맵
-
node_for_key :=새 지도
-
_update() 함수를 정의합니다. 여기에는 키, 값이 필요합니다.
-
x, 주파수 :=node_for_key[키]
-
키에 해당하는 node_for_freq[freq]에서 요소 삭제
-
node_for_freq[least_freq]의 크기가 0과 같으면
-
최소 주파수 :=최소 주파수 + 1
-
-
node_for_freq[freq+1, key] :=값, 주파수+1
-
node_for_key[키] :=값, 주파수+1
-
get() 함수를 정의합니다. 열쇠가 필요합니다
-
node_for_key에 없는 키가 0이 아니면
-
반환 -1
-
-
값 :=node_for_key[키, 0]
-
_update(키, 값)
-
반환 값
-
set() 함수를 정의합니다. 여기에는 키, 가치가 필요합니다.
-
node_for_key의 키가 0이 아닌 경우
-
_update(키, 값)
-
-
그렇지 않으면
-
node_for_key[키] :=값,1
-
node_for_freq[1, 키] :=값, 1
-
나머지가 0과 같으면
-
제거됨 :=fifoorder의 node_for_freq[least_freq]에서 하나의 요소 삭제
-
node_for_key에서 삭제 요소는 제거된 키에 해당합니다[0]
-
-
그렇지 않으면
-
남아 있음 :=남아 있음 - 1
-
-
-
최소 주파수 :=1
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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))
입력
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