집 > 기사 > 웹 프론트엔드 > 캐싱 알고리즘을 구현한 JS의 예

캐싱 알고리즘을 구현한 JS의 예

亚连원래의: 2018-05-25 16:39:171484검색

이 글에서는 주로 JS(FIFO/LRU)에서 구현한 캐싱 알고리즘의 예를 소개하고 참고하겠습니다.

FIFO

가장 간단한 캐싱 알고리즘으로 캐시 상한을 설정합니다. 캐시 상한에 도달하면 선입선출 전략에 따라 제거되고 새로운 k-v가 추가됩니다.

객체는 캐시로 사용됩니다. 배열은 레코드가 객체에 추가되는 순서와 일치하여 상한에 도달했는지 확인합니다. 상한에 도달하면 배열의 첫 번째 요소 키가 가져옵니다. 이는 객체의 키 값을 삭제하는 것과 같습니다.

/**
 * FIFO队列算法实现缓存
 * 需要一个对象和一个数组作为辅助
 * 数组记录进入顺序
 */
class FifoCache{
  constructor(limit){
    this.limit = limit || 10
    this.map = {}
    this.keys = []
  }
  set(key,value){
    let map = this.map
    let keys = this.keys
    if (!Object.prototype.hasOwnProperty.call(map,key)) {
      if (keys.length === this.limit) {
        delete map[keys.shift()]//先进先出，删除队列第一个元素
      }
      keys.push(key)
    }
    map[key] = value//无论存在与否都对map中的key赋值
  }
  get(key){
    return this.map[key]
  }
}

module.exports = FifoCache

LRU

LRU(최근에 사용됨, 최근에 사용됨) 알고리즘입니다. 이 알고리즘의 관점은 캐시가 가득 차면 최근에 액세스한 데이터가 나중에 액세스될 가능성이 더 크다는 것입니다.

알고리즘 구현 아이디어: 이중 연결 리스트의 데이터 구조를 기반으로, 가득 차 있지 않을 때 새로운 k-v가 연결 리스트의 선두에 배치되고, 캐시에 있는 k-v를 얻을 때마다 k-v가 캐시가 가득 차면 마지막 캐시가 먼저 제거됩니다.

이중 연결 목록의 특징은 헤드 및 테일 포인터가 있다는 것입니다. 각 노드에는 각각 이전 노드와 다음 노드를 가리키는 prev(선행자) 및 다음(후행) 포인터가 있습니다.

핵심 사항: 이중 연결 리스트 삽입 과정에서 순서 문제에 주의하세요. 연결 리스트를 연속적으로 유지하면서 포인터가 먼저 처리되어야 하며, 마지막으로 원래 포인터가 새로 삽입된 요소를 가리킨다는 점에 주의하세요. 코드 구현은 제가 댓글에서 설명한 순서에 주의하세요!

class LruCache {
  constructor(limit) {
    this.limit = limit || 10
    //head 指针指向表头元素，即为最常用的元素
    this.head = this.tail = undefined
    this.map = {}
    this.size = 0
  }
  get(key, IfreturnNode) {
    let node = this.map[key]
    // 如果查找不到含有`key`这个属性的缓存对象
    if (node === undefined) return
    // 如果查找到的缓存对象已经是 tail (最近使用过的)
    if (node === this.head) { //判断该节点是不是是第一个节点
      // 是的话，皆大欢喜，不用移动元素，直接返回
      return returnnode ?
        node :
        node.value
    }
    // 不是头结点，铁定要移动元素了
    if (node.prev) { //首先要判断该节点是不是有前驱
      if (node === this.tail) { //有前驱，若是尾节点的话多一步，让尾指针指向当前节点的前驱
        this.tail = node.prev
      }
      //把当前节点的后继交接给当前节点的前驱去指向。
      node.prev.next = node.next
    }
    if (node.next) { //判断该节点是不是有后继
      //有后继的话直接让后继的前驱指向当前节点的前驱
      node.next.prev = node.prev
      //整个一个过程就是把当前节点拿出来，并且保证链表不断，下面开始移动当前节点了
    }
    node.prev = undefined //移动到最前面，所以没了前驱
    node.next = this.head //注意！！！ 这里要先把之前的排头给接到手！！！！让当前节点的后继指向原排头
    if (this.head) {
      this.head.prev = node //让之前的排头的前驱指向现在的节点
    }
    this.head = node //完成了交接，才能执行此步！不然就找不到之前的排头啦！
    return IfreturnNode ?
      node :
      node.value
  }
  set(key, value) {
    // 之前的算法可以直接存k-v但是现在要把简单的 k-v 封装成一个满足双链表的节点
    //1.查看是否已经有了该节点
    let node = this.get(key, true)
    if (!node) {
      if (this.size === this.limit) { //判断缓存是否达到上限
        //达到了，要删最后一个节点了。
        if (this.tail) {
          this.tail = this.tail.prev
          this.tail.prev.next = undefined
          //平滑断链之后，销毁当前节点
          this.tail.prev = this.tail.next = undefined
          this.map[this.tail.key] = undefined
          //当前缓存内存释放一个槽位
          this.size--
        }
        node = {
          key: key
        }
        this.map[key] = node
        if(this.head){//判断缓存里面是不是有节点
          this.head.prev = node
          node.next = this.head
        }else{
          //缓存里没有值，皆大欢喜，直接让head指向新节点就行了
          this.head = node
          this.tail = node
        }
        this.size++//减少一个缓存槽位
      }
    }
    //节点存不存在都要给他重新赋值啊
    node.value = value
  }
}

module.exports = LruCache

구체적인 아이디어는 얻으려는 노드가 헤드 노드가 아닌 경우(즉, 이미 가장 최근에 사용한 노드이고 노드 위치를 이동할 필요가 없는 경우) 먼저 다음 작업을 수행해야 한다는 것입니다. 링크 끊기 작업을 원활하게 하고 포인터 사이의 관계를 처리하고 꺼내기 연결 리스트에 삽입하려면 프런트 노드로 이동해야 합니다.

위 내용은 제가 여러분을 위해 정리한 내용입니다. 앞으로 도움이 되길 바랍니다.

캐싱 알고리즘을 구현한 JS의 예

관련 기사