c语言编程笔录

首页 >   > 笔记大全

笔记大全

JavaScript怎么实现LRU算法

更新时间：2023-10-05
前言： LRU（Least Recently Used）算法是一种常用的缓存淘汰策略，用于解决缓存容量有限情况下的数据替换问题。LRU算法的思想是根据数据的使用历史来进行淘汰，即将最近最少使用的数据替换出去，以保留最常使用的数据。在JavaScript中实现LRU算法，可以借助对象和链表的数据结构，通过记录访问时间和访问频率，实现对缓存数据的管理和替换。 第一段： LRU算法需要存储访问过的数据，并按照访问时间顺序进行排序以判断最近最少使用的数据。在JavaScript中，我们可以使用一个对象和一个双向链表来实现这样的数据结构。对象用于存储缓存的键值对，链表则用于记录访问时间和访问频次。

使用对象和链表实现缓存数据结构

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = {};
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key) {
    if (key in this.cache) {
      const node = this.cache[key];
      this.moveToHead(node);
      return node.value;
    }
    return -1;
  }

  put(key, value) {
    if (key in this.cache) {
      const node = this.cache[key];
      node.value = value;
      this.moveToHead(node);
    } else {
      const node = new Node(key, value);
      this.cache[key] = node;
      this.addToHead(node);
      if (Object.keys(this.cache).length > this.capacity) {
        const removedNode = this.removeTail();
        delete this.cache[removedNode.key];
      }
    }
  }

  moveToHead(node) {
    this.removeNode(node);
    this.addToHead(node);
  }

  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  addToHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  removeTail() {
    const tailNode = this.tail.prev;
    this.removeNode(tailNode);
    return tailNode;
  }
}

const cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
console.log(cache.get(1)); // 1
第二段： 在LRUCache类中，首先定义了两个辅助节点head和tail，它们并不存储实际的缓存数据，只是作为链表的头尾节点。head节点始终指向最近被访问的节点，而tail节点指向最近最少被访问的节点。

实现LRU缓存的get和put方法

get(key) {
  if (key in this.cache) {
    const node = this.cache[key];
    this.moveToHead(node);
    return node.value;
  }
  return -1;
}

put(key, value) {
  if (key in this.cache) {
    const node = this.cache[key];
    node.value = value;
    this.moveToHead(node);
  } else {
    const node = new Node(key, value);
    this.cache[key] = node;
    this.addToHead(node);
    if (Object.keys(this.cache).length > this.capacity) {
      const removedNode = this.removeTail();
      delete this.cache[removedNode.key];
    }
  }
}
第三段： 在get方法中，如果缓存中存在对应的key，则将该节点移到链表头部，并返回节点的值；否则返回-1。在put方法中，如果缓存中已存在对应的key，则更新节点的值，并将节点移到链表头部；如果缓存已满，则移除链表尾部的节点，并删除对应的缓存条目；最后，创建新节点，并添加至链表头部。

LRU算法的时间复杂度和空间复杂度分析

实现LRU算法的时间复杂度如下： - get操作的时间复杂度是O(1)，由于使用了哈希表来存储缓存数据，通过键来快速查找对应的节点。 - put操作的时间复杂度是O(1)，同样依赖于哈希表的快速查找能力，而链表的插入和删除操作都是常数时间。 空间复杂度是O(capacity)，由于依赖于缓存的容量上限。 总结： LRU算法是一种常用的缓存淘汰策略，通过保留最近最常使用的数据来提高缓存的命中率。在JavaScript中，可以使用对象和链表的数据结构来实现LRU算法，通过记录访问时间和访问频率，实现对缓存数据的管理和替换。使用这种实现方式，可以快速地进行缓存的查找、插入和删除操作，提高了LRU算法的效率。

图文推荐