Untitled

mail@pastecode.io avatar
unknown
c_cpp
6 months ago
2.1 kB
3
Indexable
Never
#include <iostream>
#include <map>
#include <ctime>
#include <unordered_map>
#include <chrono>
using namespace std;

class mockHashMap {
public:
	void put(int key, int val);
	int get(int key);
	double measure_put_load();
	double measure_get_load();

private:
	unordered_map<int, int> m;
	map<time_t, int> getTime; // time, count
	map<time_t, int> putTime;
	time_t getCurrentTimestamp();
};


time_t mockHashMap::getCurrentTimestamp(){
	time_t t = time(nullptr); // ??????? difference?

	// auto now = chrono::system_clock::now();
    // auto seconds_since_epoch = chrono::duration_cast<chrono::seconds>(now.time_since_epoch()).count();

    // time_t t = static_cast<time_t>(seconds_since_epoch);

	return t;
}


void mockHashMap::put(int key, int val){
	m[key] = val;
	time_t t = getCurrentTimestamp();
	putTime[t]++;
}

int mockHashMap::get(int key){
	if(m.find(key) == m.end()){
		return 0;
	}
	time_t t = getCurrentTimestamp();
	getTime[t]++;
	
	return m[key];
}

double mockHashMap::measure_put_load(){ // O(log n)
	time_t t = getCurrentTimestamp();

	auto start = putTime.lower_bound(t - 300);
	auto end = putTime.upper_bound(t);

	int count;
	for(auto it = start; it != end; ++it){
		count += it->second;
	}

	return count / (double)300;
}

double mockHashMap::measure_get_load(){ // O(log n)
	time_t t = getCurrentTimestamp();

	auto start = getTime.lower_bound(t - 300);
	auto end = getTime.upper_bound(t);

	int count;
	for(auto it = start; it != end; ++it){
		count += it->second;
	}

	return count / (double)300;
}


int main(){
	mockHashMap myHashMap;
	myHashMap.put(10, 5);
	myHashMap.put(20, 20);
	int getResult = myHashMap.get(10);
	cout << "getResult = " << getResult << endl;


	double putLoad = myHashMap.measure_put_load();
	cout << "putLoad = " << putLoad << endl;
	double getLoad = myHashMap.measure_get_load();
	cout << "getLoad = " << getLoad << endl;

}


/*

get/put O(1)
measure O(log(m)) ???????????

m為目前的get或put次數

1. 這樣get/put如何達到O(1)?????? measure 如何O(log m)??? 直接lower_bound算嗎?
2. timestamp



*/