#include <bits/stdc++.h>
using namespace std;
/* *
* FIFO算法的实现：其实是可以采用双端队列，然后限制一下
* 双端队列的长度，根据我的限制应该是4。对于查询是否出现
* 在这个队列里面，我们可以采用一个数组标记是否有存在。
*
* 测试数据如下
16 4
0 1 2 4 3 4 5 1 2 5 1 2 3 4 5 6
* * */
struct FIFO{
int len, m; /// 长度, len - 总访问数; m - 分配的物理块数
int arr[ 105 ]; /// 存储访问页面的编号
deque< int > que;
int vids[ 15 ]; /// 标记数组，标记在当前可以查找到的序号
double result;
int a; /// a - 非缺页数
void Print(deque< int > a){
while (! a.empty()){
printf( " %d " , a.front());
a.pop_front();
}
printf( " \n " );
}
void Init(){ /// 初始化函数
while (! que.empty()){
que.pop_back();
}
memset(vids, 0 , sizeof (vids));
}
void solve(){
scanf( " %d%d " , &len, &m); /// 输入处理的数字的长度，输入有多少可用物理块
for ( int i = 0 ; i < len; i ++ ){
scanf( " %d " , &arr[i]); /// 预先输入处理的数据
}
int r = 0 ; /// 从第一个数据开始判断
while (r < len){ /// 如果没有到达尾部,接着运行
if (!vids[arr[r]]){ /// 如果不在物理块中
a ++; /// 非缺页数加一
printf( " *: " );
if (que.size() < m){ /// 物理块的储存的内容小于m
que.push_back(arr[r]); /// 则将序号放入双端队列
}
else { /// 数量超过了，要实现的是弹出队头，然后把在队列中的标记去掉
int nums = que.front(); /// 获取队头元素
que.pop_front(); /// 弹出队头
vids[nums] --; /// 把出现过的标志去掉
que.push_back(arr[r]); /// 队列压入新的元素
}
vids[arr[r]] ++; /// 把对应的元素的值++
}
Print(que);
r ++; /// 移动到下一个元素
}
printf( " Number of page breaks = %d Total number of visits = %d\n " , a, len);
result = double (a) / double (len);
printf( " f = %f\n " , result);
}
}f;
int main(){
f.Init();
f.solve();
}
#include <bits/stdc++.h>
using namespace std;
/* *
* LRU算法的实现：可以使用一个结构体，来储存对应的数据
* 那么使用一个vector动态数组来储存当前的物理块中的内容
* 那么每访问一次就更新结构体中的value值，那么对vector数组
* 进行对应sort排序,即按照value从大到小排序，然后每次弹出队尾
* 将最小的value值的结构体弹出
* 测试数据如下
16 4
0 1 2 4 3 4 5 1 2 5 1 2 3 4 5 6
* * */
struct LRU_node{ /// LRU的节点结构
int key, value; /// key代表节点最后一次出现的序号，value代表节点的权值
};
bool cmp( const LRU_node &a, const LRU_node & b){
return a.key > b.key; /// 排序，自定义排序cmp方法
}
struct LRU{
int arr[ 105 ]; /// arr即存储当前的数据
vector<LRU_node>vec; /// 动态数组储存节点
int vids[ 105 ]; /// 标记数组
void Init(){ /// 清空函数
memset(vids, 0 , sizeof (vids));
memset(arr, 0 , sizeof (arr));
vec.clear();
}
void slove(){
int n, m;
scanf( " %d%d " , &n, &m); /// n 代表输入的序列的长度是多少， m代表物理块的大小
for ( int i = 0 ; i < n; i ++ ){
scanf( " %d " , & arr[i]);
}
int flag = 0 ; /// 缺页数
int r = 0 ; /// 遍历边界
while (r < n){
LRU_node a;
a.key = r;
a.value = arr[r]; /// 获取一个节点
if (!vids[a.value]){ /// 物理块中没有这个数
flag ++; /// 缺页数加一
printf( " *: " ); /// 代表缺页
if (vec.size() < m){ /// vec的数量小于物理块m
vec.push_back(a);
vids[a.value] ++; /// 标记块中出现的数
sort(vec.begin(), vec.end(), cmp); /// 排序，保证弹出的肯定是时间最开始的那个
}
else { /// vec的数量等于物理块的大小
sort(vec.begin(), vec.end(), cmp); /// 排序
LRU_node en = vec[vec.size() - 1 ]; /// 取出最后的那个即时间最开始的那个
vids[en.value] --; /// 把弹出的数去掉
vec.pop_back();
vec.push_back(a); /// 把新的值压入vec
vids[a.value] ++; /// 标记新的值在块中出现
sort(vec.begin(), vec.end(), cmp); /// 排序
}
for ( int i = 0 ; i < vec.size(); i ++ ){
printf( " %d " , vec[i].value);
}
printf( " \n " );
}
else { /// 否则在块中有对应的数
for ( int i = 0 ; i < vec.size(); i ++){ /// 遍历块中数据
if (vec[i].value == a.value){
vec[i].key = a.key; /// 更新块中的数据所对应的key值，即出现的最后的时间
break ;
}
}
sort(vec.begin(), vec.end(), cmp); /// 排序
for ( int i = 0 ; i < vec.size(); i ++ ){
printf( " %d " , vec[i].value);
}
printf( " \n " );
}
r ++ ;
}
printf( " Number of page breaks = %d Total number of visits = %d\n " , flag, n);
printf( " f = %lf\n " , double (flag) / double (n));
}
}l;
int main(){
l.Init();
l.slove();
return 0 ;
}
#include <bits/stdc++.h>
/* *
* 思路：采用队列来保存每个每个值对应的下一个出现的位置
* 如果只后都不出现，那就把这个值置为无穷大，那么这样的
* 话就能保证这个值，会被先弹出动态数组，那么就能保证实
* 现对应的按照最远出现的位置来淘汰对应的数字。
* * */
using namespace std;
const int MAXN = 105 ; /// 可以控制出现的编号的范围，我假设只会出现105以内的数字
const int inf = 0x7fffffff ; /// int 的最大值，代表这个数再也不会出现
int n, m; /// n 代表序列的长度， m代表物理块的大小
queue< int >que[MAXN]; /// 记录下一个该数字出现的位置
int arr[MAXN]; /// 储存序列
int vids[MAXN]; /// 标记块中是否存在这个
bool cmp( const int &a, const int & b){
return que[a].front() < que[b].front(); /// 按照下一次出现的位置从小到大排序
/// 保证可以将最远访问的块进行更换
}
struct opt{
void Init(){ /// 清空
for ( int i = 0 ; i < MAXN; i ++){ /// 清空队列
while (! que[i].empty()){
que[i].pop();
}
}
memset(vids, 0 , sizeof (vids)); /// 清空标记数组
memset(arr, 0 , sizeof (arr)); /// 清空数组
return ;
}
void solve(){
int f = 0 ; /// 缺页数
scanf( " %d%d " , &n, & m);
Init();
for ( int i = 0 ; i < n; i ++ ){
scanf( " %d " , & arr[i]);
que[arr[i]].push(i); /// 将对应的出现的位置放入队列中
}
for ( int i = 0 ; i < MAXN; i ++ ){
que[i].push(inf); /// 全部放入完成后，放入一个无穷大
/// 这样的好处是如果这个数，后面不再出现，就视为无穷大
}
int r = 0 ;
vector < int >vec; /// 物理块使用动态数组模拟
vec.clear();
while (r < n){
if (!vids[arr[r]]){ /// 如果在物理块中没有出现
f ++; /// 对应的缺页数加一
printf( " *: " ); /// 代表缺页
if (vec.size() < m){ /// 如果没有达到物理块上限
vec.push_back(arr[r]); /// 动态数组压入对应的物理块
vids[arr[r]] ++; /// 标记物理块存在出现
que[arr[r]].pop(); /// 把对应的位置弹出，使其更新为下一个最近的位置
}
else {
sort(vec.begin(), vec.end(), cmp); /// 否则达到上限,按照后面出现的位置排序
int temp = vec[vec.size() - 1 ]; /// 获取队尾的数值
vids[temp] --; /// 把对应的数值的出现标记抹去
vec.pop_back(); /// 将队尾弹出
vec.push_back(arr[r]); /// 压入新的数值
vids[arr[r]] ++; /// 把对应的数值的出现标记更新
que[arr[r]].pop(); /// 把对应新的数值的下一个出现的位置进行更新
}
/* *输出物理块中的内容* */
for ( int i = 0 ; i < vec.size(); i ++ ){
printf( " %d " , vec[i]);
}
printf( " \n " );
}
else {
que[arr[r]].pop(); /// 在物理块中，将对应的值的后续的出现位置进行更新
sort(vec.begin(), vec.end(), cmp); /// 按照出现的位置的远近排序
for ( int i = 0 ; i < vec.size(); i ++){ /// 输出块中的内容
printf( " %d " , vec[i]);
}
printf( " \n " );
}
r ++ ;
}
printf( " Number of page breaks = %d Total number of visits = %d\n " , f, n);
printf( " %f\n " , double (f) / double (n));
}
}a;
/* *
测试样例如下：
12 3
2 3 2 1 5 2 4 5 3 2 5 2
* */
int main(){
a.solve();
return 0 ;
}
#include <bits/stdc++.h>
using namespace std;
/* *
* 思路：lfu的实现，可以使用Map<int, int>来实现计数
* 或者使用int数组来标记出现的次数，然后每次进行对次数
* 的排序就行了，然后每次淘汰访问次数最小的就ok了，如果
* 数据范围较小的话，使用int数组来标记的话，把每次查询的
* 复杂度降到O(1)，所以下面的代码实现使用数组来标记出现的
* 次数
* * */
const int MAXN = 105 ;
int flag[MAXN]; /// 下标代表出现的数值，下标里的数值代表被访问的次数
bool cmp( const int &a, const int & b)
{ /// 按照被访问的次数进行从大到小的排序
return flag[a] > flag[b]; /// 这样能保证更换物理块的时候是按照出现的次数最小的被更换
}
struct LFU
{
vector < int > vec; /// 代表物理块
int vids[MAXN]; /// 代表物理块中出现的数
int n, m;
void Init() /// 初始化函数
{
vec.clear();
memset(vids, 0 , sizeof (vids));
memset(flag, 0 , sizeof (flag));
}
void solve()
{
int f = 0 ; /// 缺页数
scanf( " %d%d " , &n, & m);
Init();
for ( int i = 0 ; i < n; i++ )
{
int num;
scanf( " %d " , &num); /// 输入一个值
if (!vids[num]) /// 判断是否在物理块中
{
f ++ ;
printf( " *: " );
if (vec.size() < m) /// 如果数量小于物理块的数量
{
vec.push_back(num); /// 直接压入物理块
vids[num]++; /// 标记其出现
flag[num]++; /// 对应的出现次数加一
}
else
{
sort(vec.begin(), vec.end(), cmp); /// 针对出现的次数排序
int temp = vec[vec.size() - 1 ]; /// 获取出现次数最小的数的值
vids[temp]--; /// 将其标记去掉
flag[temp] = 0 ; /// 将其访问的次数变为0
vec.pop_back(); /// 将其弹出队列
vec.push_back(num); /// 将新的值压入内存块
vids[num]++; /// 将新的值标记出现
flag[num]++; /// 将新的值得出现次数加一
}
sort(vec.begin(), vec.end(), cmp); /// 排序
for ( int i = 0 ; i < vec.size(); i++) /// 输出物理块
{
printf( " %d " , vec[i]);
}
printf( " \n " );
}
else
{
flag[num] ++; /// 在物理块中，将访问值加一
sort(vec.begin(), vec.end(), cmp); /// 排序
for ( int i = 0 ; i < vec.size(); i++) /// 输出物理块的情况
{
printf( " %d " , vec[i]);
}
printf( " \n " );
}
}
printf( " Number of page breaks = %d Total number of visits = %d\n " , f, n);
printf( " %f\n " , double (f) / double (n));
}
} a;
int main()
{
a.solve();
return 0 ;
}
查看更多关于FIFO算法，LRU算法，OPT算法，LFU算法的C++实现的详细内容...
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did238232