首页 > 资讯 > 前端开发 > JavaScript >JavaScript双向链表实现LFU缓存算法

401

分享到

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

2024-04-02 19:04:59 401人浏览薄情痞子

摘要

目录什么是LFU描述解题思路1、构造节点结构体2、构造双向链表3、编写链表头添加节点方法4、编写删除节点方法5、构造LRU缓存结构体6、编写get方法7、编写put方法什么是LFU

什么是LFU

LFU（Least Frequently Used），最近最少使用策略，也就是说在一段时间内，数据被使用频次最少的，优先被淘汰。
它是一种用于管理计算机内存的缓存算法，采用LFU算法的最简单方法是为每个加载到缓存的块分配一个计数器。每次引用该块时，计数器将增加一。当缓存达到容量并有一个新的内存块等待插入时，系统将搜索计数器最低的块并将其从缓存中删除。

描述

请你为最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象

int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。

void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。

当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。

在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最近最久未使用的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个使用计数器。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路

1、构造节点结构体

保存对应的数据信息

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

2、构造双向链表

构造带有头尾节点的双向链表，head和tail为哨兵节点，不保存信息，仅用于标记头尾。

const LFULinkLine = function (node) {
  let head = new LFUNode("head");
  let tail = new LFUNode("tail");
  head.next = node;
  tail.pre = node;
  node.pre = head;
  node.next = tail;
  this.head = head;
  this.tail = tail;
};

3、编写链表头添加节点方法

将节点插入到链表的头结点之后，其他节点往后移。

LFULinkLine.prototype.addNode = function (node) {
  this.head.next.pre = node;
  node.pre = this.head;
  node.next = this.head.next;
  this.head.next = node;
};

4、编写删除节点方法

将节点从链表中删除。

LFULinkLine.prototype.removeNode = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};

5、构造LRU缓存结构体

构造LRU缓存结构体，具体信息如下代码，capacity用于保存最大缓存数，即该类的容量；num保存当前存储的数据量，用于判别是否超出最大容量；minFreq保存当前存储的数据中的最小频率，删除的时候需要优先删除频率最小的；kvMap保存节点详细信息，索引为节点的key值，查询可以直接从这里查出信息；freqMap保存对应频率的链表信息，索引为节点的freq（频率），删除的时候可以快速从这里获取需要删除节点的信息。


var LFUCache = function (capacity) {
  this.capacity = capacity;//最大缓存
  this.num = 0;//当前数目
  this.minFreq = 0;//当前最小频率
  this.kvMap = new Map();//保存节点信息
  this.freqMap = new Map();//保存对应频率的链表信息
};

6、编写get方法

get主要有以下两种情况：

（1）节点存在

通过kvMap获取到对应节点
将节点从freqMap中删除
判断是否需要修改minFreq
修改节点的freq
重新将节点插入freqMap
返回节点的value

（2）节点不存在
容量capacity为0或者kvMap中没有该节点信息，直接返回-1即可。


LFUCache.prototype.get = function (key) {
  if (this.capacity === 0) return -1;
  if (!this.kvMap.has(key)) return -1;
  //通过kvMap获取到对应节点
  let node = this.kvMap.get(key);
  let linkLine = this.freqMap.get(node.freq);
  //将节点从freqMap中删除
  linkLine.removeNode(node);
  //判断是否需要修改minFreq
  //清空了
  if (linkLine.head.next === linkLine.tail) {
    this.freqMap.delete(node.freq);
    if (this.minFreq == node.freq) this.minFreq++;
  }
  //修改节点的freq
  node.freq++;
  //重新将节点插入freqMap
  if (this.freqMap.has(node.freq)) {
    linkLine = this.freqMap.get(node.freq);
    linkLine.addNode(node);
  } else {
    this.freqMap.set(node.freq, new LFULinkLine(node));
  }
  //返回节点的value
  return node.val;
};

7、编写put方法

put操作主要有以下两种情况：

（1）更新

通过kvMap获取到对应节点
将节点从freqMap中删除
判断是否需要修改minFreq
更新节点信息
重新将节点插入freqMap

（2）存入

存入情况下又有两种情况：

容量已满

通过minFreq找到需要删除的节点
将节点从freqMap中删除
判断是否需要修改minFreq
将新节点插入freqMap
更新minFreq

容量未满

修改num
将新节点插入freqMap
更新minFreq


LFUCache.prototype.put = function (key, value) {
  if (this.capacity === 0) return;
  if (this.kvMap.has(key)) {
    //更新
    //通过kvMap获取到对应节点
    let node = this.kvMap.get(key);
    //将节点从freqMap中删除
    let linkLine = this.freqMap.get(node.freq);
    linkLine.removeNode(node);
    //判断是否需要修改minFreq
    if (linkLine.head.next === linkLine.tail) {
      if (this.minFreq == node.freq) this.minFreq++;
      this.freqMap.delete(node.freq);
    }
    //更新节点信息
    node.val = value;
    node.freq++;
    //重新将节点插入freqMap
    if (this.freqMap.has(node.freq)) {
      linkLine = this.freqMap.get(node.freq);
      linkLine.addNode(node);
    } else {
      linkLine = new LFULinkLine(node);
      this.freqMap.set(node.freq, linkLine);
    }
  } else {//存入
    if (this.capacity == this.num) {//存满
      //通过minFreq找到需要删除的节点
      let freq = this.minFreq;
      let linkLine = this.freqMap.get(freq);
      let node = linkLine.tail.pre;
      //将节点从freqMap中删除  
      linkLine.removeNode(node);
      this.kvMap.delete(node.key);
      //判断是否需要修改minFreq
      if (linkLine.head.next === linkLine.tail) {
        this.freqMap.delete(node.freq);
      }
    } else {
      //修改num
      this.num++;
    }
    //将新节点插入freqMap
    let node = new LFUNode(key, value, 0);
    this.kvMap.set(key, node);
    if (this.freqMap.has(0)) {
      let linkLine = this.freqMap.get(0);
      linkLine.addNode(node);
    } else {
      let linkLine = new LFULinkLine(node);
      this.freqMap.set(0, linkLine);
    }
    //更新minFreq
    this.minFreq = 0;
  }
};

代码

const LFUNode = function (
  key = "",
  val = "",
  freq = 0,
  pre = null,
  next = null
) {
  this.key = key;
  this.val = val;
  this.freq = freq;
  this.pre = pre;
  this.next = next;
};
const LFULinkLine = function (node) {
  let head = new LFUNode("head");
  let tail = new LFUNode("tail");
  head.next = node;
  tail.pre = node;
  node.pre = head;
  node.next = tail;
  this.head = head;
  this.tail = tail;
};
LFULinkLine.prototype.addNode = function (node) {
  this.head.next.pre = node;
  node.pre = this.head;
  node.next = this.head.next;
  this.head.next = node;
};
LFULinkLine.prototype.removeNode = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};


var LFUCache = function (capacity) {
  this.capacity = capacity;
  this.num = 0;
  this.minFreq = 0;
  this.kvMap = new Map();
  this.freqMap = new Map();
};


LFUCache.prototype.get = function (key) {
  if (this.capacity === 0) return -1;
  if (!this.kvMap.has(key)) return -1;
  let node = this.kvMap.get(key);
  let linkLine = this.freqMap.get(node.freq);
  linkLine.removeNode(node);
  //清空了
  if (linkLine.head.next === linkLine.tail) {
    this.freqMap.delete(node.freq);
    if (this.minFreq == node.freq) this.minFreq++;
  }
  node.freq++;
  if (this.freqMap.has(node.freq)) {
    linkLine = this.freqMap.get(node.freq);
    linkLine.addNode(node);
  } else {
    this.freqMap.set(node.freq, new LFULinkLine(node));
  }
  return node.val;
};


LFUCache.prototype.put = function (key, value) {
  if (this.capacity === 0) return;
  if (this.kvMap.has(key)) {
    //更新
    let node = this.kvMap.get(key);
    node.val = value;
    let linkLine = this.freqMap.get(node.freq);
    linkLine.removeNode(node);
    if (linkLine.head.next === linkLine.tail) {
      if (this.minFreq == node.freq) this.minFreq++;
      this.freqMap.delete(node.freq);
    }
    node.freq++;
    if (this.freqMap.has(node.freq)) {
      linkLine = this.freqMap.get(node.freq);
      linkLine.addNode(node);
    } else {
      linkLine = new LFULinkLine(node);
      this.freqMap.set(node.freq, linkLine);
    }
  } else {
    //存入
    if (this.capacity == this.num) {
      //存满
      let freq = this.minFreq;
      let linkLine = this.freqMap.get(freq);
      let node = linkLine.tail.pre;
      linkLine.removeNode(node);
      this.kvMap.delete(node.key);

      if (linkLine.head.next === linkLine.tail) {
        this.freqMap.delete(node.freq);
      }
    } else {
      this.num++;
    }
    let node = new LFUNode(key, value, 0);
    this.kvMap.set(key, node);
    if (this.freqMap.has(0)) {
      let linkLine = this.freqMap.get(0);
      linkLine.addNode(node);
    } else {
      let linkLine = new LFULinkLine(node);
      this.freqMap.set(0, linkLine);
    }
    this.minFreq = 0;
  }
};

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

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: JavaScript双向链表实现LFU缓存算法

本文链接: https://www.lsjlt.com/news/162478.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

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

目录什么是LFU描述解题思路1、构造节点结构体2、构造双向链表3、编写链表头添加节点方法4、编写删除节点方法5、构造LRU缓存结构体6、编写get方法7、编写put方法什么是LFU ...

99+

2024-04-02
python基于双向链表实现LFU算法

本文实例为大家分享了python实现LFU算法的具体代码，供大家参考，具体内容如下在第一节中实现了双向链表DoubleLinkedList类，上一节中基于双向链表实现了LRU算法，...

99+

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

目录目标什么是LRU简介硬件支持寄存器栈代码实现思路链表节点数据结构链表数据结构LRUCache数据结构完整代码测试目标请你设计并实现一个满足 LRU (最近最少使用) 缓存约束...

99+

2024-04-02
C++ 实现LRU 与 LFU 的缓存算法

目录一、LRU (Least Recently Used) 缓存二、LFU (Least Frequently Used) 缓存一、LRU (Least Recently Used...

99+

2024-04-02
JavaScript实现双向链表过程解析

目录一、什么是双向链表二、双向链表的封装三、双向链表的常用操作1、append（element)方法-----向列表尾部添加一个项2、将链表转化为字符串形式3、insert(posi...

99+

2024-04-02
Python实现双向链表

之前写的单向链表和环形链表都只是单向的，只能单向遍历，不能根据后面的节点获取前面的节点，除非进行反转操作。双向链表每个节点都有两个指针，这两个指针分别指向前后两个节点，这样就可以从...

99+

2024-04-02
Java实现双向链表

本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下 1、双向链表 1.1 双向链表的每个节点组成包含节点数据，上一个节点（pre），下一个节点（next） ...

99+

2024-04-02
LRU LFU TinyLFU缓存算法实例详解

目录简介一、LRU和LFU算法LRU算法LFU算法小结：二、TinyLFU三、Window-TinyLFU简介前置知识知道什么是缓存听完本节公开课，你可以收获掌握朴素LRU、...

99+

2024-04-02
Java实现常用缓存淘汰算法:FIFO、LRU、LFU

目录缓存淘汰算法FIFOLRULFU总结缓存淘汰算法在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。第一次请求时把计算好的结果存放在缓存中，下次遇到同...

99+

2024-04-02
C语言如何实现双向链表和双向循环链表

本文小编为大家详细介绍“C语言如何实现双向链表和双向循环链表”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言如何实现双向链表和双向循环链表”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。双向链表和双向循环链表...

99+

2023-06-16
java代码实现双向链表

本文实例为大家分享了双向链表java实现代码，供大家参考，具体内容如下一、双向链表简介 1、单链表的缺陷单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据...

99+

2024-04-02
Java如何实现双向链表

本篇内容介绍了“Java如何实现双向链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！1、双向链表1 双向链表的每个节点组成包含节点数据，上...

99+

2023-06-30
java双向链表怎么实现

Java中的双向链表可以通过定义一个Node类来实现，该类包含一个值和两个指针，分别指向前一个节点和后一个节点。具体实现如下： pu...

99+

2023-10-22

java
Python 实现双向链表（图解）

双向链表双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。双向链表基本方法实现（Python） 1...

99+

2023-01-31

双向链表 Python
python双向链表怎么实现

这篇文章主要介绍“python双向链表怎么实现”，在日常操作中，相信很多人在python双向链表怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”python双向链表怎么实现”的疑惑有所帮助！接下来，请跟...

99+

2023-06-30
C++怎么实现双向链表

这篇“C++怎么实现双向链表”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++怎么实现双向链表”文章吧。前言:前面文章分析...

99+

2023-06-29
python实现双向链表原理

双向链表一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另...

99+

2024-04-02
基于python实现双向链表

目录一、构建链表节点二、实现链表类三、测试逻辑在一些面试或者力扣题中都要求用双向链表来实现，下面是基于python的双向链表实现。一、构建链表节点 class Node: ...

99+

2024-04-02
C++代码实现双向链表

本文实例为大家分享了C++实现双向链表的具体代码，供大家参考，具体内容如下双向链表：两个指针域，一个指向前结点，一个指向后结点 list.h #pragma once #defin...

99+

2024-04-02
java模拟实现双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点下图是双...

99+

2024-04-02