Map Container Iterating

이번엔 Map Container Iterating에 대해서 측정해 보았다.

지난번 블로깅에서 Functor가 가장 빠른 Iterating 속도를 보여줬으므로,
모든 Map Container에 대해서 Functor Iterating을 이용하여 측정하였다.

측정 환경 : Visual Studio 2008
측정 컨테이너 :
    1. std::map
    2. stdext::hash_map
    3. boost::unordered_map
측정 방법 : Functor

std::map과 boost::unordered_map은 약 2:1의 측정 속도 차이를 보여준다.
map data의 순서 정렬 보장이 필요없는 경우에는 boost::unordered_map을 사용하는 것이 더 빠른 속도를 얻을 수 있다.
map container의 경우에는 균형 탐색 트리(balanced search tree)로 구현되어 있기 때문에, 로그(Log) 시간 복잡도를 보장한다.
unordered_map은 Hash 알고리즘으로 Bucket을 찾아가기 때문에 검색속도가 빠르고 향상된 검색 속도만큼 Iterating 시간이 짧이졌다.
그에 비해 hash_map의 경우에는 초기에 STL에 포함되지 않아서 각 컴파일러 제작 회사마다 각각 구현하여 포함되었으므로, Hash 알고리즘이 최적화되어 있지 않아서 Iterating 및 검색속도가 떨어지는 문제점이 있다.
2010/04/11 21:20 2010/04/11 21:20

글 걸기 주소 : 이 글에는 트랙백을 보낼 수 없습니다

덧글을 달아 주세요