命题作业 5-1 【C++ 实现版本】

//----cat hash.h-------
#include <string>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
using string=std::string;
struct DataNode{
	int nodeID;
	int nodeVirtualID;
	string nodeHashValue;
	DataNode(int id,int vid, const string& hash):nodeID(id),nodeVirtualID(vid),nodeHashValue(hash)
	{}
};
struct DataNodeCompare{
	bool operator()(const DataNode& lhs, const DataNode& rhs) const
	{
		return lhs.nodeHashValue<rhs.nodeHashValue;
	}
};
class CacheManager{
	std::map<int,int> virtualID;
	std::set<DataNode, DataNodeCompare> ring;
	CacheManager(){}
public:
	static CacheManager& GetInstance()
	{
		static CacheManager manager;
		return manager;
	}
	void addNode(int nodeID);
	void Init(int nodeNum,int virtualnodeNum);
	int getDataID(const string& dataKey);
	void showRing()
	{
		for(auto x:ring)
			std::cout<<"nodeid is "<<x.nodeID<<" nodevid is"<<x.nodeVirtualID<<" hash value is"<<x.nodeHashValue<<std::endl;
	}
};
class Statistics 
{
	std::map<int,int> map;
	int avg;
	Statistics(){}
public:
	void SetAvg(int a)
	{
		avg = a;
	}
	static Statistics& GetInstance()
	{
		static Statistics  imp;
		return imp;
	}
	void HitNode(int nodeID)
	{
		if(map.find(nodeID)!=map.end())
			map[nodeID]++;
		else
			map[nodeID]=1;
	}
	double CalcResult();
	void Clear()
	{
		map.clear();
	}
	void ShowResult()
	{
		for(auto x:map)
			std::cout<<"nodeid "<<x.first<<" node time"<<x.second<<std::endl;
	}
};
class Log
{
	std::ofstream file;
	Log()
	{ 
		file.open("log.csv",std::ios::out|std::ios::trunc);
		file<<"虚拟节点个数,标准差"<<std::endl;
	}
	~Log()
	{
		file.close();
	}
public:
	static Log& GetInstance()
	{
		static Log imp;
		return imp;
	}
	void GetLog(int vnum, double sqrt)
	{
		file<<vnum<<","<<sqrt<<std::endl;
	}
};
//----cat hash.cpp-------
#include "hash.h"
#include "md5.h"
#include <math.h>
#include <sstream>
using stringstream=std::stringstream;
void CacheManager::addNode(int nodeID)
{
	int vid = 0;
	if(virtualID.find(nodeID)!=virtualID.end())
	{
		vid = virtualID[nodeID]++;
	}
	else
	{
		virtualID[nodeID] = 1;
	}
	stringstream str;
	str<<nodeID<<"-"<<vid;
	DataNode node(nodeID, vid, MD5(str.str()).toString());
	ring.insert(node);
}
void CacheManager::Init(int nodeNum, int virtualnodeNum)
{
	virtualID.clear();
	ring.clear();
	for(size_t i=0;i<nodeNum;i++)
		for(size_t j=0;j<virtualnodeNum;j++)
			addNode(i);
}
int CacheManager::getDataID(const string& dataKey)
{
	//获取哈希值
	string hash=MD5(dataKey).toString();
	//寻找虚拟节点
	auto itr=ring.upper_bound(DataNode(0,0,hash));
	//得到物理节点ID
	if(itr!=ring.end())
		return itr->nodeID;
	return 0;
}
void TestCache(const string& tmp)
{
	int id = CacheManager::GetInstance().getDataID(tmp);
	//std::cout<<"data is"<<tmp<<"  id is"<< id << std::endl;
	Statistics::GetInstance().HitNode(id);
}
void ShowRing()
{
	CacheManager::GetInstance().showRing();
}
double Statistics::CalcResult() 
{
	//标准差定义是总体各单位标准值与其平均数离差平方的算术平均数的平方根。它反映组内个体间的离散程度。
	//s=sqrt(((x1-x)^2 +(x2-x)^2 +......(xn-x)^2)/（n-1）)
	double sum=0;
	for(auto x:map)
		sum+=((x.second-avg)*(x.second-avg)/map.size());
	return sqrt(sum);
}
int main()
{
	for(int m=100;m<201;m++)
	{
		CacheManager::GetInstance().Init(10,m);
		for(int i=0;i<1000000;i++)
		{
			stringstream str;
			str<<i;
			TestCache(str.str());
			//		ShowRing();
		}
		Statistics::GetInstance().SetAvg(100000);
		Log::GetInstance().GetLog(m,Statistics::GetInstance().CalcResult());
		Statistics::GetInstance().Clear();
	}
}