C++一步一步优化LRU算法

女爷i 2023-01-06 14:59 130阅读 0赞

### c++实现LRU算法 ###

*  LRU
 *  单链表
 *   *  代码
 *  双向链表+哈希表
 *   *  代码
 *  总结

# LRU #

今日无意在头条看到一篇文章,[其实吧，LRU也就那么回事][LRU]  
LRU好耳熟的东西,于是乎我就点进去看了看才发现这东西不就是操作系统里将页面置换算法时讲的东西吗?  
![在这里插入图片描述][20210114215010374.png]  
简单的一张图就能很简单的明白这个算法有多简单,考试要考这种算法感觉就是送分题,当时置换算法最容易理解和最容易计算的就是这个算法,当时考操作系统时贼希望考这种类型的计算题,可是并没有!!!  
当时看这个简单理解和计算所以就没怎么太在意他,直到看到那篇文章后才发现其实这种算法在开发中用的特别多,唉,这是我没想到的!!!感叹的话已经说完,今天写这篇文章的主要目的并不是为了告诉你这个算法的用处还是什么,今天就纯c++写出这个算法并优化

# 单链表 #

就像那篇文章所说的,  
![在这里插入图片描述][2021011421562953.png]  
不用LinkedHashmap的只用Node开始撸,不知道有多少壮汉会…  
真的不废话了这次真的实践了  
首先我们先理解一下LRU的思路是什么?  
**如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以，当指定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。**  
从思路划分关键句

*  指定空间已存满
 *  淘汰最久没访问的

从关键句里划分问题

*  没存满时,是直接插入还是先遍历后在插入
 *  怎么判断数据是最久的

![在这里插入图片描述][20210114220725783.png]

逐步解决问题

*  容器不满时,先假设直接插入,可能出现这种情况—>连续插入同一个数据,那就可能使得容器有相同元素存在,所以应该先遍历查找容器是否存在该元素,如果有则删除该元素并重新插入到容器中
 *  判断数据的插入时间,第一时间我就考虑到时间戳,这个是一个办法但是还有更好的吗,看到上图我就联想到了链表准确的来说应该是栈原理,如果一个元素在栈底不就代表他是最早进栈的吗?

## 代码 ##

#include<iostream>
    using namespace std;
    //创建单链表
    typedef struct NODE {
    	int val;//值
    	NODE *next;
    } Node;
    class LRU {
    	private:
    		Node *head;
    		int count;
    		int MaxSize;
    	public:
    		LRU() {
    			head=new Node();
    			head->next=NULL;
    			count=0;
    			MaxSize=3;
    		}
    		~LRU() {
    			while(head!=NULL) {
    				Node *node=head;
    				head=head->next;
    				delete node;
    				
    			}
    		}
    		bool IsMax() {
    			return count==MaxSize;
    		}
    		void push(int value) {
    			Node *p=new Node;
    			Node *node=head;
    			//判断链表是否已经存在该值
    			bool flag=false;
    			while(node->next!=NULL) {
    				if(node->next->val==value) {
    					node->next=node->next->next;
    					count--;
    					flag=true;
    				}
    				//特殊处理当该元素是最后一个元素 
    				if(node->next==NULL){
    					break;
    				}
    				node=node->next;
    			}
    			//当链表已满
    			if(IsMax()) {
    				//不存在该值,删除链顶
    				if(!flag) {
    					head=head->next;
    					count--;
    				}
    			}
    			p->val=value;
    			p->next=NULL;
    			node->next=p;
    			count++;
    		}
    		void print(){
    			Node *node=head->next;
    			while(node){
    				cout<<node->val<<" ";
    				node=node->next;
    			}
    			cout<<endl;
    		} 
    };
    int main() {
    	LRU lru=LRU();
    	lru.push(2);
    	lru.push(3);
    	lru.push(2);
    	cout<<"当容器没满时,插入存在的元素,结果为:"; 
    	lru.print(); 
    	lru.push(4);
    	cout<<"当容器已满时,结果为:"; 
    	lru.print();
    	lru.push(5);
    	cout<<"当容器已满时,插入不存在的元素,结果为:"; 
    	lru.print();
    	lru.push(3);
    	lru.push(5);
    	cout<<"当容器已满时,插入存在的元素,结果为:"; 
    	lru.print();
    }

![在这里插入图片描述][20210114222919575.png]  
代码不多,还是很好写出来的,不过如果单纯只用链表的话还会出现一些问题,

*  时间复杂度
 *  查一个数就会遍历一次链表 遍历的时间复杂度就是O(n)
 *  删除麻烦
 *  每次添加都必须要到栈顶位置,就相当于一次遍历一样

# 双向链表+哈希表 #

现在我们一一来解决单链表出现的问题

*  减少在查找时的时间复杂度,引用数组的下标能快速查找到某个值,但是数组在增删时间复杂度要比链表高很多,所以要是有什么方法能做到数组和链表特性的结合体就好了,我第一时间能想到的就是那牺牲空间来换取时间的java叫集合,python叫字典,c++叫hash表的键值对表示方式的玩意,如果我将链表中每个元素存在hash表中并用其进行标记即key是标记,value则是值,这样就能快速定位到某个节点了
 *  对于增删处理,无疑双向链表是不二之选

## 代码 ##

这里用到的是c++所以用到的是hashmap,而不是map,因为map的get请求的时间复杂度是O(logn),而hashmap则是O(1)

#include<iostream>
    #include<hash_map>
    using namespace std;
    using namespace __gnu_cxx;
    typedef struct NODE {
    	int val;
    	NODE *pre,*next; //上一个节点和下一个节点
    	NODE(int v):val(v),pre(NULL),next(NULL) {}
    } Node;
    class LRU {
    	private:
    		int size;
    		hash_map<int,Node*> hash_mp;
    		Node *head,*tail;
    
    	public:
    		LRU(int capacity) {
    			size=capacity;
    			head=NULL;
    			tail=NULL;
    		}
    		~LRU() {
    			while(head) {
    				Node *n=head;
    				head=head->next;
    				delete n;
    			}
    		}
    		/*
    		插入处理
    		1.hash表中包含该值,移除该值,并向尾部插入该值 hashmap更新key的值
    		2.hash表中不包含,判断容器是否已满
    		2.1容器未满,直接插入,hashmap添加key-value
    		2.2 容器已满,删除链底元素后尾部插入该节点,hashmap同步删除和添加
    		*/
    		void push(int value) {
    			hash_map<int, Node *>::iterator it = hash_mp.find(value);
    			Node * node=new Node(value);
    			if(it!=hash_mp.end()) {
    				node=it->second;
    				//删除该节点
    				remove(node);
    				node->next=NULL;
    			} else {
    				if(hash_mp.size()>=size) {
    					//容器已满,删除链底元素
    					hash_map<int, Node *>::iterator iter = hash_mp.find(head->next->val);
    					head=head->next;
    					hash_mp.erase(iter);
    				}
    			}
    			add(node);
    			hash_mp[value]=node;
    		}
    		/*
    		添加新节点
    		1.首次添加
    		2.尾指针的下一个节点指向新节点->新节点的上一个指针指向尾指针->设置新指针为尾指针
    		*/
    		void add(Node * node) {
    			if(head==NULL) {
    				head=node;
    				tail=head;
    				return;
    			}
    
    			tail->next=node;
    			node->pre=tail;
    			tail=node;
    		}
    		/*
    		删除节点
    		1.该节点为头节点
    		2.该节点为尾节点
    		3.其他
    		*/
    		void remove(Node *node) {
    			if(node->pre==NULL) {
    				head=head->next;
    				head->pre=NULL;
    				return;
    			}
    
    			if(node->next!=NULL) {
    				node->pre->next=node->next;
    				node->next->pre=node->pre;
    			} else {
    				tail=node->pre;
    			}
    		}
    		void print() {
    			Node *node=head;
    			while(node) {
    				cout<<node->val<<" ";
    				node=node->next;
    			}
    			cout<<endl;
    		}
    };
    int main() {
    	LRU lru=LRU(3);
    	lru.push(2);
    	lru.push(3);
    	lru.push(2);
    	cout<<"当容器没满时,插入存在的元素,结果为:";
    	lru.print();
    	lru.push(4);
    	cout<<"当容器已满时,结果为:";
    	lru.print();
    	lru.push(5);
    	cout<<"当容器已满时,插入不存在的元素,结果为:";
    	lru.print();
    	lru.push(3);
    	lru.push(5);
    	cout<<"当容器已满时,插入存在的元素,结果为:";
    	lru.print();
    	lru.push(4);
    	cout<<"当容器已满时,插入已存在的栈底元素的元素,结果为:";
    	lru.print();
    	lru.push(4);
    	cout<<"当容器已满时,插入已存在的栈顶的元素,结果为:";
    	lru.print();
    }

![在这里插入图片描述][20210115230318988.png]

# 总结 #

LRU在置换算法中还是比较简单实现的,在后续也会更新偏中等的LFU的实现方法

[LRU]: https://www.toutiao.com/a6911523050357916164/
[20210114215010374.png]: /images/20221119/651a62a8f10e48e890984e08deaf71a1.png
[2021011421562953.png]: https://img-blog.csdnimg.cn/2021011421562953.png
[20210114220725783.png]: https://img-blog.csdnimg.cn/20210114220725783.png
[20210114222919575.png]: https://img-blog.csdnimg.cn/20210114222919575.png
[20210115230318988.png]: https://img-blog.csdnimg.cn/20210115230318988.png