LeetCode 고급 - LRU 캐 시 메커니즘
11487 단어 LRU
당신 이 파악 한 데이터 구 조 를 활용 하여 LRU (최근 최소 사용) 캐 시 체 제 를 설계 하고 실현 합 니 다.데이터 get 을 가 져 오고 데 이 터 를 기록 하 는 put 를 지원 해 야 합 니 다.
데이터 get (key) 가 져 오기 - 키 (key) 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.데이터 put (key, value) 를 기록 합 니 다. - 키 가 존재 하지 않 으 면 데이터 값 을 기록 합 니 다.캐 시 용량 이 상한 선 에 이 르 렀 을 때 새 데 이 터 를 쓰기 전에 최근 에 가장 적 게 사용 한 데이터 값 을 삭제 하여 새로운 데이터 값 에 공간 을 남 겨 야 합 니 다.
진급:
당신 은 O (1) 시간 복잡 도 내 에 이 두 가지 조작 을 완성 할 수 있 습 니까?
예시:
LRUCache cache = new LRUCache( 2 /* */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 1
cache.put(3, 3); // 2
cache.get(2); // -1 ( )
cache.put(4, 4); // 1
cache.get(1); // -1 ( )
cache.get(3); // 3
cache.get(4); // 4
분석 은 먼저 아래 를 보고 싶 지 않 은 학생 들 을 위해 핵심 점 을 직접 제시한다.
1. 링크 드 HashMap 의 accessOrder 속성 치 를 true 2 로 재 작성 removeEldestEntry 방법
다음은 설명 입 니 다.
최근 에 안 드 로 이 드 를 배 웠 는데 LruCache 의 실현 을 보 니 내부 의 실제 핵심 은 링크 드 HashMap 을 유지 하 는 것 이 었 습 니 다. 그래서 API 를 찾 아 보 니 재 미 있 는 방법 을 발 견 했 습 니 다.
protected boolean removeEldestEntry(Map.Entry eldest)
공식 문서 에 다음 과 같이 적 혀 있다.
Returns true if this map should remove its eldest entry. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache: it allows the map to reduce memory consumption by deleting stale entries.
이것 이 바로 우리 가 LruCache 를 실현 하 는 데 필요 한 것 이 아 닙 니까? "용량 을 초과 한 후에 새로운 내용 을 추가 할 때 '가장 오래된 것' 을 제거 합 니 다."
공식 문서 에서 도 사용 예 시 를 제시 했다.
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
// 100 entrys, , 。
이 방법 이 있 으 면 우 리 는 약간의 보충 만 더 하면 큰 성 과 를 거 둘 수 있다.
링크 드 하 쉬 맵 의 지식 을 보충 해 야 합 니 다.
상세 한 분석 에 대해 서 는 한 편의 문장 을 추천 합 니 다.https://blog.csdn.net/justloveyou_/article / details / 71713781 로 분석 이 잘 되 어 있 습 니 다.링크 드 해시 맵 에는 다음 과 같은 구조 함수 가 있 습 니 다.
public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)
이 accessOrder 매개 변 수 는 교체 순 서 를 제어 합 니 다. true 는 방문 순서에 따라 교체 되 고 false 는 삽입 순서에 따라 교체 되 는 것 을 표시 합 니 다.
쉽게 말 하면 원래 LinkedHashMap 은 A - > B - > C 순 으로 옮 겨 다 니 는데 이때 B 를 방문 하고 D 를 추가 합 니 다.
따라서 저 희 는 LruCache 를 실현 하려 면 access Order = true 만 더 명령 하면 됩 니 다. 이때 최신 방문 / 추 가 된 것 은 항상 맨 끝 에 있 습 니 다. removeEldestEntry 방법 과 결합 하여 용량 에 도 착 했 을 때 가장 오래 방문 하지 않 은 내용 을 우선 삭제 합 니 다.
코드
class LRUCache {
// , LRUCache LinkedHashMap
// , , 。
// = = ,
// ,
// , ,
MapCache cache;
public LRUCache(int capacity) {
cache = new MapCache(capacity);
}
public int get(int key) {
return cache.getOrDefault(key,-1);
}
public void put(int key, int value) {
cache.put(key,value);
}
}
class MapCache extends LinkedHashMap<Integer, Integer> {
private int MAX;
// , accessOrder = true
MapCache(int max){
super(max,0.75f,true);
this.MAX = max;
}
protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
return size() > MAX;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
https://blog.csdn.net/whdAlive/article/details/81411800
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
프로그래머스 캐시(LV2)지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.