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

目录
  • 目标
  • 什么是LRU
  • 简介
  • 硬件支持
    • 寄存器
  • 代码实现
    • 思路
    • 链表节点数据结构
    • 链表数据结构
    • LRUCache数据结构
  • 完整代码
  • 测试

目标

请你设计并实现一个满足 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 是最近最久未被访问的页,应将它置换出去。

代码实现

思路

  • Map 使用一个Map来保存当前所有节点的信息,键为key,值为链表中的具体节点。
  • 链表

    使用一个双向链表来记录当前节点的顺序。

链表节点数据结构

保存插入节点信息,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为节点的顺序链表。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.kvMap = new Map();
  this.linkLine = new linkLine();
};

get

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

/**
 * @param {number} key
 * @return {number}
 */
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 , 则应该 逐出 最久未使用的关键字。

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
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);
};

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.kvMap = new Map();
  this.linkLine = new linkLine();
};

/**
 * @param {number} key
 * @return {number}
 */
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;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
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缓存算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • JS 实现缓存算法的示例(FIFO/LRU)

    FIFO 最简单的一种缓存算法,设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 k-v . 使用了一个对象作为缓存,一个数组配合着记录添加进对象时的顺序,判断是否到达上限,若到达上限取数组中的第一个元素key,对应删除对象中的键值. /** * FIFO队列算法实现缓存 * 需要一个对象和一个数组作为辅助 * 数组记录进入顺序 */ class FifoCache{ constructor(limit){ this.limit = limit || 10 this

  • Nodejs基于LRU算法实现的缓存处理操作示例

    本文实例讲述了Nodejs基于LRU算法实现的缓存处理操作.分享给大家供大家参考,具体如下: LRU是Least Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,是根据页面调入内存后的使用情况进行决策了.由于无法预测各页面将来的使用情况,只能利用"最近的过去"作为"最近的将来"的近似,因此,LRU算法就是将最近最久未使用的页面予以淘汰. 可以用一个特殊的栈来保存当前正在使用的各个页面的页面号.当一个新的进程访问某页面时,便将

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

    目录 目标 什么是LRU 简介 硬件支持 寄存器 栈 代码实现 思路 链表节点数据结构 链表数据结构 LRUCache数据结构 完整代码 测试 目标 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构. 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 . void put(int key

  • JavaScript双向链表实现LFU缓存算法

    目录 什么是LFU 描述 解题思路 1.构造节点结构体 2.构造双向链表 3.编写链表头添加节点方法 4.编写删除节点方法 5.构造LRU缓存结构体 6.编写get方法 7.编写put方法 什么是LFU LFU(Least Frequently Used),最近最少使用策略,也就是说在一段时间内,数据被使用频次最少的,优先被淘汰.它是一种用于管理计算机内存的缓存算法,采用LFU算法的最简单方法是为每个加载到缓存的块分配一个计数器.每次引用该块时,计数器将增加一.当缓存达到容量并有一个新的内存块等

  • JavaScript使用Ajax上传文件的示例代码

    本文介绍了JavaScript使用Ajax上传文件的示例代码,分享给大家,具体如下: 实现文件的上传主要有两种方式: 使用form表单提交上传 html代码如下: <form id="uploadForm" enctype="multipart/form-data"> <input id="file" type="file" name="file"/> <button id=&

  • javascript实现Emrips反质数枚举的示例代码

    今天看到一个kata,提出一个"emirps"的概念:一个质数倒转后得到的是一个不同的质数,这个数叫做"emirps". 例如:13,17是质数,31,71也是质数,13和17是"emirps". 但是质数757,787,797是回文质数,这意味着反转的数字与原始数字相同,所以它们不被认为是"emirps". 题目要求写一个函数输入一个正整数n,返回小于n的"emirps"的个数,其中最大"emi

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • JAVA用递归实现全排列算法的示例代码

    求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i

  • c# 实现KMP算法的示例代码

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法).KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息.KMP算法的时间复杂度O(m+n) . 实现方式就不再这里献丑了,网上很多讲解,此处只是记录下c#实现的代码. public class KMP { public

  • python实现经典排序算法的示例代码

    以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想. 冒泡排序 内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序. def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(length - i - 1): if arr[j] > arr[j

  • JavaScript/TypeScript 实现并发请求控制的示例代码

    场景 假设有 10 个请求,但是最大的并发数目是 5 个,并且要求拿到请求结果,这样就是一个简单的并发请求控制 模拟 利用 setTimeout 实行简单模仿一个请求 let startTime = Date.now(); const timeout = (timeout: number, ret: number) => { return (idx?: any) => new Promise((resolve) => { setTimeout(() => { const compa

  • Python实现七大查找算法的示例代码

    查找算法 -- 简介 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素.     查找表(Search Table):由同一类型的数据元素构成的集合     关键字(Key):数据元素中某个数据项的值,又称为键值     主键(Primary Key):可唯一的标识某个数据元素或记录的关键字 查找表按照操作方式可分为:         1.静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是:         ①

随机推荐

其他