JavaScript에서 간단한 LRU 캐시 구현

소프트웨어 엔지니어로서의 여행 중에, 당신은 이러한 상황을 만날 수 있다. 모든 가능한 데이터 구조는 이채로운 기회를 가질 수 있다.그 중 하나는 다른 사람만큼 주목받지 못하지만, 어떤 경우에도 마찬가지로 유용할 수 있다. (더 유용하지 않다면.)논의된 데이터 구조는 LRU 캐시입니다.

LRU 캐시란?
LRU Cache 또는 최근에 가장 적게 사용된 캐시는 최근에 추가되거나 액세스한 순서대로 정보를 저장하는 데이터 구조입니다.
유행하는 비유는 옷장 안의 옷걸이이다. 옷을 잘 입고 걸 때 옷걸이 오른쪽에 놓는다.시간의 흐름에 따라 옷걸이의 왼쪽을 살펴보면 어떤 옷을 오랫동안 입지 않았는지 쉽게 분별할 수 있다.

내가 왜 써야 되지?
LRU 캐시를 사용하여 다른 데이터 구조에 비해 정보를 저장하는 주요 이점은 기능 증대입니다.
컴퓨터 과학 용어의 캐시는 메모리의 빠른 접근 위치에 저장된 최근에 사용된 블록으로 여겨지며, 같은 데이터를 중복 추출할 때 더욱 빠른 성능을 낼 수 있다.
만약 우리가 LRU 캐시를 고려한다면, 이것은 사용자가 데이터베이스를 통해 정보를 검색하는 응용 프로그램에서 매우 유용할 것이다.일반적으로 사용자가 어떤 내용을 찾을 때마다 응용 프로그램은 ping 데이터베이스를 요청하는데 귀중한 시간이 걸린다.그러나 최근에 검색한 항목을 LRU 캐시에 저장하면 캐시에 검색한 항목이 있는지 신속하게 확인할 수 있고, 존재한다면 더 짧은 시간 안에 검색할 수 있습니다.매우 유용하다.

괜찮은 것 같은데, 우리는 어떻게 하나를 지을까요?
이렇게 물어봐서 반갑습니다!전통적으로 LRU 캐시는 해시 맵과 더블 체인 테이블을 결합시켜 구축된 것으로 일정한 O(1) 시간 내에 프로젝트의 빠른 검색과 최근 사용과 최근에 사용한 최소한의 항목의 검색을 유지할 수 있다.
그러나 소규모 프로젝트에서 처음부터 LRU 캐시를 신속하게 실현하는 것에 관심이 있다면, 자바스크립트 클래스와 Map() 대상만 사용하면 LRU 캐시를 구축할 수 있으며, 그 대가로 검색이 실행될 때이다.
최소한/최근에 사용한 기능은 변하지 않을 것이며, 이것은 실천에서 데이터 구조의 관건적인 부분이다.이 버전의 LRU 캐시를 만드는 방법에 관심이 있다면 계속 읽어 보십시오.

1. 클래스와 구조 함수 구축
다음과 같이 JavaScript ES6 클래스를 사용하여 LRU 캐시를 구축합니다.

class LRUCache {

}

이 클래스에서는 LRU 캐시의 모든 인스턴스가 동일한 구조를 유지하도록 구조 함수를 설정합니다.Google 캐시는 용량을 매개 변수로 합니다. 이것은 캐시가 저장소에서 최근에 가장 적게 사용한 항목을 삭제하기 전에 최대 크기로 증가할 수 있도록 설정하여 공간을 절약하고 구조를 질서정연하게 유지합니다.
또한 이 구조 함수를 사용하여 캐시 자체를 설정하고 JavaScript를 사용하여 객체를 매핑합니다.

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

}

JavaScript 맵이 키와 값의 삽입 순서를 유지하기 때문에 여기서 Map 객체를 사용합니다.이것은 우리를 위해 대부분의 일을 해 주었다.

2. 캐시를 구축하는 Get 및 Put 방법
현재, 우리는 클래스에서 두 가지 중요한 함수를 실현할 것이다. 그것이 바로 Get과 Put이다. 이 두 함수는 각각 하나의 값을 검색하고 캐시에 키/값 쌍을 삽입할 것이다.
Get부터 시작하겠습니다.

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

  // Implementing Get method
  get(key) {
    if (!this.cache.has(key)) return undefined;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

}

우리가 방금 한 일을 분석해 봅시다.

지도에 열쇠가 있는지 검사합니다.없으면 "undefined"를 되돌려줍니다. (이것은 검색에 실패한 모든 되돌려주는 값일 수도 있습니다. 예를 들어 -1이나 오류 메시지일 수도 있습니다.)

다음에 이 키와 관련된 값을 가져와 이 변수에 분배하는 변수'val'을 설명합니다.

캐시에서 키/값 쌍을 제거한 다음 다시 설정합니다.우리의 지도는 우리가 물건을 삽입하는 순서를 유지하기 때문에, 이것은 우리가 검색한 키/값을 가장 앞쪽 (최근에 사용한) 위치로 되돌려줍니다.

이 방법을 호출하는 모든 프로그램에서 사용할 수 있도록 이 값을 되돌려줍니다.

이것이 바로 얻는 방법의 전부입니다!
이제 Put 접근 방식을 구현합니다.

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

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  // Implementing Put method
  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

}

다음 단계로 분해합니다.

첫 번째 줄은 키가 지도에 존재하는지 확인하고 존재하면 삭제한다.전화를 걸다.delete () 가 존재하면 키/값 쌍을 삭제하고, 존재하지 않으면 정의되지 않은 것으로 되돌려줍니다.

현재 캐시가 최대 용량인 경우(cache.size === this.capacity)this.cache.keys().next().valueiterator 대상을 사용하여 맵의 첫 번째 키를 가져와 매개 변수로 전달this.cache.delete(). 그런 다음 Put 전송 메서드의 매개 변수를 사용하여 캐시에 새 키/값 쌍을 설정합니다.

현재 최대 용량에 도달하지 못하면 평소와 같이 새 키/값 쌍만 추가할 수 있습니다.

이게 우리가 설정한 방법이야!

3. GetLeastTrecent 및 GetMostTrecent 구현 방법
이때 LRU 캐시의 기본 기능을 만들었지만 전체 데이터 구조를 얻으려면 아직 한 걸음 더 가야 한다.최근에 사용한(LRU) 또는 최근에 사용한(MRU) 값을 검색할 수 있습니다!
이를 위해 맵을 배열로 변환한 다음 배열의 첫 번째 값(LRU)과 마지막 값(MRU)을 각각 검색합니다.

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

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

  // Implement LRU/MRU retrieval methods
  getLeastRecent() {
    return Array.from(this.cache)[0];
  }

  getMostRecent() {
    return Array.from(this.cache)[this.cache.size - 1];
  }

}

갈게요!원하는 경우 Map concept의 동일한 배열을 사용하여 최근에 가장 적게 사용한 두 번째, 최근에 사용한 세 번째 등을 찾을 수 있습니다.
그것은 우리의 LRU 캐시입니다!
만약 당신이 이미 여기까지 읽었다면, 시간을 내서 나의 댓글을 확인해 주셔서 매우 감사합니다.
나는 이것이 데이터 구조를 배우고 이해하려고 하는 사람들이나 자바스크립트로 그것을 실현하려고 하는 사람들에게 도움이 되기를 바란다.😄