当前位置: 首页 > news >正文

数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

关于LRU缓存

  • LRU - Lease Recently Used 最近使用

  • 如果内存优先,只缓存最近使用的,删除 ‘沉睡’ 数据

  • 核心 api: get set

  • 分析

    • 使用哈希表来实现, O(1)
    • 必须是有序的,常用放在前面,沉睡放在后面, 即:有序,可排序
    • 这样 {} 不符合要求;Map是可以排序的,按照设置顺序
class LRUCache {private length: numberprivate data: Map<any, any> = new  Map()constructor(length: number) {if (length < 1) throw new Error('invalid length')this.length = length}set(key: any, value: any) {const data = this.dataif (data.has(key)) {data.delete(key)}data.set(key, value)if (data.size > this.length) {// 如果超出了容量,则删除 Map 最老的元素const delKey = data.keys().next().valuedata.delete(delKey)}}get(key: any): any {const data = this.dataif(!data.has(key)) return nullconst value = data.get(key)data.delete(key)data.set(key, value) // 保持最新的return value}
}const lruCache = new LRUCache(2)
lruCache.set(1, 1) // { 1=1 }
lruCache.set(2, 2) // { 1=1,  2=2 }
lruCache.get(1) // 1 {2=2, 1=1}
lruCache.set(3,3) // {1=1, 3=3}
lruCache.get(2) // null
lruCache.set(4,4) // {3=3, 4=4}
lruCache.get(1) // null
lruCache.get(3) // {4=4, 3=3}
lruCache.get(4) // 4 {3=3, 4=4}

不用 Map 如何实现 LRU 缓存

  • 注意:有序
  • 结合 Object + Array
  • 将Array改造成双向链表
const obj1 = {value: 1, key: 'a'}
const obj2 = {value: 2, key: 'b'}
const obj3 = {value: 3, key: 'c'}const data = [obj1, obj2, obj3]
const map =  {'a': obj1, 'b': obj2, 'c': obj3}
  • 上述数据结构很精妙
interface IListNode {value: anykey: stringprev?: IListNodenext?: IListNode
}export default class LRUCache {private length: numberprivate data: { [key: string]: IListNode } = {}private dataLength: number = 0private listHead: IListNode | null = nullprivate listTail: IListNode | null = nullconstructor(length: number) {if (length < 1) throw new Error('invalid length')}private moveToTail(curNode: IListNode) {const tail = this.listTailif (tail === curNode) return// 1. 让 pre next 断绝与 curNode的关系const preNode = curNode.prevconst nextNode = curNode.nextif (prevNode) {if (nextNode) {preNode.next = nextNode} else {delete prevNode.next}}if (nextNode) {if (prevNode) {nextNode.prev = prevNode} else {delete nextNode.prev}if (this.listHead === curNode) this.listHead = nextNode}// 2. 让 curNode 断绝与 prev, next的关系delete curNode.prevdelete curNode.next// 3. 在list 末尾重新建立 curNode 的新关系if (tail) {tail.next = curNodecurNode.prev = tail}this.listTail = curNode}private tryClean() {while(this.dataLength > this.length) {const head = ths.listHeadif (!head) throw new Error('head is null')const headNext = head.nextif (!headNext) throw new Error('headNext is null')// 1. 断绝head和next的关系delete headNext.prevdelete head.next// 2. 重新赋值 listHeadthis.listHead = headNext// 3. 清理 data, 重新计数delete this.data[head.key]this.dataLength -= 1}}get(key: string):any {const data = this.dataconst curNode  = data[key]if (!curNode) return nullif (this.listTail === curNode) {reutrn curNode.vlaue}// curNode 移动到末尾this.moveToTail(curNode)}set(key: string, value: any) {const data = this.dataconst curNode  = data[key]if (!curNode) {// 新增数据const newNode: IListNode = {key, value}// 移动到末尾this.moveToTail(newNode)data[key] = newNodethis.dataLength ++if (this.dataLength === 1) this.listHead = newNode} else {// 修改现有数据curNode.value = value// 移动到末尾this.moveToTail(curNode)}// 长度超过了,则需要清理this.tryClean()}
}

功能性测试

const lruCache = new LRUCache(2)
lruCache.set('1', 1) // { 1=1 }
lruCache.set('2', 2) // { 1=1,  2=2 }
lruCache.get('1') // 1 {2=2, 1=1}
lruCache.set('3',3) // {1=1, 3=3}
lruCache.get('2') // null
lruCache.set('4',4) // {3=3, 4=4}
lruCache.get('1') // null
lruCache.get('3') // {4=4, 3=3}
lruCache.get('4') // 4 {3=3, 4=4}
  • 数据结构设计:data 和 list 分别存储什么
  • 双向链表的操作非常繁琐,代码很容易写错, 不易调试
  • 链表 node 要存储 node.key, 否则需要遍历 data 删除

相关文章:

数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

关于LRU缓存 LRU - Lease Recently Used 最近使用 如果内存优先&#xff0c;只缓存最近使用的&#xff0c;删除 ‘沉睡’ 数据 核心 api: get set 分析 使用哈希表来实现, O(1)必须是有序的&#xff0c;常用放在前面&#xff0c;沉睡放在后面, 即&#xff1a;有序&#xff0…...

Matlab | 基于二次谱提取地震数据的地震子波

本文通过地震数据二次谱求取地震子波谱&#xff0c;具体方法如下&#xff1a; MATLAB代码实现如下&#xff1a; function w SndSpecExtWavelet(x, M) % 功能&#xff1a;基于二次谱提取输入地震数据data的地震子波wavelet % Extracting Wavelet from Input Seismic Dat…...

利用远程IO模块,轻松驾驭食品包装生产的自动化

常见的自动化包装系统&#xff0c;它的核心部分通常由一系列高端设备组成&#xff0c;包括自动开箱机、自动封箱机、自动捆扎机、装箱机器人、码垛机器人等。这些设备协同工作&#xff0c;形成一条高效运转的生产线&#xff0c;从开箱到装箱&#xff0c;再到码垛&#xff0c;每…...

华为OD机考算法题:计算最大乘积

题目部分 题目计算最大乘积难度易题目说明给定一个元素类型为小写字符串的数组&#xff0c;请计算两个没有相同字符的元素长度乘积的最大值。 如果没有符合条件的两个元素&#xff0c;返回 0。输入描述输入为一个半角逗号分隔的小写字符串的数组&#xff0c;2< 数组长度<…...

用友 GRP-U8 存在sql注入漏洞复现

0x01 漏洞介绍 用友 GRP-U8 license_check.jsp 存在sql注入&#xff0c;攻击者可利用该漏洞执行任意SQL语句&#xff0c;如查询数据、下载数据、写入webshell、执行系统命令以及绕过登录限制等。 fofa&#xff1a;app”用友-GRP-U8” 0x02 POC: /u8qx/license_check.jsp?kj…...

vue页面el-tab控件标签栏加入按钮功能

vue页面el-tab控件标签栏加入按钮功能 显示效果为&#xff1a; <el-tabs v-model"activeName" type"border-card" style"margin-right:5px"><el-tab-pane label"模型管理" name"first"><span slot"l…...

vue3使用ref和reactive

Vue 3引入了两个新的API&#xff0c;ref和reactive&#xff0c;用于创建响应式对象。这两个方法都位于Vue.prototype上&#xff0c;因此可以在组件实例中直接使用。 ref ref函数用于创建一个响应式引用对象。这个函数可以接受一个普通的变量或对象作为参数&#xff0c;并返回…...

7 款用于解锁iPhone密码的苹果解锁软件

无法访问您的 iPhone 一定是最烦人的情况之一。 即使您以前从未遇到过这种情况&#xff0c;做好准备总是一个好主意&#xff0c;而不是在它发生时感到无助。事实上&#xff0c;这种情况经常发生并且可能有很多实例&#xff0c;例如忘记密码或购买锁定的二手 iPhone。 牢记 Ap…...

.jnlp

首先配置电脑的java环境。 百度搜索jre下载&#xff0c;会有很多结果&#xff0c;一般选择官网进行下载。 下载正确的jre版本。 我的电脑是windows 64位&#xff0c;根据你自己电脑的情况选择版本进行下载。不懂自己电脑是多少位的可以看下一步。 查看电脑是64位还是32…...

Linux启动之uboot分析

Linux启动之uboot分析 uboot是什么&#xff1f;一、补充存储器概念1.存储器种类1.norflash - 是非易失性存储器&#xff08;也就是掉电保存&#xff09;2.nandflash - 是非易失性存储器&#xff08;也就是掉电保存&#xff09;3.SRAM - 静态随机访问存储器 - Static Random Acc…...

element -plus table的二次封装

个人简介 博主写了对element-plus的表格和表单的封装 大家支持一下 [表格]https://gitee.com/childe-jia/table-vue3 [表单] https://gitee.com/childe-jia/form-render Introduction WHAT i-table 基于元素 element-plus&#xff0c;但不限于元素 element-plus 组件。在完…...

windows应用软件扫描报告 不告谱 要钱

chatGPT开路&#xff0c;帮找。 当你想要查找Windows软件的漏洞而不涉及查看源代码时&#xff0c;你可以使用一些专门设计用于扫描漏洞的工具。这些工具通常会检查已安装的软件和操作系统的漏洞&#xff0c;并提供建议或修补程序。以下是一些可以用于查找Windows软件漏洞的工具…...

世界前沿技术发展报告2023《世界航空技术发展报告》(七)机载系统与武器技术

&#xff08;七&#xff09;机载系统与武器技术 1.机载系统技术1.1 美国推进商用5G技术在航空装备中的应用1.2 人工智能技术在航空中的应用日益增多1.3 美国空军研究实验室推出综合座舱感知技术1.4 美国空军为固定翼飞机驾驶员选定新一代头盔1.5 美国DARPA探索通过机载光能量中…...

JAVA 学习笔记——抽象类

概念&#xff1a; 当定义一个类时&#xff0c;常常需要定义一些成员方法来描述类的行为特征&#xff0c;但有时这些方法的实现方式是无法确定的。 例如&#xff0c;前面在定义 Animal 类时&#xff0c;walk()方法用于描述动物的行走行为&#xff0c;但是针对不同的动物&#…...

磁盘调度算法之先来先服务(FCFS),最短寻找时间优先(SSTF),扫描算法(SCAN,电梯算法),LOOK调度算法

目录 1.一次磁盘读/写操作需要的时间1.寻找时间2.延迟时间3.传输时间4.影响读写操作的因素 2.磁盘调度算法1.先来先服务(FCFS)1.例题2.优缺点 2.最短寻找时间优先(SSTF)1.例题2.优缺点3.饥饿的原因 3.扫描算法(SCAN)1.例题2.优缺点 4.LOOK调度算法1.例题2.优点 5.循环扫描算法(…...

postman接口测试—Restful接口开发与测试

开发完接口&#xff0c;接下来我们需要对我们开发的接口进行测试。接口测试的方法比较多&#xff0c;使用接口工具或者Python来测试都可以&#xff0c;工具方面比如之前我们学习过的Postman或者Jmeter &#xff0c;Python脚本测试可以使用Requests unittest来测试。 测试思路…...

RK3568-emmc控制器

emmc控制器 eMMC主机控制器具有高度的可配置性和可编程性&#xff0c;并提供高性能的eMMC主机控制器&#xff0c;以AXI作为数据传输的总线接口&#xff08;主接口&#xff09;&#xff0c;以AHB作为其从接口。 它支持以下功能&#xff1a; - 支持SD-HCI主机版本4模式或更少的 …...

02-操作符及类型转换与控制流程语句

操作符及类型转换与控制流程语句 1.操作符1.1.算数运算符正常的数据运算进行数据运算时&#xff0c;除外&#xff0c;其他运算符可以自动将字符串数字隐形转成数字 1.2.一元运算符JavaScript中有8种常用的一元运算符 (正号)1.的第一种用法:进行数据相加2.放在数据的前面&#…...

判断一个字符串中是否包含中文字符

下面我将为你提供三种常用的方法&#xff1a; 方法一&#xff1a;使用正则表达式 import java.util.regex.Pattern; import java.util.regex.Matcher;public class ChineseCharacterChecker {public static boolean containsChineseCharacters(String input) {String regex …...

软件测试面试怎样介绍自己的测试项目?会问到什么程度?

想知道面试时该怎样介绍测试项目&#xff1f;会问到什么程度&#xff1f;那就需要换位思考&#xff0c;思考HR在这个环节想知道什么。 HR在该环节普遍想获得的情报主要是下面这2个方面&#xff1a; 1&#xff09;应聘者的具体经验和技术能力&#xff0c; 2&#xff09;应聘者的…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...