vector, unordered_map 전체 순회 알고리즘 속도 비교

vector는 배열을, unordered_map은 hash_table를 사용해 hash를 구현한 모두 유명한 자료구조 컨테이너이다.

 

unordered_map의 탐색 시간 복잡도는 O(1)이다.

그렇다면 전체 순회의 경우 vector와 비교할 때는 어떻게 될까?

단순히 시간복잡도만을 계산하면 둘 다 O(n)인데 어떤 것이 더 빠를까? 

 

직접 해보자

#include <iostream>
#include <chrono>
#include <unordered_map>
#include <vector>

#define COUNTER 1000000


int main() {
	using namespace std::chrono;
	// std::chrono::milliseconds is an instatiation of std::chrono::duration:
	int tmp;
	std::vector<int> v;
	std::unordered_map<int, int> m;

	for (int i = 0; i < COUNTER; i++)
		v.push_back(i);

	for (int i = 0; i < COUNTER; i++)
		m[i] = i;

	auto startv = system_clock::now();

	for (auto iter = v.begin(); iter != v.end(); ++iter)
		tmp = (*iter);

	auto endv = system_clock::now();

	duration<double> vector_elapsed = endv - startv;
	std::cout <<"백만개 순회"<<"\n";
	std::cout <<"std::vector<int> : "<< vector_elapsed.count()<<"ms" << std::endl;

	auto startm = system_clock::now();

	//for (auto iter = m.begin(); iter != m.end(); ++iter)
	//	tmp = iter->second;
	for (int i = 0; i < COUNTER; i++)
		tmp = m[i];

	auto endm = system_clock::now();

	duration<double> map_elapsed = endm - startm;

	std::cout << "std::unordered_map<int, int> : " << map_elapsed.count() << "ms" << std::endl;

}

iterator로 접근하나 key로 접근하나 둘다 vector가 성능이 뛰어나다.

특히 key로 접근하는 경우에는 차이가 성능이 6배이상까지 벌어졌다.

iterator로 순회하는 경우

key로 접근하는 경우 

결론

생각해보면 전체순회의 경우는 당연히 unordered_map의 의도에 맞지않는 방법이다.  

전체 순회를 할 경우 vecter를 사용하자.

쓸대없는 짓을 하지말자.

 

 

REFERENCE

https://en.cppreference.com/w/cpp/container/unordered_map

 

https://en.cppreference.com/w/cpp/container/vector

 

• 논외로 map과 hash_map(unordered_map)에 대한 고찰도 있다. 좋은 글이니 여유가 되면 참고하시길 

https://gracefulprograming.tistory.com/3