Javascript 手写 LRU 算法

更新日期: 2022-09-30阅读: 880标签: 算法

LRU 是 Least Recently Used 的缩写,即最近最少使用。作为一种经典的缓存策略,它的基本思想是长期不被使用的数据,在未来被用到的几率也不大,所以当新的数据进来时我们可以优先把这些数据替换掉。


一、基本要求

  1. 固定大小:限制内存使用。
  2. 快速访问:缓存插入和查找操作应该很快,最好是 O(1) 时间。
  3. 在达到内存限制的情况下替换条目:缓存应该具有有效的算法来在内存已满时驱逐条目。


二、数据结构

下面提供两种实现方式,并完成相关代码

2.1 Map

在 Javascript 中,Map 的 key 是有序的,当迭代的时候,他们以插入的顺序返回键值。结合这个特性,我们也通过 Map 实现 LRU 算法。

2.2 Doubly Linked List

我们也可通过双向链表(Doubly Linked List)维护缓存条目,通过对链表的增、删、改实现数据管理。为确保能够从链表中快速读取某个节点的数据,我们可以通过 Map 来存储对链表中节点的引用。


三、Map 实现

在 初始化时 完成两件事情:

  1. 配置存储限制,当大于此限制,缓存条目将按照最近读取情况被驱逐。
  2. 创建一个用于存储缓存数据的 Map 。

在 添加数据 时:

  1. 判断当前存储数据中是否包含新进数据,如果存在,则删除当前数据
  2. 判断当前存储空间是否被用尽,如果已用尽则删除 Map 头部的数据。
    map.delete(map.keys().next().value)
  3. 插入新数据到 Map 的尾部

基于 Javascript Map 实现 LRU,代码如下:

class LRUCache {
    size = 5
    constructor(size) {
        this.cache = new Map()
        this.size = size || this.size
    }

    get(key) {
        if (this.cache.has(key)) {
            // 存在即更新
            let temp = this.cache.get(key)
            this.cache.delete(key)
            this.cache.set(key, temp)
            return temp
        }
        return null
    }

    set(key, value) {

        if (this.cache.has(key)) {
            this.cache.delete(key)
        }

        if (this.cache.size >= this.size) {
            this.cache.delete(this.cache.keys().next().value)
        }

        this.cache.set(key, value)
    }
}


四、双向链表实现

4.1 定义节点类

包含 prev,next,data 三个属性,分别用以存储指向前后节点的引用,以及当前节点要存储的数据。

{
    prev: Node
    next: Node
    data: { key: string, data: any}
}

4.2 定义链表类

包含 head、tail 属性,分别指向链表的 头节点 和 尾节点

当从链表中读取数据时,需要将当前读取的数据移动到链表头部;添加数据时,将新节点插入到头部;当链表节点数量大于限定的阀值,需要从链表尾部删除节点。

{
    head: Node
    next: Node
    moveNodeToHead(node)
    insertNodeToHead(node)
    deleteLastNode()
}

4.3 定义 LRU 类

为 LRU 定义属性:linkLine 用以存储指向链表的引用;size 用以配置存储空间大小限制;
为简化从链表中查找节点,再定义 map 属性,用以存储不同键指向链表节点的引用。

定义成员方法,set(key,value) 用以添加数据,get(key) 读取一条数据。

4.4 set(key,value)

  1. 如果 map 中存在当前 key,则修改当前节点的值,然后从链表中把当前节点移动到链表头部;
  2. 否则:
    1. 判断当前链表节点数量是否达到了存储上线,如果是,则删除链表尾部的节点。同时从 map 中移除相应的节点引用;
    2. 创建新节点,然后插入到链表头部,并添加 map 引用。

4.5 get(key)

如果 map 中存在当前 key,从链表中读取节点,将其移动到链表头部,并返回结果,否则返回空。

{
    linkLine: LinkLine
    map: Map
    size: Number
    set(key, value)
    get(key)
}

4.6 代码实现

class LinkNode {
    prev = null
    next = null
    constructor(key, value) {
        this.data = { key, value }
    }
}

class LinkLine {

    head = null
    tail = null

    constructor() {
        const headNode = new LinkNode('head', 'head')
        const tailNode = new LinkNode('tail', 'tail')

        headNode.next = tailNode
        tailNode.prev = headNode

        this.head = headNode
        this.tail = tailNode
    }

    moveNodeToFirst(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
        this.insertNodeToFirst(node)
    }

    insertNodeToFirst(node) {
        const second = this.head.next
        this.head.next = node
        node.prev = this.head
        node.next = second
        second.prev = node
    }

    delete(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
    }

    deleteLastNode() {
        const last = this.tail.prev
        this.tail.prev = last.prev
        last.prev.next = this.tail
        return last
    }
}

class LRUCache {
    linkLine = null
    map = {}
    size = 5

    constructor(size) {
        this.size = size || this.size
        this.linkLine = new LinkLine
    }

    get(key) {
        let value
        if (this.map[key]) {
            const node = this.map[key]
            value = node.value
            this.linkLine.moveNodeToFirst(node)
        }
        return value
    }

    set(key, value) {
        if (this.map[key]) {
            const node = this.map[key]
            node.value = value
            this.linkLine.moveNodeToFirst(node)
        } else {
            // 删除最后一个元素
            if (Object.keys(this.map).length >= this.size) {
                const lastNode = this.linkLine.deleteLastNode()
                delete this.map[lastNode.data.key]
            }

            const newNode = new LinkNode(key, value)
            this.linkLine.insertNodeToFirst(newNode)
            this.map[key] = newNode
        }       
    }
}

来源:https://gauliang.github.io/blogs/2022/lru-algorithm/

链接: https://fly63.com/article/detial/12187

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!