leetcode 146 문제 [LRU (최근 최소 사용) 캐 시 메커니즘] (js 최 적 해법 첨부!)

LEETcode 146. 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

문제 풀이 방향:
두 가지 문 제 를 알 아내 면 됩 니 다. put 작업 을 수행 할 때 주목 하 세 요.
1. 캐 시 데이터 의 변화
두 가지 상황 으로 나 뉜 다.
1. 캐 시 불만
명중 캐 시 (캐 시 에 이 값 이 존재 함) 는 캐 시 에 변화 가 없습니다.
캐 시 에 명중 하지 않 았 습 니 다 (캐 시 에 이 값 이 존재 하지 않 습 니 다). 캐 시 에 이 값 을 추가 합 니 다.
2. 캐 시가 가득 찼 습 니 다
명중 캐 시, 캐 시 변화 없 음
캐 시 에 명중 하지 않 았 습 니 다. 캐 시 끝의 값 을 삭제 한 후 캐 시 에 이 값 을 추가 합 니 다.
이상 의 분석 을 통 해 를 찾 으 려 면 두 가지 방법 이 생각 났 다.
(1) 캐 시 를 질서 있 게 합 니 다 (질서 화 는 정렬 과 관련 되 고 알고리즘 의 복잡 도 를 증가 하기 때문에 저 는 이 방법 을 사용 하지 않 습 니 다)
(2) 메모리 의 첫 번 째 숫자 부터 캐 시 끝의 값 을 추적 하 는 지침 을 설정 합 니 다.
2. 메모리 에 데 이 터 를 추가 할 때 메모리 의 변화
두 가지 경우 입 니 다. 1. 메모리 에 이 값 이 존재 하지 않 습 니 다 (새 데이터)
이 값 을 메모리 첫 번 째 에 직접 저장 합 니 다.
2. 메모리 에 이 값 이 이미 존재 합 니 다 (오래된 데이터)
메모리 의 중간 값 을 업데이트 하 는 순서 입 니 다. 규칙 은 변 경 된 이전 노드 의 다음 노드 를 이 값 의 다음 노드 로 설정 한 다음 이 값 을 메모리 첫 번 째 부분 에 두 는 것 입 니 다 (기본 링크 작업).
메모리 가 비어 있 는 상태 에서 다음 작업 을 연속 으로 수행 하 는 등 일부 특수 한 상황 을 고려 해 야 한다.

put(1, 1);
put(1, 1);

그래서 업 데 이 트 된 규칙 은 상기 상황 을 호 환 해 야 합 니 다.
get 을 실행 할 때 캐 시 에 get 데이터 가 존재 하면 캐 시 순 서 를 업데이트 합 니 다.
코드:

let LRUCache = function(capacity) {
    this.cacheSize = capacity;
    //      
    this.cacheIndex = 0;
    this.cacheSet = new Set();
    //      
    this.head = null;
    //      
    this.cacheShift = null;
    this.memory = {};
};

LRUCache.prototype.get = function(key) {
    let val;
    const { cacheSet, memory } = this;
    if (cacheSet.has(key)) {
        val = memory[key].value;
        console.log(memory[key].value)
        // get       
        if (memory[key].next == null) {
            return val;
        }
        if (memory.cacheShift === memory[key] && memory.cacheShift.next) {
            memory.cacheShift = memory.cacheShift.next;
        }
        this.memorySort(key);
    } else {
        val = -1;
        console.log(-1);
    }
    
    return val;
};

LRUCache.prototype.put = function(key, value) {
    const { cacheSet, memory } = this;

    if (this.cacheIndex < this.cacheSize) {
        !cacheSet.has(key) && this.cacheIndex++;
        cacheSet.add(key)
    } else {
        if (!cacheSet.has(key)) {
            cacheSet.delete(memory.cacheShift.key);
            memory.cacheShift.next && (memory.cacheShift = memory.cacheShift.next);
            cacheSet.add(key);
        }
    }

    //      
    if (memory.head) {
        //          
        if (!memory[key]) {
            memory[key] = {
                prev: memory.head,
                next: null
            }
            memory.head.next = memory[key];
            memory.head = memory[key];
        } else { //        
            if (memory.cacheShift === memory[key] && memory.cacheShift.next) {
                memory.cacheShift = memory[key].next;
            }
            this.memorySort(key);
        }
    } else {  //     ，         
        memory[key] = {
            prev: null,
            next: null
        };
        memory.cacheShift = memory.head = memory[key];
    }

    memory[key].key = key;
    memory[key].value = value;
};

LRUCache.prototype.memorySort = function(key) {
    const { memory } = this;
    // get          
    if (memory[key].next != null) {
        if (memory[key].prev != null) {
            memory[key].prev.next = memory[key].next;
        } else {    //      
            memory[key].next.prev = null;
        }
        memory[key].next.prev = memory[key].prev;
        memory[key].prev = memory.head;
        memory[key].next = null;
        memory.head.next = memory[key];
        memory.head = memory[key];
    } 
}

이상 은 내 가 처음 느끼 는 방법 이다.왜 첫 느낌 이 라 고 하 는 지, 우선 제목 요구 O(1) 의 복잡 도 때문에 나 는 js 에서 비교적 조작 하기 쉬 운 배열 을 사용 할 수 없다.기간, 대상 을 사용 할 수 없습니다. 대상 으로 캐 시 순 서 를 알 수 없 기 때 문 입 니 다.그래서 저 는 링크 의 조작 만 생각 할 수 있 습 니 다. 링크 를 사용 하면 각종 삭제 와 검 사 를 피 할 수 없 기 때문에 코드 가 복잡 할 것 입 니 다.
그러나 내 동료 한 명의 행동 은 나 를 놀 라 게 했다.다음 과 같다.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.map = new Map()
  }

  get(key) {
    let val = this.map.get(key)
    if (typeof val === 'undefined') { return -1 }
    this.map.delete(key)
    this.map.set(key, val)
    return val
  }

  put(key, value) {
    if (this.map.has(key)) { 
      this.map.delete(key) 
    }

    this.map.set(key, value)
    let keys = this.map.keys()
    while (this.map.size > this.capacity) { this.map.delete(keys.next().value) }
  }
}

여기 서 그 가 사용 하 는 것 은 map 인 데 왜 map 가능 합 니까?여기 서 분석 해 봐.map.keys().next() 그 가 1 위 를 차지 하 는 키 값 을 얻 을 수 있 습 니 다. map.put() 유사 한 배열 의 push 조작 을 하고 값 을 맨 위 에 저장 하 는 것 이 가장 관건 적 인 것 입 니 다. 바로 제 가 생각 하지 못 한 것 입 니 다.이렇게 되면 제거 할 수 있 는 정렬 이 고 map 에 대한 조작 복잡 도 는 O(1) 로 조작 대상 보다 빠르다.코드 와 그 아름다움 뿐만 아니 라 알고리즘 의 복잡 도도 가장 좋다.
감명: js 우 리 를 위해 많은 함 수 를 봉 장 했 습 니 다. 능숙 하 게 파악 하면 호랑이 에 게 날 개 를 달 수 있 습 니 다.