前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >js 实现 LFU 算法

js 实现 LFU 算法

作者头像
蓓蕾心晴
发布2022-09-24 14:55:27
1.6K0
发布2022-09-24 14:55:27
举报
文章被收录于专栏:前端小叙前端小叙

LFU 算法

代码语言:javascript
复制
/**
 * @param {number} capacity
 */
var LFUCache = function (capacity) {
    this.map = new Map();// 存放 key:node 的索引,便于快速访问节点
    this.freqArr = new Array() // 定义一个频次数组,存放一个双向链表
    this.capacity = capacity  // 可以保存的容量
    this.minFreq = 1 // 方便找到访问次数最小的双向链表,默认设置为 1
    this.freqArr.push(new DoubleLink())// 插入一个双向链表
    this.freqArr.push(new DoubleLink())// 插入一个双向链表,因为 minFreq 默认设置为了 1,所以要push两次
};

/** 
 * @param {number} key
 * @return {number}
 */
// 访问
LFUCache.prototype.get = function (key) {
    const node = this.map.get(key); // 获取双向链表的 node 节点
    if (node) {
        this._updateFreq(node) // 如果节点存在,则更新频次
        return node.value  // 并返回 node节点值
    }
    return -1 // 否则返回-1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
// 设置
LFUCache.prototype.put = function (key, value) {
    if (this.capacity <=0 ) return  // 如果容量设置为<=0,则直接退出
    const node = this.map.get(key) // 获取 node 节点
    if (node) { 
        // 如果节点值存在,则更新频次
        this._updateFreq(node)
        // 并设置节点的值为最新的值
        node.value = value
        return true
    }
    // 如果当前容量>=设定容量
    if (this.map.size >= this.capacity) {
        // 获取当前最小频次下双向链表中的最后一个节点,并删除
        const lastNode = this.freqArr[this.minFreq].pop()
        // 删除 map 维护的该节点的 key 
        this.map.delete(lastNode.key)
    }
    // 创建新的双向链表节点
    const newNode = new DoubleLinkNode(key, value)
    // 由于是新创建节点,则第一次频次为 1,获取频次为 1 的双向链表,并在最前面插入新节点
    this.freqArr[1].unshift(newNode)
    // 不管之前最小频次到几,这里重置为 1
    this.minFreq = 1
    // map 中新增 key:node 映射
    this.map.set(key, newNode)
};
// 更新节点频次
LFUCache.prototype._updateFreq = function (node) {
    // 获取节点频次
    const freq = node.freq
    // 给节点中的频次变量+1
    node.incFreq() 
    // 删除原频次对应的双向链表中的该节点
    this.freqArr[freq].del(node)
    // 获取+1 后的频次数
    const newFreq = freq + 1
    // 如果频次数组对应的新的频次数的索引下没有节点
    if (!this.freqArr[newFreq]) {
        // 则给该频次数下赋值为新的双向链表
        this.freqArr[newFreq] = new DoubleLink()
    }
    // 否则,直接获取对应频次数下的双向链表,并在开头插入新节点
    this.freqArr[newFreq].unshift(node)
    // 最小访问次数等于freq,并且freq的双向链表指向为空,证明需要更新最小访问次数为最新的访问次数,避免原频次下节点删除后对应的节点已不存在
    if (freq === this.minFreq && this.freqArr[freq].size === 0) {
        this.minFreq = newFreq
    }
}
// 双向链表节点
var DoubleLinkNode = function (key, value) {
    this.key = key
    this.value = value
    this.freq = 1
    this.prev = null
    this.next = null
}
// 更新双向链表节点的频次数,+1
DoubleLinkNode.prototype.incFreq = function () {
    this.freq++
}
// 双向链表
var DoubleLink = function () {
    this.head = new DoubleLinkNode(-1, -1) // 创建头部节点
    this.tail = new DoubleLinkNode(-1, -1) // 创建尾部节点
    this.head.next = this.tail // 将头部节点的下一个节点指针指向尾部节点
    this.tail.prev = this.head // 将尾部节点的上一个节点指针指向头部节点
    this.size = 0 // 由于只有头尾,还没有插入节点,size 设为 0
}
// 双向链表的开头插入新节点方法
DoubleLink.prototype.unshift = function (node) {
    const tmp = this.head.next
    this.head.next = node
    node.next = tmp
    node.prev = this.head
    tmp.prev = node
    this.size++ // 记得更改节点长度
}
// 双向链表删除节点方法
DoubleLink.prototype.del = function (node) {
    const prev = node.prev
    const next = node.next
    prev.next = next
    next.prev = prev
    delete node.prev
    delete node.next
    this.size-- // 记得更改节点长度
}
// 双向链表从默认删除节点并返回该节点的方法
DoubleLink.prototype.pop = function () {
    const lastNode = this.tail.prev
    this.del(lastNode)
    return lastNode
}
代码语言:javascript
复制
源代码链接:https://leetcode.cn/problems/lfu-cache/solution/javascriptban-jie-ti-si-lu-by-ityou-o-vuw5/
本文主要给该代码增加了注释,便于理解。
转载请注明出处:https://www.cnblogs.com/beileixinqing/p/16669653.html
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-09-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档