页面置换算法（FIFO、LRU、LFU）c++实现

1. FIFO(First in First out) -- 先进先出

先来先服务的策略。如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。（这个可以类比队列较好理解）

实现：核心：双向链表实现队列+ hashmap

利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾，这样插入和删除都可以在O（1）时间内完成。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。访问效率为O（n），可以通过添加hashmap来提高访问速度达到O（logn）。

#include"head.h"//头文件在最后处
#include<math.h>

class FIFOCache
{
public:

	FIFOCache(int capacity)
	{
		FIFOcapacity = capacity;
		FIFOsize = 0;
		list.Listcapcity = capacity;

	}

	int get(int key)
	{
		if (!FIFOmap.count(key))
			return -1;
		Node* node = FIFOmap[key];
		return node->val;
	}
	void put(int key, int value)
	{
		if (FIFOcapacity == 0)
			return;
		if (FIFOmap.count(key))
		{
			Node* node = FIFOmap[key];
			list.remove(node);
			node->val = value;
			list.append(node);
		}
		else
		{
			if (FIFOsize == FIFOcapacity)
			{
				Node* node = list.pop();
				int x = node->val;
				map<int, Node*>::iterator it3 = FIFOmap.find(x);
				//通过find拿到 node.val 为关键字的的迭代器
				FIFOmap.erase(it3);
				--FIFOsize;
			}
			Node* node = new Node(value);

			list.append(node);
			FIFOmap[key] = node;
			++FIFOsize;

		}
	}

	void printFIFO()
	{
		list.printList();
	}
	//数据成员
	int FIFOsize;
	int FIFOcapacity;
	DoubleList list;
	map<int, Node*>FIFOmap;
};

测试代码（FIFO）：

FIFOCache cache(2);
	cache.put(1,1);
	cache.printFIFO();

	cache.put(2, 2);
	cache.printFIFO();

	cout << cache.get(1) << endl;

	cache.put(3, 3);
	cache.printFIFO();

	cout << cache.get(2) << endl;
	cache.printFIFO();

	cache.put(4, 4);
	cache.printFIFO();

	cout << cache.get(1) << endl;

页面置换算法（FIFO、LRU、LFU）c++实现

2. LFU（Least Frequently Used） -- 最近最少使用

基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。

LFU是基于访问次数的。（这里可以把LFU看作是FIFO的优化，数据在原有基础增添一新的数据成员，用以计数数据被访问次数，按照数据被访问计数进行“分组”，计数相同的数据分为一组，淘汰时，选取最计数组，按照FIFO方法淘汰首元素）

实现：核心：存放双向链表的hashmap

LFU可以视为按频率“分组”的FIFO算法，所以我们利用hashmap，key存放数据被访问频率，key对应的value存放key频率下的双向链表。这样淘汰数据时，只要找到最小频率组，再按照FIFO策略淘汰数据即可。同时需要一个hashmap存放，数据地址，加快查找。

访问数据命中，则从相应的双向链表中删除，插入下一频数的双向链表，若该频数双向链表不存在则创建并插入；若删除数据使得双向链表为空，则删除双向链表。

#include"head.h"
#include<math.h>
class LFUNode :public Node//新定义的LFUNode类继承Node类基础上，添加freq数据成员作为计数
{
public:
	LFUNode() {}
	
	LFUNode(int x)
	{
		freq = 0;
		val = x;
	}
	int freq;
};

class LFUcache
{
public:
	LFUcache(int capacity)
	{
		LFUcapacity = capacity;
		LFUsize = 0;
		
	}

	void update(LFUNode*node) //更新节点 每次get或者put 访问频率改变
	{
		int freq = node->freq;
		//删除
		LFUNode* node1 = NULL;
		node1=(LFUNode*)freq_map[freq]->remove(node); ///
		if (freq_map[freq]->Listsize == 0)//如果该节点为最后一个节点，则删除双向链表
		{
			map<int, DoubleList*>::iterator it = freq_map.find(freq);
			freq_map.erase(it);
		}

		//更新
		++freq;
		node1->freq = freq;
		if (freq_map.count(freq))//该频率已存在，则尾部加入
		{
			freq_map[freq]->append(node1);//static_cast<Node*>(node)
		}
		else  //该频率未存在，则创建新双向链表插入
		{
			DoubleList* Dlist = new DoubleList();
			Dlist->append(node1);//
			freq_map[freq] = Dlist;
		}
	}
	int get(int key)
	{
		if (!LFUmap.count(key))
			return -1;
		else
		{
			LFUNode* node = LFUmap[key];
			update(node);
			return node->val;
		}
	}

	void put(int key,int value)
	{
		if (LFUcapacity == 0)
			return;
		if (LFUmap.count(key))//缓存命中
		{
			LFUNode* node = LFUmap[key];
			node->val = value;
			update(node);
		}
		else//缓存没有命中
		{
			if (LFUsize == LFUcapacity)
			{
				Node* node = NULL;
				map<int, DoubleList*>::iterator it1 = freq_map.begin();
				node =it1->second->pop();
				map<int, LFUNode*>::iterator it2 = LFUmap.find(node->val);
				LFUmap.erase(it2);
				--LFUsize;
			}
			LFUNode* lfNode = new LFUNode(value);
			lfNode->freq = 1;
			LFUmap[key] = lfNode;
			if (!freq_map.count(lfNode->freq))
			{
				freq_map[lfNode->freq] = new DoubleList();
			}
			freq_map[lfNode->freq]->append(static_cast<Node*>(lfNode));//
			++LFUsize;
		}
	}

	void printLFU()
	{
		cout << "---------Start-------------------"<< endl;
		for (map<int ,DoubleList*>::iterator it= freq_map.begin();  it != freq_map.end(); ++it)
		{
			cout << "Freq = " << it->first << " :" << endl;
			it->second->printList(); 
		}
		cout << "---------End-------------------"<< endl<<endl;
	}


	int LFUsize;
	int LFUcapacity;
	
	map<int, DoubleList*>freq_map;
	map<int, LFUNode*>LFUmap;

};

测试代码（LFU）：

LFUcache cache3(2);
	cache3.put(1, 1);
	cache3.printLFU();

	cache3.put(2, 2);
	cache3.printLFU();

	cout << cache3.get(1) << endl;
	cache3.printLFU();

	cache3.put(3, 3);
	cache3.printLFU();

	cout<<cache3.get(2) << endl;
	cache3.printLFU();
	cout << cache3.get(3) << endl;
	cache3.printLFU();

	cache3.put(4, 4);
	cache3.printLFU();

	cout << cache3.get(1) << endl;
	cache3.printLFU();
	cout << cache3.get(3) << endl;
	cache3.printLFU();
	cout << cache3.get(4) << endl;
	cache3.printLFU();

页面置换算法（FIFO、LRU、LFU）c++实现

3. LRU（Least Frequently Used） -- 最近最久未使用

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。（从描述来看和LFU很类似，区别在于，LRU注重的是访问时间，而LFU注重的是访问次数，考察细节不同，但大体方向类似）

实现：核心：双向链表实现队列+ hashmap

用一个双向链表来存储数据，并把相应的地址放入hashmap中，hashmap的作用主要是提高查找效率。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部；如果不存在，则新建一个节点，放到链表头部。若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。

#include"head.h"
#include<math.h>
class LRUcache
{
public:
	LRUcache(int capacity)
	{
		LRUcapacity = capacity;
		list.Listcapcity = capacity;
		LRUsize = 0;
	}
	int get(int key)
	{
		if (LRUmap.count(key))
		{
			Node* node = LRUmap[key];
			list.remove(node);
			list.append_front(node);
			return node->val;
		}
		else
			return - 1;
	}

	void put(int key, int value)
	{
		if (LRUcapacity == 0)
			return;
		if (LRUmap.count(key))
		{
			Node* node = NULL;
			node = list.remove(LRUmap[key]);
			node->val = value;
			list.append_front(node);
		}
		else
		{
			if (LRUsize == LRUcapacity)
			{
				Node* node = NULL;
				node= list.remove();
				int x = node->val;
				map<int, Node*>::iterator it = LRUmap.find(x);
				LRUmap.erase(it);
				--LRUsize;
			}
			Node* node = new Node(value);
			list.append_front(node);
			LRUmap[key] = node;
			++LRUsize;
		}
	}

	void printLRU()
	{
		list.printList();
	}
	//数据成员
	int LRUsize;
	int LRUcapacity;
	DoubleList list;
	map<int, Node*>LRUmap;
};

测试代码（LRU）：

LRUcache cache2(2);
	cache2.put(2, 2);
	cache2.printLRU();

	cache2.put(1, 1);
	cache2.printLRU();

	cache2.put(3, 3);
	cache2.printLRU();

	cout << cache2.get(1) << endl;
	cache2.printLRU();

	cout << cache2.get(2) << endl;
	cache2.printLRU();

	cout << cache2.get(3) << endl;
	cache2.printLRU();

页面置换算法（FIFO、LRU、LFU）c++实现

头文件：

#pragma once
#include<iostream>
#include<map>
using namespace std;

class Node
{
public:
	Node() {}
	Node(int x)
	{
		val = x;
	}
	int val = 0;
	Node* prev = NULL;
	Node* next = NULL;
};

class DoubleList
{
public:

	DoubleList(int capacity = 100)
	{
		Listsize = 0;
		head = NULL;
		tail = NULL;
		Listcapcity = capacity;
	}
	//头插入
	bool add_head(Node* node)
	{
		if (head == NULL)
		{
			head = node;
			tail = node;
			head->prev = NULL;
			tail->next = NULL;
			++Listsize;
			return false;
		}
		else
		{
			node->next = head;
			head->prev = node;
			head = node;
			head->prev = NULL;

			++Listsize;
			return true;
		}

	}

	//尾插入
	bool add_tail(Node* node)
	{
		if (tail == NULL)
		{
			head = node;
			tail = node;
			head->prev = NULL;
			tail->next = NULL;
			++Listsize;
			return true;
		}
		else
		{
			node->prev = tail;
			tail->next = node;
			tail = node;
			tail->next = NULL;
			++Listsize;
			return true;
		}
	}

	//任意删除
	Node* removerad(Node* node)
	{
		//node为 NULL 默认删除尾部节点
		if (node == NULL)
			node = tail;
		if (node == tail)
		{
			remove_tail();
			return node;
		}

		else if (node == head)
		{
			remove_head();
			return node;
		}

		else
		{
			node->prev->next = node->next;
			node->next->prev = node->prev;
			--Listsize;
			return node;
		}

	}
	//尾部删除
	Node* remove_tail()
	{
		if (Listsize == 0)
			return NULL;

		else if (Listsize == 1)
		{
			Node* node = tail;
			head = NULL;
			tail = NULL;
			--Listsize;
			return node;
		}
		else
		{
			Node* node = tail;
			tail = tail->prev;
			tail->next = NULL;
			--Listsize;
			return node;
		}
	}
	//头部删除
	Node* remove_head()
	{
		if (Listsize == 0)
			return NULL;

		else if (Listsize == 1)
		{
			Node* node = head;
			head = NULL;
			tail = NULL;
			--Listsize;
			return node;
		}
		else
		{
			Node* node = head;
			head = head->next;
			head->prev = NULL;
			--Listsize;
			return node;
		}
	}

	//外部接口：弹出头部
	Node* pop()
	{
		return remove_head();
	}

	//外部接口： 添加节点  从尾部
	bool append(Node* node)
	{
		return add_tail(node);
	}

	//外部接口： 添加节点  从头部
	bool append_front(Node* node)
	{
		return add_head(node);
	}

	//外部接口： 删除节点
	Node* remove(Node* node = NULL)
	{
		return removerad(node);
	}
	//外部接口： 打印链表
	void printList()
	{
		if (Listsize == 0)
			cout << "No Node..." << endl;
		else {
			Node* cur = head;
			cout << "{ ";
			while (cur != NULL)
			{
				cout << " -> " << cur->val ;
				cur = cur->next;
			}
			cout <<" }"<< endl;
		}

	}
	//数据成员部分
	int Listsize;
	int Listcapcity;
	Node* head;
	Node* tail;
};

页面置换算法（FIFO、LRU、LFU）c++实现

继续阅读

软件开发设计整体文档编制手册

使用滴答清单的一点小体会

Android Studio调用QT for Android生成的.so库本文介绍如何实现Android 与 QT 的结合，使Android能够调用QT的代码，避免重复造轮子

当服务器崩了之后

Android SDK Manager和AVD Manager使用

兄弟我在码农界的平庸史＜11＞近似项目经理

Linux 下安装配置jdk jre

04概要设计说明书（机房收费系统）

《机房收费系统》概要设计说明书1引言2总体设计3接口设计4运行设计5系统数据结构设计6系统出错处理设计

解决 Qt5 报错 This application failed to start because it could not find or load the Qt platform plugin解决 Qt5 报错 This application failed to start because it could not find or load the Qt platform plugin

两种解决Qt5显示中文乱码的方法（使用QStringLiteral和#pragma execution_character_set("utf-8")两种方法）两种解决Qt5显示中文乱码的方法（使用QStringLiteral和#pragma execution_character_set("utf-8")两种方法）

测试的基本理论与方法（1）

软件开发模型_扫盲 (Software Development Model)前言CMMI是啥软件开发模型 (Software Development Model)

软件开发的打怪升级攻略

我做“内网知识星球”一周年总结

MySQL的4种隔离级别？出现问题