C++ 速度比較(7) unordered_map,mapの違い、速度の面から検討する

皆さんこんにちは
お元気ですか。ふらふらしてます。

さて、今日は速度比較を行おうと思います。

概略については前回の記事を参考にしてください

実験

実験内容

１、全てをループした時に速度がどうなるか
→iterater と foreach それぞれで検証するので４種類
10000000000回のループで検証

２、アクセスに差が出るのか
→アクセスする場所（？）によって差が出るのか。atメソッド含めて５種類
0とN-1にアクセスした時で差が出るのかわからない。また一種類だけatメソッドを混入する。
1000000回のループで検証

実験環境

結果

全出力

algorithm	time(秒)
unordered_iterator	212.942
unordered_foreach	75.5393
map_iterator	484.02
map_foreach	313.835

アクセス

algorithm	time(秒)
unordered_0	0.285083
unordered_AN-1	0.194741
map_iterator_0	0.075297
map_foreach_N-1	0.076464

考察

ソートの影響を受けた結果となっている。
ソートの必要性があるものについてはmap、そうでなければunordered_mapで良いと思う。

アクセスに関する内容でも、木構造とハッシュマップにおける差が顕著に出ている。（計算によるアクセスと木をたどりながらアクセスするのとの違い）
用途によってunordered_mapを利用するかmapを利用するか検討中。

ソースコード

#include <iostream>
#include <unordered_map>
#include <map>

#define N 1000000
#define T 10000
#define AN 1000000
using namespace std;


void iterator_unordered_map(unordered_map<int,int> &mp){
	unordered_map<int,int>::iterator itr = mp.begin();
	for(itr; itr!=mp.end(); itr++){
		int x = itr->first;
	}
}

void foreach_unordered_map(unordered_map<int,int> &mp){
	for(auto &pair:mp){
		int x = pair.first;
	}
}

void foreach_map(map<int,int> &mp){
	for(auto &pair:mp){
		int x = pair.first;
	}
}

void iterator_map(map<int,int> &mp){
	map<int,int>::iterator itr = mp.begin();
	for(itr; itr!=mp.end(); itr++){
		int x = itr->first;
	}
}

//全ての要素を調べる
void compareAccessSpeedAllElement(unordered_map<int,int> &u_mp,map<int,int> &mp){
	cout << "compare access speed all element" << endl;
	cout << "unordered_map iterator" << endl;
	clock_t start = clock();
	for(int t = 0; t < T; t++){
		iterator_unordered_map(u_mp);
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "unordered_map foreach" << endl;
	start = clock();
	for(int t = 0; t < T; t++){
		foreach_unordered_map(u_mp);
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "map iterator" << endl;
	start = clock();
	for(int t = 0; t < T; t++){
		iterator_map(mp);
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "map foreach" << endl;
	start = clock();
	for(int t = 0; t < T; t++){
		foreach_map(mp);
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;
}

//アクセス速度を検証する
void compareAccessSpeed(unordered_map<int,int> &u_mp,map<int,int> &mp){
	cout << "map access 0" << endl;

	clock_t start = clock();
	for(int j = 0; j < AN; j++){
		int x = mp[0];
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "map access N - 1" << endl;

	start = clock();
	for(int j = 0; j < AN; j++){
		int x = mp[N-1];
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "unordered_map access 0" << endl;
	start = clock();
	
	for(int j = 0; j < AN; j++){
		int x = u_mp[0];
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "unordered_map access N - 1" << endl;
	start = clock();

	for(int j = 0; j < AN; j++){
		int x = u_mp[N-1];
	}


	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

	cout << "use at method for unordered_map access N - 1" << endl;
	start = clock();

	for(int j = 0; j < AN; j++){
		int x = u_mp.at(N-1);
	}

	cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char const *argv[])
{
	unordered_map<int,int> u_mp;
	for(int i = 0; i < N; i++){
		u_mp[i] = i;
	}
	map<int,int> mp(u_mp.begin(),u_mp.end());
	compareAccessSpeedAllElement(u_mp,mp);
	compareAccessSpeed(u_mp,mp);

	return 0;
}