LRU算法与LFU算法

article/2025/10/17 0:16:33

LRU算法

LRU是Least Recently Used的缩写，即最近最少使用算法，是操作系统中页面置换算法的一种，由于内存中存放的页数有限，所以将最近没有使用到的算法会移出内存。
LRU原理：
LRU原理如下图所示：
在这里插入图片描述
它会将最近访问的节点放在前面，将最近没有访问的节点放在后面。如果缓存空间满了，就会将最后一个节点删掉，并将新的节点添加到首部。

Java实现
对于链式存储的结构，使用到的集合有ArrayList和LinkedList，而ArrayList底层是基于数组的，对元素的移动花费的时间复杂度较高，所以使用LinkedList，基于链表形式的，并且是双向链表，因为要考虑删除节点。而链表的查找时间复杂度也高，但是可以通过使用hash进行快速定位。所以，LRU算法可以通过双向链表和hash来进行实现。

代码部分
手动实现双向链表：

import java.util.HashMap;
import java.util.Map;public class LRUCache {//定义map映射private Map<String, Node> map;//定义缓存容量private int capacity = 8;//缓存中当前有一个数据private int size = 0;//链表的头结点和尾结点private Node head, tail;//从缓存中读取数据public int get(String key) {Node node = map.get(key);//如果能找到，就将节点移动到链表头部，没有返回-1if (node != null) {moveToHead(node);return node.value;}return -1;}//将节点添加到缓存中public void put(String key, int value) {if(capacity == 0)   return;Node node = map.get(key);if (node != null) {//如果存在，就将这个点的值进行修改并移到链表头部node.value = value;moveToHead(node);return;}//如果不存在，先判断空间缓存空间是否足够if (size == capacity) {map.remove(tail.pre.key);deleteNode(tail.pre);size -= 1;}Node newNode = new Node(key, value);addToHead(newNode);map.put(key, newNode);size += 1;}//将节点移到头结点private void moveToHead(Node node) {deleteNode(node);addToHead(node);}//将节点添加到头部private void addToHead(Node node) {node.next = head.next;head.next.pre = node;node.pre = head;head.next = node;}//删除这个节点private void deleteNode(Node node) {node.pre.next = node.next;node.next.pre = node.pre;}public LRUCache(int capacity) {this.capacity = capacity;initLinkedList();map = new HashMap<>(capacity);size = 0;}//初始化链表private void initLinkedList() {head = new Node();tail = new Node();head.next = tail;tail.pre = head;}public LRUCache() {initLinkedList();map = new HashMap<>(this.capacity);}public static class Node {public Node pre;public Node next;public String key;public int value;public Node(String key, int value) {this.key = key;this.value = value;}public Node() {}}public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put("key1", 1);cache.put("key2", 2);System.out.println(cache.get("key2"));//21cache.put("key3", 3);System.out.println(cache.get("key1"));//32}}

调用LinkedList API进行实现

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class LRUCache {//定义map映射private Map<String, Node> map;//定义缓存容量private int capacity = 8;private LinkedList<Node> list = new LinkedList<>();//从缓存中读取数据public int get(String key) {Node node = map.get(key);//如果能找到，就将节点移动到链表头部，没有返回-1if (node != null) {list.remove(node);list.addFirst(node);return node.value;}return -1;}//将节点添加到缓存中public void put(String key, int value) {if(capacity == 0)   return;Node node = map.get(key);if (node != null) {//如果存在，就将这个点的值进行修改并移到链表头部node.value = value;list.remove(node);list.addFirst(node);return;}//如果不存在，先判断空间缓存空间是否足够if (list.size() == capacity) {//如果存在，要将map和LinkedList中的删掉map.remove(list.getLast().key);list.removeLast();}Node newNode = new Node(key, value);map.put(key, newNode);list.addFirst(newNode);}public LRUCache(int capacity) {this.capacity = capacity;//也是定义map的容量，其实这一步没必要map = new HashMap<>(capacity);}public LRUCache() {map = new HashMap<>(this.capacity);}public static class Node {public String key;public int value;public Node(String key, int value) {this.key = key;this.value = value;}public Node() {}}public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put("key1",1);cache.put("key2",2);System.out.println(cache.get("key2"));  //21cache.put("key3",3);System.out.println(cache.get("key1"));  //32}}

LFU算法

LFU是 Least Frequently Used 的缩写，即最近最少访问频率，也是操作系统中页面调换算法的一种，将最近使用频率最小，并且很长时间没使用的页面调出内存。

LFU原理
在这里插入图片描述
其中，一个map存储频率和节点的集合之间的关系，即 freq - list，另一个map存储key - node 之间的关系。从key - node 中读到节点，然后去 freq - list 中将节点添加到对应的list集合中

代码部分
由于对每一个频率都要创建一个链表来存储，所以这里直接使用 Java 中的 API 进行实现

package cache;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class LFUCache {private Map<String,Node> key_node;private Map<Integer, LinkedList<Node>> freq_list;private int capacity = 2;private int minFreq = 1;public int get(String key){//如果不包含这个数，返回-1if(!key_node.containsKey(key))  return -1;Node node = key_node.get(key);//获得节点的频率int freq = node.freq;//当前节点频率加1node.freq += 1;//从对应的集合中删除节点freq_list.get(freq).remove(node);//如果删除完节点为0，删除集合if(freq_list.get(freq).size() == 0){freq_list.remove(freq);if(freq == minFreq){minFreq += 1;}}LinkedList<Node> list = freq_list.getOrDefault(freq + 1, new LinkedList<Node>());list.addFirst(node);freq_list.put(freq + 1, list);return node.value;}public void put(String key,int value){if(capacity == 0)   return ;Node node = key_node.get(key);if(node != null){//获取当前节点的频率int freq = node.freq;node.freq += 1;node.value = value;//从对应的频率节点的集合中删除节点freq_list.get(freq).remove(node);//如果集合中没有了元素，就将集合删除if(freq_list.get(freq).size() == 0){freq_list.remove(freq);//如果删除的是最小的频次，就让最小的频次加1if(freq == minFreq){minFreq += 1;}}//将节点移动到下一个频率的节点集合中LinkedList<Node> list = freq_list.getOrDefault(freq + 1, new LinkedList<Node>());list.offerFirst(node);freq_list.put(freq + 1, list);key_node.put(key, node);}else {Node newNode = new Node(key,value,1);//如果缓存容量已经满了，需要将使用频率最低并且长时间没使用的数据删除if(key_node.size() == capacity){Node lastNode = freq_list.get(minFreq).pollLast();key_node.remove(lastNode.key);if(freq_list.get(minFreq).size() == 0){freq_list.remove(minFreq);}}//将新的节点添加到集合中key_node.put(key,newNode);LinkedList<Node> list = freq_list.getOrDefault(1, new LinkedList<Node>());list.offerFirst(newNode);freq_list.put(1,list);minFreq = 1;}}public LFUCache(int capacity) {this.capacity = capacity;key_node = new HashMap<>();freq_list = new HashMap<>();}public LFUCache() {key_node = new HashMap<>();freq_list = new HashMap<>();}public static class Node{public String key;public int value;public int freq;public Node() {}public Node(String key, int value, int freq) {this.key = key;this.value = value;this.freq = freq;}}public static void main(String[] args) {LFUCache cache = new LFUCache(2);cache.put("key1",1);    //1cache.put("key2",2);    //21cache.put("key3",3);    //32System.out.println(cache.get("key1"));System.out.println(cache.get("key2"));System.out.println(cache.get("key3"));cache.put("key1",1);    //13System.out.println(cache.get("key1"));System.out.println(cache.get("key2"));System.out.println(cache.get("key3"));cache.put("key2",2);    //21cache.put("key1",1);    //12}
}

http://chatgpt.dhexx.cn/article/dNBKsvOT.shtml

相关文章

【算法】LFU及其优化

【算法】LFU及其优化

文章目录 什么是LFU&#xff1f;设计思路代码实现&#xff08;基础版本&#xff09;参考论文代码实现&#xff08;优化版本&#xff09;区别 什么是LFU&#xff1f; LRU及其实现 上文讲解了LRU&#xff0c;他是一个基于最近是否被访问来做缓存淘汰的策略。 那么今天介绍一个新…
阅读更多...
LRU和LFU算法解析

LRU和LFU算法解析

文章目录 LRU和LFU算法解析LRULRU概念LRU算法实现LRU算法描述LRU算法图示LRU C代码代码测试 LFULFU概念LFU算法实现LFU算法描述LFU算法图示LFU C代码代码测试 总结 LRU和LFU算法解析 LRU LRU概念 LRU&#xff08;The Least Recently Used&#xff0c;最近最少未使用&#xf…
阅读更多...
LRU和LFU的区别

LRU和LFU的区别

对于web开发而言&#xff0c;缓存必不可少&#xff0c;也是提高性能最常用的方式。无论是浏览器缓存(如果是chrome浏览器&#xff0c;可以通过chrome:://cache查看)&#xff0c;还是服务端的缓存(通过memcached或者redis等内存数据库)。缓存不仅可以加速用户的访问&#xff0c;…
阅读更多...
LFU算法族：LFU算法

LFU算法族：LFU算法

LFU算法族相关文章目录汇总&#xff1a; LFU算法&#xff08;本文&#xff09;​​​​​​​ LFU-Aging算法 window-LFU算法 1、原理 LFU&#xff08;Least Frequently Used&#xff09;算法&#xff0c;即最少访问算法&#xff0c;根据访问缓存的历史频率来淘汰数据&…
阅读更多...
LFU算法详解

LFU算法详解

LFU算法&#xff1a;least frequently used&#xff0c;最近最不经常使用算法 对于每个条目&#xff0c;维护其使用次数 cnt、最近使用时间 time。 cache容量为 n&#xff0c;即最多存储n个条目。 那么当我需要插入新条目并且cache已经满了的时候&#xff0c;需要删除一个之…
阅读更多...
算法题就像搭乐高：手把手带你拆解 LFU 算法

算法题就像搭乐高：手把手带你拆解 LFU 算法

f学算法认准labuladong 东哥带你手把手撕力扣???? 点击下方卡片即可搜索???? PS&#xff1a;以后每篇文章最后&#xff0c;labuladong 都会推荐一些自己学过的优质技术专栏&#xff0c;供读者参考。 上篇文章 算法题就像搭乐高&#xff1a;手把手带你拆解 LRU 算法 写了…
阅读更多...
LRU LFU 概念、底层原理及其实现 超详细~

LRU LFU 概念、底层原理及其实现 超详细~

0. 前置提要 本篇约为8650字&#xff0c;阅读完需要约40~60分钟。主要介绍页面置换算法,LRU和LFU的原理及其实现&#xff0c;对应leetcode140和460&#xff0c;如果能给个赞就更好了^-^。 1.从内存置换算法说起 计算机的运行的程序和数据保存在内存中&#xff0c;内存的空间是有…
阅读更多...
如何实现LFU缓存（最近最少频率使用）

如何实现LFU缓存（最近最少频率使用）

目录 1.什么是LFU缓存&#xff1f; 2.LFU的使用场景有哪些&#xff1f; 3.LFU缓存的实现方式有哪些&#xff1f; 4.put/get 函数实现具体功能 1.什么是LFU缓存&#xff1f; LFU缓存是一个具有指定大小的缓存&#xff0c;随着添加元素的增加&#xff0c;达到容量的上限&…
阅读更多...
LFU缓存策略算法

LFU缓存策略算法

在之前的文章中&#xff0c;我们介绍了如何设计一个LRU算法–如何设计LRU Cache算法&#xff0c;今天我们再聊一聊另一种缓存策略LFU。目前博主个人博客已经搭建发布&#xff0c;后期相关文章也会发布在上面&#xff0c;大家有兴趣可以去上面学习&#xff0c;点击即可前往文青乐…
阅读更多...
国内编程学习网站

国内编程学习网站

在本文中&#xff0c;我们介绍了来自两岸三地的编程学习网站&#xff0c;通过它们&#xff0c;不仅可以一窥国内App开发的发展现状&#xff0c;而且这些网站各有特点&#xff0c;无论是主打游戏学习还是视频学习&#xff0c;对于想要自学的开发者而言&#xff0c;都是个好去处。…
阅读更多...
如何高效的自学编程

如何高效的自学编程

现在的社会对于IT人才的需求越来越大&#xff0c;程序员的薪资水平在各个行业中都算比较高的。所以很多人都想往IT行业发展&#xff0c;已经身处这个行业的人也需要不断的学习新的知识&#xff0c;因为IT行业的技术更新实在是太快了&#xff0c;不像传统行业那样是越老越吃香。…
阅读更多...
电脑编程自学(零基础自学编程怎么入门)

电脑编程自学(零基础自学编程怎么入门)

电脑编程自学入手：确定编程学习的方向。编程语言有多种：php，C++，C，C#，JAVA，Python等，每种语言都有不同的优缺点，可以根据自己的兴趣方向选择一门编程语言作为自己的学习目标。 基础阶段的语法学习。学习任何一门编程语言，都需要掌握其编程的语法规则，可以通过阅读一…
阅读更多...
自学编程的 6 个致命误区

自学编程的 6 个致命误区

嗨&#xff0c;小伙伴们大家好&#xff0c;我是沉默王二。本篇文章来和大家聊聊自学编程中的一些误区——这是我在 B 站上看了羊哥的一期视频后有感而发的文章。因为确实有很多读者也曾私信问过我这些方面的问题&#xff0c;很有代表性&#xff0c;所以我就结合自己的亲身体会来…
阅读更多...
java编程自学app_Java编程自学软件

java编程自学app_Java编程自学软件

Java编程自学软件是是一款Java学习软件。Java编程自学软件为用户提供Java语言&#xff0c;ISh和SQL 数据库编程等技术方便用户学习Java知识。有需要自学Java编程的小伙伴们可在华军软件园下载Java编程自学软件。 Java编程自学软件功能特色 专业化、具体化。 有真正意义上的实战…
阅读更多...
c语言 软件编程入门自学,软件编程入门自学

c语言 软件编程入门自学,软件编程入门自学

文章目录[隐藏] 软件编程入门自学 作为界面&#xff0c;MFC方便上手&#xff0c;QT也不错。您好&#xff0c;自学编程建议从C语言开始。可以说60%~80%的程序员都是从C语言开始的。 众所周知&#xff0c;编程语言分为结构化编程语言和面向对象编程语言。结构化编程语言比面向对象…
阅读更多...
自学编程，收藏好这7个免费网站，可省你上万块钱的学费

自学编程，收藏好这7个免费网站，可省你上万块钱的学费

如果你要自学编程&#xff0c;一定要收藏好这7个网站&#xff0c;上面免费的优质教程很多&#xff0c;完全可以省去你上万块钱的学费&#xff01; 话不多说&#xff0c;直接上干货&#xff01; 第一个&#xff0c;W3school 一个主打图文教程的网站&#xff0c;不管是前端开发…
阅读更多...
蛙跳算法优化VMD参数，惩罚系数，分解层数，matlab语言 ，最小包络熵为适应度函数。

蛙跳算法优化VMD参数，惩罚系数，分解层数，matlab语言 ，最小包络熵为适应度函数。

蛙跳算法优化VMD参数&#xff0c;惩罚系数&#xff0c;分解层数&#xff0c;matlab语言 &#xff0c;最小包络熵为适应度函数。
阅读更多...
粒子群算法(6)-----几个适应度评价函数

粒子群算法(6)-----几个适应度评价函数

下面给出几个适应度评价函数&#xff0c;并给出图形表示 头几天机子种了病毒&#xff0c;重新安装了系统&#xff0c;不小心把程序全部格式化了&#xff0c;痛哭&#xff01;&#xff01;&#xff01;没办法&#xff0c;好多程序不见了&#xff0c;现在把这几个典型的函数重新编…
阅读更多...
粒子群算法几个适应度评价函数

粒子群算法几个适应度评价函数

http://blog.csdn.net/niuyongjie/article/details/1619496 粒子群算法(6)-----几个适应度评价函数 标签&#xff1a; 算法图形function 2007-05-21 16:28 37960人阅读 评论(25) 收藏 举报 分类&#xff1a; 粒子群算法研究&#xff08;8&#xff09; 版权声明&#xff1…
阅读更多...
遗传算法优化LSTM网络结构(实现自动根据适应度函数：即准确率来全局搜索最佳网络结构)：主要被优化参数：网络层数，每层的神经元个数，全连接的层数，全连接层的神经元个数。代码有详细注解

遗传算法优化LSTM网络结构(实现自动根据适应度函数：即准确率来全局搜索最佳网络结构)：主要被优化参数：网络层数，每层的神经元个数，全连接的层数，全连接层的神经元个数。代码有详细注解

代码视频链接：https://www.bilibili.com/video/BV19q4y1Q7DR/ 代码效果图： 1.优化参数 本文优化的是LSTM的层数参数和各层神经元参数，其中包含了lstm层和Dense层，其中我们规定了神经网络的层数不超过3层，每层的神经元个数在[32,256]之间。 2.注意事项 2.1.本文的遗传算…
阅读更多...
推荐文章

Copyright @ 2022~2023