当前位置：首页 > 编程日记 > 正文

LRU算法 -- 链表完整实现

编程日记 2024-04-09 11:30:00

LRU算法(Least Recently Used) 算是我们经常遇到的一种淘汰算法，其中内存管理模块进行内存页回收时有用到，针对不经常使用的内存页，LRU淘汰策略能够将该内存页回收给操作系统。

属于我们操作系统设计中的时间局部性原理，最长时间未被访问的数据优先淘汰，当内存中已存在的数据再次被访问时，则进行热度的提升。

本文为了巩固数据结构相关知识，特使用链表数据结构方式完整实现LRU链表的功能。关于数据结构和算法相关的学习导图可以借鉴数据结构和算法导图

实现算法思路：

   LRU 功能的实现:1. 已有链表中存在 待插入元素，则将该元素在链表中删除，并头插法到链表头节点2. 已有链表中不存在 待插入元素：a. 若 LRU 容量已满，则删除尾元素，头插当前元素b. 若 LRU 容量未满，则直接头插法当前元素

以上实现使用其他的线性表数据结构（栈、队列、数组）均能够实现，链表的实现方式如下：

#include <iostream>using namespace std;typedef int DataType;/*节点类*/
class Node{public:DataType val;Node *next;
};class List{
private:int maxSize;int length;Node *head;public:List();List(int size);~List();void insertElementBegin(DataType x); //头插法建立链表bool findElement(DataType x);        //查找链表中是否存在元素x,存在则返回true，不存在则返回falsevoid deleteElementEnd();             //删除链表的最后一个节点bool deleteElem(DataType x);         //删除链表中值为x的节点，删除成功则返回true,不存在则返回falsebool isEmpty();                      //判断链表是否为空，是则返回true,否则返回falsebool isFull();                       //判断链表是否满，是则返回true,否则返回falsevoid printAll();                     //打印链表中的元素，链表长度，LRU长度void * findElemOptim(DataType x);       //针对此应用的优化，查找,返回指定元素的前一个节点的指针void deleteElemOptim(void * node);     //针对此应用的优化，删除
};List::List(){head = new Node;head -> next = NULL;this -> length = 0;this -> maxSize = 10;
}List::List(int size) {head = new Node;head -> next = NULL;this -> length = 0;this -> maxSize = size;
}List::~List() {Node* p, *tmp;p = head;while(p -> next) {tmp = p -> next;p -> next = p -> next -> next;delete tmp;}delete head;this -> head = NULL;this -> length = 0;
}void List::insertElementBegin(DataType x) {Node *p = new Node;p -> val = x;p -> next = head -> next;head -> next = p;this -> length ++;
}bool List::findElement(DataType x) {Node *p = head;while(p -> next != NULL) {if(p -> val == x) {return true;}p = p -> next;}return false;
}void List::deleteElementEnd() {if(head -> next == NULL) {return;}Node *tmp;Node *p = head;while(p -> next != NULL && p -> next -> next != NULL) {p = p -> next;}tmp = p -> next;p -> next = tmp -> next;this -> length --;delete tmp;
}bool List::deleteElem(DataType x) {Node *p = head;Node *tmp;while(p -> next != NULL) {if(p -> next -> val == x) {tmp = p -> next;p -> next = tmp -> next;delete tmp;this -> length --;return true;}p = p -> next;}return false;
}bool List::isEmpty() {return this -> length == 0 ? true:false;
}bool List::isFull() {return this -> length == maxSize ? true:false;
}void List::printAll() {Node *p;p = head;cout << "lru list length :" << this -> length << endl;cout << "lru list maxSize :" << this -> maxSize << endl;cout << "lru list val:" << endl;while(p -> next != NULL) {p = p -> next;cout << p -> val << " ";}cout << endl;
}void * List::findElemOptim(DataType x) {Node *p = head;while(p -> next != NULL) {if(p -> next -> val == x) {return (void *)p;}p = p -> next;}return NULL;
}void List::deleteElemOptim(void *node) {Node *p, *tmp;p = (Node*)node;tmp = p -> next;p -> next = tmp -> next;delete tmp;this -> length --;
}int main() {cout << "test LRU:" << endl;List list(10);int num = 0;while(1) {cout << "please enter a number, 99999 = exit" << endl;cin >> num;if(num == 9999) {break;}/*LRU 功能的实现:1. 已有链表中存在 待插入元素，则将该元素在链表中删除，并头插法到链表头节点2. 已有链表中不存在 待插入元素：a. 若 LRU 容量已满，则删除尾元素，头插当前元素b. 若 LRU 容量未满，则直接头插法当前元素           */Node *node = (Node*)list.findElemOptim(num);if(node != NULL) {list.deleteElemOptim(node);list.insertElementBegin(num);} else {if(list.isFull()) {list.deleteElementEnd();list.insertElementBegin(num);} else {list.insertElementBegin(num);}}list.printAll();}return 0;
}

编译g++ -std=c++11 lru_list.cc

运行如下./a.out：

test LRU:
please enter a number, 99999 = exit
2
lru list length :1
lru list maxSize :10
lru list val:
2 
please enter a number, 99999 = exit
3
lru list length :2
lru list maxSize :10
lru list val:
3 2 
please enter a number, 99999 = exit
4
lru list length :3
lru list maxSize :10
lru list val:
4 3 2
...
...
...
please enter a number, 99999 = exit #输入了34，此时LRU容量已满，则删除尾元素，头插入34
34
lru list length :10
lru list maxSize :10
lru list val:
34 23 12 11 1 8 7 3 2 6 
please enter a number, 99999 = exit #输入23，提升23的热度
23
lru list length :10
lru list maxSize :10
lru list val:
23 34 12 11 1 8 7 3 2 6 
please enter a number, 99999 = exit #输入2，提升2的热度
2
lru list length :10
lru list maxSize :10
lru list val:
2 23 34 12 11 1 8 7 3 6 
please enter a number, 99999 = exit
9999

https://www.dkcj.cn/info/4419.html

python getostime_python中sys，os，time模块的使用（包括时间格式的各种转换）

sys模块sys.argv: 实现从程序外部向程序传递参数。位置参数argv[0]代表py文件本身，运行方法 python xx.py 参数1，参数2 。。self sys.argv[0]name sys.argv[1]age sys.argv[2]print self, name, agesys.getdefaultencoding(): 获取系统当前编码&#…

编程日记2024/04/09 11:00:00

关于SpringMVC和Struts2的区别

1. 与struts2不同 1、 springmvc的入口是一个servlet即前端控制器，而struts2入口是一个filter过虑器。 2、 springmvc是基于方法开发，传递参数是通过方法形参，可以设计为单例或多例(建议单例)，struts2是基于类开发&#xff0c…

编程日记2024/04/09 10:30:00

DC-RC加固修补型砂浆

DC-RC加固修补型砂浆www.hrbjg.net一、DC-RC加固修补型砂浆的产品特点：1、耐火、耐高温、耐腐蚀、耐老化性能优良。2、强度高，抹灰操作性好。3、与原混凝土结构的粘结性能良好。4、无收缩，基本不会产生裂缝。5、二氧化碳、氯化物等透过性差&a…

编程日记2024/04/09 10:00:00

类，实例，属性习题

class Restaurant(): def __init__(self,restaurant_name,cuisine_type): self.restaurant_namerestaurant_name self.cuisine_typecuisine_type def describle_restaurant(self): print("打印的第一条消息") print("打印的第…

编程日记2024/04/09 09:30:00

数据结构和算法 -- 学习导图

数据结构和算法是作为程序员写出高效代码的基础，为了今后的两年在高效代码之路上持续精进，将按照此学习导图进行算法和数据结构的刻意练习，同时也希望为同样有高效代码追求的伙伴们提供一条学习路径，共同进步。以下为今后持续…

编程日记2024/04/09 09:00:00

HDU 1248 寒冰王座(全然背包:入门题)

HDU 1248 寒冰王座(全然背包:入门题) http://acm.hdu.edu.cn/showproblem.php?pid1248 题意: 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,仅仅有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡骑士:"我要买…

编程日记2024/04/09 08:30:00

import java.io.*;import java.util.Random;class num{public static void main(String[]args){//声明一个随机数组int sjsh[]new int[7];int sum;try{InputStreamReader anew InputStreamReader(System.in);BufferedReader bnew BufferedReader(a);System.out.println ("…

编程日记2024/04/09 08:00:00

Windows Server 2012 文件服务器群集

概述：之前已经测试了Windows Server 2012系统群集、Hyper-V群集，接下来将测试Windows Server 2012 文件服务器群集功能。实验环境：4台服务器都为Windows Server 2012 DataCenter操作系统在之前配置了群集的基础上，SRV2012服务器新…

编程日记2024/04/09 07:30:01

023 判断出栈顺序是否正确

1.题目输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但4、3…

编程日记2024/04/09 07:00:00

栈 -- 顺序栈、链式栈的实现及其应用（函数栈，表达式求值，括号匹配）

文章目录实现顺序栈实现链式栈实现应用函数栈的应用表达式求值中的应用括号匹配中的应用我们使用浏览器的时候经常会用到前进、后退功能。依次访问完一串页面 a – b – c之后点击后退功能，则能够依次看到c – b – a的页面。但是这个过程中，如果后退…

编程日记2024/04/09 06:30:01

OC中的NSArray和NSMutableArray、NSDictionary和NSMutableDictionary用法

一：NSArray 和NSMutableArray1: NSArray：不可变数组NSArray是OC中使用的数组，只能用来存放OC对象，不能存放非OC对象如基本数据类型它使不可变的，一旦初始化完毕，内容不能改变，也不能添加元素。而…

编程日记2024/04/09 06:00:00

java中ContentArea_java中TextArea怎么加载指定路径的文本内容

展开全部这设计到IO操作，很62616964757a686964616fe58685e5aeb931333332643334久以前练手写的加载文本到文本域的界面。具体代码第一步：得到一个File对象，需要参数文本路径File file new File("C:\\test.txt");第二步：…

编程日记2024/04/09 05:30:01

文本分类技术基础

分类体系分类：给定一个对象，从一个事先定义好的分类体系中挑出一个或多个最适合该对象的类别。文本分类(TC, Text Categorization)：在给定的分类体系下，根据文本内容自动的确定文本关联的类别。从数学角度看，文本分类…

编程日记2024/04/09 05:00:01

C# 返回值为 listT

public List<T> test<T>(List<T> EntityList) where T : class{return EntityList;} 转载于:https://www.cnblogs.com/enych/p/10497312.html

编程日记2024/04/09 04:30:00

ceph bluestore 源码分析：ceph-osd内存查看方式及控制源码分析

文章目录内存查看内存控制内存控制源码分析通过gperftools接口获取osd进程实际内存动态设置cache大小动态调整cache比例trim释放内存本文通过对ceph-osd内存查看跟踪的5种手段以及osd内存控制的方式进行源码层面的说明，并未通过修改相关源码进行控制（水…

编程日记2024/04/09 04:00:00

c语言函数库学习~sscanf~格式化输入

---恢复内容开始--- 今天算是被打击到了吧，由郑轻的acm老师来我学院指导安排了个现场的小比赛，，俺们居然有还是输给一个大一的新手，，哎，情何以堪，，所以还是要重视下基础编程能力的培…

编程日记2024/04/09 03:30:00

java mobile phone games_j2me100-src Java

文件名大小更新时间codesc.net\[J2SE]应用编程150例\chap01\实例1\BorderLayoutDemo.class8192003-07-07codesc.net\[J2SE]应用编程150例\chap01\实例1\BorderLayoutDemo.java5752003-07-07codesc.net\[J2SE]应用编程150例\chap01\实例1\BoxLayoutFrame.class7262003-07-15code…

编程日记2024/04/09 03:00:00

***突然断开可能是ADSL猫惹的祸

在我们使用服务器的时候，最讨厌的就是无故的断线了，可能正在和好一起副本，或者正在视频热聊中，还或者youtube视频看的正起劲，突然windows一个对话框弹出 - “连接已经断开”。实在是太影响体验了，断开之后&…

编程日记2024/04/09 02:30:00

文件中数组的最大值及其对应的最小下标

2019年春季学期第二周作业基础作业请在第一周作业的基础上，继续完成：找出给定的文件中数组的最大值及其对应的最小下标（下标从0开始）。并将最大值和对应的最小下标数值写入文件。输入：请建立以自己英文名字命名的txt文…

编程日记2024/04/09 02:00:00

ceph bluestore源码分析：admin_socket实时获取内存池数据

环境： 版本：ceph 12.2.1 部署完cephfs 使用ceph-fuse挂载，并写入数据关键参数： debug_mempool true 将该参数置为true即可查看详细的blustore管理的内存池的数据命令： ceph daemon osd.id dump_mempools该命令为ad…

编程日记2024/04/09 01:30:00

java clob内存溢出_java - java.sql.SQLException：ORA-01704：字符串文字太长时插入或更新 - 堆栈内存溢出...

通常，当我插入4000个字符限制时，它的工作正常，但当超过4000个字符时，它抛出SQL异常字符串文字太长，即使我的DISCHARGE_TEXT数据类型是CLOB我的JavaScript代码是function saveAsDraftNew(){var admissionNo document.g…

编程日记2024/04/09 01:00:00

LC并联谐振回路

转载于:https://www.cnblogs.com/prayer521/p/4103091.html

编程日记2024/04/09 00:30:01

zencart分类页产品页去掉url中的id号

最近公司新上的网站被seo指出要修改url，去掉url中产品id。由于我们用的是zencart框架，装了 Ultimate SEO URLs 插件，所以在网上应该有这方面的资料，本文主要参考资料：原网址：修改seo url中去掉产品id的方法…

编程日记2024/04/09 00:00:00

hexo博客更新主题后上传Git操作

克隆主题: git clone https://github.com/SuperKieran/TKL.git _config.yml文件中主题改为新增主题 # Extensions ## Plugins: https://hexo.io/plugins/ ## Themes: https://hexo.io/themes/ theme: TKL 进入主题目录,更新git cd theme/TKL git pull 执行更新 hexo clean hex…

编程日记2024/04/08 23:30:00

ceph bluestore源码分析：非对齐写逻辑

文章目录环境原理说明总结环境 ceph:12.2.1 场景：ec 21 部署cephfs，执行如右写模式:dd if/dev/zero of/xxx/cephfs bs6K count4 oflagdirect 关键配置： bluestore_min_alloc_size_hdd 65536 bluestore分配空间的最小粒度单位：B…

编程日记2024/04/08 23:00:01

JVM系列（之ClassLoader）

Class Loader Java运作流程内部class loader bootstrap class loader --引导类加载器，它负责加载Java的核心类【java.* 】（如classpath下面的类库），不是 java.lang.ClassLoader的子类，而是由JVM自身实现的。Code . UR…

编程日记2024/04/08 22:30:00

java平台类成员访问修饰符_JAVA类的修饰符及访问权限

1.类外部类 class前的修饰符只能有publicfinalabstrct无(默认) ：同包可见 (Eclipse中选择package)内部类 class前的修饰符有public、protected、private、默认、final、abstract、static。先看类的访问权限，再看成员的访问权限，类…

编程日记2024/04/08 22:00:00

ios实例开发精品源码文章推荐

1、IOS代码分享:视图布局（View Layout）Border View140601bvpw22rir88b9i8i.png(19.97 KB, 下载次数: 0)下载附件保存到相册半小时前上传http://www.apkbus.com/android-101999-1-14.html2、IOS代码分享：导航条（Navigation Bar&am…

编程日记2024/04/08 21:30:00

Spring BeanDefinitionRegistryPostProcessor BeanPostProcessor作用

写博客，写博客，把自己知道的小知识点全部记录，? BeanDefinitionRegistryPostProcessor 接口属于Beanddefination 装配定义的范畴，此时bean 并没有初始化 BeanPostProcessor属于be an 实例化修改的范畴，be an 已经进行…

编程日记2024/04/08 21:00:00

关于ceph源码 backtrace 打印函数调用栈

当集中精力看一个问题的时候，时间久了就会有这样一个状态，天空飘来五个字，那都不算事 ceph源码庞大的体量以及复杂的设计让很多人望而却步，尤其是大量的纯虚函数更是让读者迷失在代码的海洋，这个时候函数调用栈是一个救…

编程日记2024/04/08 20:30:00