LRU.rar_LRU资源-CSDN文库

共1个文件

cpp：1个

版权申诉

17 浏览量 2022-09-14 17:16:17 上传评论收藏 1KB RAR 举报

LRU（Least Recently Used）是最常用的缓存淘汰策略之一，其基本思想是“最近最少使用的数据优先被替换”。当缓存满时，如果新的数据进来，那么最近最少使用的数据会被淘汰，以腾出空间给新数据。这个策略假设最近经常访问的数据在未来也更可能被频繁访问。在C++中实现LRU算法，主要涉及到数据结构的设计和操作。一种常见的方式是使用哈希表（HashMap）结合双向链表来实现。哈希表用于快速查找，双向链表则用来记录数据的访问顺序，因为LRU的关键在于数据的最近使用顺序。我们需要定义一个节点类`Node`，它包含数据、键和指向前后节点的指针。节点类可能如下所示： ```cpp struct Node { int key; int value; Node* prev; Node* next; }; ``` 然后，我们创建一个`LRUCache`类，它包含哈希表`unordered_map`和双向链表`list`。初始化时，哈希表和链表为空。`LRUCache`类可能包含以下方法： 1. `get(int key)`：查询指定键的值。如果键存在，更新该节点在链表中的位置，并返回值；否则，返回-1。 2. `put(int key, int value)`：将键值对插入到缓存中。如果键已经存在，则更新其值；如果缓存已满且新键不存在，淘汰最不常使用的节点，然后插入新节点。 3. `evict()`：淘汰最不常使用的节点，即链表尾部的节点。在`put`方法中，我们需要检查当前缓存大小是否超过预设容量。如果超过，需要先淘汰`list`的尾部节点，即`list_.back()`，然后从`hash_map`中删除对应的键。接着，将新键值对插入到链表头部，并更新哈希表。 `get`方法中，若找到键，将找到的节点移到链表头部，并返回值。否则，返回-1。 `LRUCache`类的大概实现如下： ```cpp class LRUCache { private: int capacity_; unordered_map<int, Node*> hash_map; list<Node*> list_; public: LRUCache(int capacity) : capacity_(capacity) {} int get(int key) { if (hash_map.find(key) != hash_map.end()) { moveToHead(hash_map[key]); return hash_map[key]->value; } return -1; } void put(int key, int value) { if (hash_map.find(key) != hash_map.end()) { list_.erase(hash_map[key]->next); } else { if (hash_map.size() == capacity_) { evict(); } } Node* newNode = new Node{key, value, nullptr, list_.front()}; list_.front()->prev = newNode; list_.splice(list_.begin(), list_, newNode); hash_map[key] = newNode; } void evict() { hash_map.erase(list_.back()->key); list_.pop_back(); } void moveToHead(Node* node) { list_.splice(list_.begin(), list_, node); updateHash(node); } void updateHash(Node* node) { hash_map[node->key] = node; } }; ``` 以上就是LRU算法的基本实现思路。在实际编程中，还需要考虑异常处理、内存管理以及优化细节。通过这样的实现，我们可以高效地在内存有限的情况下，优先保持最近常用数据的可用性，从而提高系统性能。

资源推荐

资源详情

资源评论

收起资源包目录

LRU.rar （1个子文件）

LRU.cpp 3KB

#include<iostream.h> #include<stdio.h> void read(int a[50],int& n) //读入页面走向 { cout<<"输入进程的页面走向（每输完一页回车一次），最后以0结束！\n"; n=0; do { cin>>a[n]; }while(a[n++]!=0&&n<50); --n; cout<<"页面走向为：\n"; cout<<"----------------------\n"; for(int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<'\n'; cout<<"----------------------\n"; } void main() { cout<<"***** 07计机<1>班 ******\n"; cout<<"*****此程序使用的是 LRU算法******\n\n\n"; cout<<"输入分配的内存块数:"; int k; //k为存储页面的内存块数 cin>>k; int q=0; //记录缺页次数 int x[50]={0},y; //记录内存块中页面停留的时间 int i,a[50]; //记录页面走向 int p[50]={0}; //记录内存块中的页面 read(a,i); for(int j=0;j<i;j++) { int count1=0; for(int m=0;m<k;m++) //判断内存中有无调度的页面 { if(a[j]!=p[m]) count1++; } if(count1==k) //调度页面不在内存中 { for(int t=0;t<k;t++) { int count2=0; for(int r=0;r<k;r++) { if(x[t]>=x[r])count2++; } if(count2==k) { y=t;break; } } cout<<"第"<<j+1<<"次 <"<<a[j]<<"页> 执行时"<<"\t"<<"缺页"<<" "; if(p[y]==0)cout<<"内存块"<<y+1<<"中无页面"<<"直接将 <"<<a[j]<<"页> 调入内存块"<<y+1; //内存中还有没用的块直接调入 else cout<<"调出内存块"<<y+1<<"中的 <"<<p[y]<<"> 页,将 <"<<a[j]<<"页> 调入内存块"<<y+1; p[y]=a[j]; //置换进内存块 x[y]=0; for(t=0;t<k;t++) { x[t]++; } x[y]--; q++; //缺页次数记录 } else { for(int t=0;t<k;t++) //比较优先级 { if(a[j]==p[t]){y=t;break;} } cout<<"第"<<j+1<<"次 <"<<a[j]<<"页> 执行时"<<"\t" <<"命中"<<'\t'<<"执行下个页面!"; x[y]=0; //重新调度了页面后给它进入内存的时间归零 for(t=0;t<k;t++) //使其余页面进入内存的时间全部加1 { x[t]++; } x[y]--; } cout<<endl; } cout<<"缺页次数:"<<q<<endl; cout<<"缺页率 :"<<q<<'/'<<i<<"="<<(float)q/(float)i<<endl; cout<<endl<<"------------------输入enter结束--------------"<<endl; getchar(); }

评论收藏

内容反馈

版权申诉