지난번 블로깅에서 Functor가 가장 빠른 Iterating 속도를 보여줬으므로,
모든 Map Container에 대해서 Functor Iterating을 이용하여 측정하였다.
측정 환경 : Visual Studio 2008
측정 컨테이너 :
1. std::map
2. stdext::hash_map
3. boost::unordered_map
측정 방법 : Functor
map data의 순서 정렬 보장이 필요없는 경우에는 boost::unordered_map을 사용하는 것이 더 빠른 속도를 얻을 수 있다.
map container의 경우에는 균형 탐색 트리(balanced search tree)로 구현되어 있기 때문에, 로그(Log) 시간 복잡도를 보장한다.
unordered_map은 Hash 알고리즘으로 Bucket을 찾아가기 때문에 검색속도가 빠르고 향상된 검색 속도만큼 Iterating 시간이 짧이졌다.
그에 비해 hash_map의 경우에는 초기에 STL에 포함되지 않아서 각 컴파일러 제작 회사마다 각각 구현하여 포함되었으므로, Hash 알고리즘이 최적화되어 있지 않아서 Iterating 및 검색속도가 떨어지는 문제점이 있다.
덧글을 달아 주세요