文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

JavaScript双向链表实现LRU缓存算法的示例代码

2024-04-02 19:55

关注

目标

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

什么是LRU

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。

简介

最近最少使用算法(LRU)是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是,发生缺页中断时,选择未使用时间最长的页面置换出去。 从程序运行的原理来看,最近最少使用算法是比较接近理想的一种页面置换算法,这种算法既充分利用了内存中页面调用的历史信息,又正确反映了程序的局部问题。利用 LRU 算法对上例进行页面置换的结果如图1所示。当进程第一次对页面 2 进行访问时,由于页面 7 是最近最久未被访问的,故将它置换出去。当进程第一次对页面 3进行访问时,第 1 页成为最近最久未使用的页,将它换出。由图1可以看出,前 5 个时间的图像与最佳置换算法时的相同,但这并非是必然的结果。因为,最佳置换算法是从“向后看”的观点出发的,即它是依据以后各页的使用情况;而 LRU 算法则是“向前看”的,即根据各页以前的使用情况来判断,而页面过去和未来的走向之间并无必然的联系。

硬件支持

LRU 置换算法虽然是一种比较好的算法,但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最近最久未使用的页面,须有两类硬件之一的支持:寄存器或栈。

寄存器

为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为

R = Rn-1 Rn-2 Rn-3 … R2 R1 R0

图 2 某进程具有 8 个页面时的 LRU 访问情况

当进程访问某物理块时,要将相应寄存器的 R n -1 位置成 1。此时,定时信号将每隔一定时间(例如 100 ms)将寄存器右移一位。 如果我们把 n 位寄存器的数看做是一个整数, 那么,具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。图2示出了某进程在内存中具有 8 个页面,为每个内存页面配置一个 8 位寄存器时的 LRU 访问情况。这里,把 8 个内存页面的序号分别定为 1~8。由图可以看出,第 3 个内存页面的 R 值最小,当发生缺页时,首先将它置换出去。

图 3 用栈保存当前使用页面时栈的变化情况

可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号。假定现有一进程所访问的页面的页面号序列为:

4,7,0,7,1,0,1,2,1,2,6

随着进程的访问, 栈中页面号的变化情况如图 3 所示。 在访问页面 6 时发生了缺页,此时页面 4 是最近最久未被访问的页,应将它置换出去。

代码实现

思路

链表节点数据结构

保存插入节点信息,pre指向上一个节点,next指向下一个节点。

const linkLineNode = function (key = "", val = "") {
  this.val = val;
  this.key = key;
  this.pre = null;
  this.next = null;
};

链表数据结构

保存头结点head和尾结点tail。

const linkLine = function () {
  let head = new linkLineNode("head", "head");
  let tail = new linkLineNode("tail", "tail");
  head.next = tail;
  tail.pre = head;
  this.head = head;
  this.tail = tail;
};

链表头添加

将节点插入到头结点后面,修改头结点的next指向以及原本头结点的next节点的pre指向。

linkLine.prototype.append = function (node) {
  node.next = this.head.next;
  node.pre = this.head;
  this.head.next.pre = node;
  this.head.next = node;
};

链表删除指点节点

重新指向节点前后节点的next和pre指向。

linkLine.prototype.delete = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};

删除并返回链表的最后一个节点(非tail)

取到链表的最后一个节点(非tail节点),删除该节点并返回节点信息。

linkLine.prototype.pop = function () {
  let node = this.tail.pre;
  node.pre.next = this.tail;
  this.tail.pre = node.pre;
  return node;
};

打印链表信息

将链表的信息按顺序打印出来,入参为需要打印的属性。

linkLine.prototype.myConsole = function (key = 'val') {
  let h = this.head;
  let res = "";
  while (h) {
    if (res != "") res += "-->";
    res += h[key];
    h = h.next;
  }
  console.log(res);
};

LRUCache数据结构

capacity保存最大容量,kvMap保存节点信息,linkLine为节点的顺序链表。


var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.kvMap = new Map();
  this.linkLine = new linkLine();
};

get

如果关键字 key 存在于缓存中,则返回关键字的值,并重置节点链表顺序,将该节点移到头结点之后,否则返回 -1 。


LRUCache.prototype.get = function (key) {
  if (this.kvMap.has(key)) {
    let node = this.kvMap.get(key);
    this.linkLine.delete(node);
    this.linkLine.append(node);
    return node.val;
  }
  return -1;
};

put

如果关键字 key 已经存在,则变更其数据值 value ,并重置节点链表顺序,将该节点移到头结点之后;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity , 则应该 逐出 最久未使用的关键字。


LRUCache.prototype.put = function (key, value) {
  if (this.kvMap.has(key)) {
    let node = this.kvMap.get(key);
    node.val = value;
    this.linkLine.delete(node);
    this.linkLine.append(node);
  } else {
    let node = new linkLineNode(key, value);
    if (this.capacity == this.kvMap.size) {
      let nodeP = this.linkLine.pop();
      this.kvMap.delete(nodeP.key);
    }
    this.kvMap.set(key, node);
    this.linkLine.append(node);
  }
};

完整代码

const linkLineNode = function (key = "", val = "") {
  this.val = val;
  this.key = key;
  this.pre = null;
  this.next = null;
};

const linkLine = function () {
  let head = new linkLineNode("head", "head");
  let tail = new linkLineNode("tail", "tail");
  head.next = tail;
  tail.pre = head;
  this.head = head;
  this.tail = tail;
};

linkLine.prototype.append = function (node) {
  node.next = this.head.next;
  node.pre = this.head;
  this.head.next.pre = node;
  this.head.next = node;
};
linkLine.prototype.delete = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};
linkLine.prototype.pop = function () {
  let node = this.tail.pre;
  node.pre.next = this.tail;
  this.tail.pre = node.pre;
  return node;
};
linkLine.prototype.myConsole = function (key = 'val') {
  let h = this.head;
  let res = "";
  while (h) {
    if (res != "") res += "-->";
    res += h[key];
    h = h.next;
  }
  console.log(res);
};


var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.kvMap = new Map();
  this.linkLine = new linkLine();
};


LRUCache.prototype.get = function (key) {
  if (this.kvMap.has(key)) {
    let node = this.kvMap.get(key);
    this.linkLine.delete(node);
    this.linkLine.append(node);
    return node.val;
  }
  return -1;
};


LRUCache.prototype.put = function (key, value) {
  if (this.kvMap.has(key)) {
    let node = this.kvMap.get(key);
    node.val = value;
    this.linkLine.delete(node);
    this.linkLine.append(node);
  } else {
    let node = new linkLineNode(key, value);
    if (this.capacity == this.kvMap.size) {
      let nodeP = this.linkLine.pop();
      this.kvMap.delete(nodeP.key);
    }
    this.kvMap.set(key, node);
    this.linkLine.append(node);
  }
};

测试

var obj = new LRUCache(2);
obj.put(1, 1);
obj.put(2, 2);
console.log(obj.get(1)); //---> 1
obj.put(3, 3);
console.log(obj.get(2));//---> -1
obj.put(4, 4);
console.log(obj.get(1));//---> -1
console.log(obj.get(3));//---> 3
console.log(obj.get(4));//---> 4

到此这篇关于JavaScript双向链表实现LRU缓存算法的示例代码的文章就介绍到这了,更多相关JavaScript LRU缓存算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯