boost::unordered_map

http://blog.naver.com/titetoto123/130139993684

★ unordered_map ★

해쉬 맵으로서 원소 타입은 value_type이다

 

#include <unordered_map>

 

 

int _tmain(int argc, _TCHAR* argv[])

{

        unordered_map<int, int&> pGlobal;

        CSub2 pSub;

 

        pGlobal.insert(unordered_map<int,int&>::value_type(1,pSub.GetTest()));

 

        std::cout<<&pSub.GetTest()<<std::endl;

 

        unordered_map<int, int&>::iterator iter;

        iter = pGlobal.find(1);

        std::cout<<&(iter->second)<<std::endl;

 

        return 0;

}

[출처] ★ unordered_map ★|작성자 titetoto123

---

http://cafe.naver.com/totalprogramming/88

boost에는 기존 C++ 표준 라이브러리에 없는 해쉬맵을 제공한다.

TR1에도 포함되어 있다. 앞으로 표준에 등록될 예정이다.

 

http://www.boost.org/doc/libs/1_36_0/doc/html/unordered.html

 

사용법은 기존 C++에서 map을 사용 하던 방식과 똑같고, c++의 맵과 다른점은

연산을 통해 상수시간에 검색한다는 것이다.

 

typedef boost::unordered_map<std::string, int> map;
map x;
x["one"] = 1;
x["two"] = 2;
x["three"] = 3;

assert(x.at("one") == 1);
assert(x.find("missing") == x.end());

---

이하는 Boost 와 TR1 성능비교이고 결론적으론 Boost 가 빠르다는 결론

---

http://cafe.naver.com/ongameserver/6797

각 각 100만개의 데이터를 토대로

Integer, string length = 10

 

키를 가지고 비교하였습니다. 별도의 키의 hash를 구현할 시 각각 틀릴 수 있으므로 integer와 std::string만 사용하였습니다.

 

[사양]

Inter Core i7-2600 CPU 3.40GHz

 

VS2008 SP1

 

[속도 체크]

Integer 개수 100만개 1~ 1000000

	Insert			Find			Delete
	Second	MilliSecond	Micro second	Second	MilliSecond	Micro second	Second	MilliSecond	microsecond
Std::map	0.197763	197.763189	197763.188756	0.000002	0.002113	2.112990	0.000005	0.005433	5.43340.
Std::tr1::unordered_map	0.124919	124.918763	124918.763080	0.000001	0.001207	1.207423	0.000002	0.001509	1.509279
Std::tr1::unordered_mapwith boost::fast_pool_allocator	0.0059479	59.478556	59478.556321	0.000001	0.001207	1.207423	0.000001	0.001207	1.207423
Boost::unordered_map	0.083059	83.058921	83058.921331	0.000000	0.000302	0.301856	0.000001	0.000906	0.905567
Boost::unordered_mapwith boost::fast_pool_allocator	0.086212	86.21248	86212.408021	0.000001	0.000604	0.603711	0.00000	0.00302	0.301856

 

 

문자열 개수 100만개 랜덤 (아스키 65 ~ 127) 조합 10글자

 

	Insert			Find			Delete
	Second	MilliSecond	Micro second	Second	MilliSecond	Micro second	Second	MilliSecond	microsecond
Std::map	0.978266	978.266388	978266.388275	0.000005	0.004528	4.152736	0.000005	0.005132	5.1315747
Std::tr1::unordered_map	0.451236	451.235661	451235.661476	0.000002	0.001811	1.811134	0.000002	0.001811	1.811134
Std::tr1::unordered_mapwith boost::fast_pool_allocator	0.481112	481.112133	481112.133060	0.000002	0.001509	1.509279	0.000002	0.001811	1.811134
Boost::unordered_map	0.498683	498.683154	498683.154428	0.000001	0.001207	1.207423	0.000002	0.001509	1.509279
Boost::unordered_mapwith boost::fast_pool_allocator	0.484535	484.535479	484535.478763	0.000001	0.00604	0.603711	0.000001	0.000604	0.603711

 

 

데이터가 100만개씩이라 디버깅으로는 안 돌렸습니다. 예전에 분석 결과로 기억나는 건 BOOST, TR1 둘다 디버깅 시에 검증 코드 엄청나서 느리다고 알고 있습니다. (안그래도 많은데…;;)

기존에 회사에서 저희팀에게 속도를 알리기 위하여 테스트 결과를 공유합니다. 

ATL은 빠져있습니다. 

결과는 좋은 색을 찾아 보시면 됩니다. 

현직에 계시는 분들 중에 boost라이브러리나 외부 라이브러리를 많이 사용하시는 편입니까?

(저희팀은 현재 외부라이브러리는 안쓰고 있습니다.)

---

http://blog.daum.net/naganolacpp/33

디버그 모드 10,0000번 루프

- TR1 -

삽입 2.187

검색 0.422

삭제 35.953

100,0000번 루프시 삭제 결과가 안나와 10,0000번으로 측정

- Boost -

삽입 3.328

검색 0.922

삭제 1.953

-------------------------------------------

릴리즈 모드 100,0000번 루프

- TR1 -

삽입 0.421

검색 0.11

삭제 0.547

- Boost -

삽입 0.281

검색 0.031

삭제 0.25

 

결론 : TR1보단 Boost

 

/**

*    test 소스 코드

*    shared_ptr도 살포시 돌려보았으나 별차이가 없었다.

*/

#include <unordered_map>
#include <memory>
#include <boost/unordered_map.hpp>
#include <boost/shared_ptr.hpp>
#include <vector>

#include <boost/timer.hpp>
#include <iostream>

template< typename T >
inline void Insert( T &map )
{
 boost::timer t;
 t.restart();
 for( size_t i = 0 ; i < 100000 ; ++i )
 {
  map.insert( std::pair<int,int>( i, i ) );  
 }
 std::cout << "삽입"<< t.elapsed() << std::endl;
};

template< typename T >
inline void Search( T &map )
{
 boost::timer t;
 t.restart();
 for( size_t i = 0 ; i < 100000; ++i )
 {
  map.find( i );
 }
 std::cout << "검색"<< t.elapsed() << std::endl;
};

template< typename T >
inline void Erase( T &map )
{
 boost::timer t;
 t.restart();
 for( size_t i = 0 ; i < 100000; ++i )
 {
  map.erase( i );
 }
 std::cout << "삭제"<< t.elapsed() << std::endl;
};

/*
template< typename T , typename Type >
inline void SharedCreate( std::vector<T> &list )
{
 list.resize(1000000);
 boost::timer t;
 t.restart();
 for( size_t i = 0 ; i < 1000000 ; ++i )
 {
  list[i] = T( new Type );
 }
 std::cout << "shard_ptr Create "<< t.elapsed() << std::endl;
}

class Test
{
public:
 void Run( void )
 {
  int a;
 }
};
template< typename T >
inline void SharedGetTest( std::vector<T> &list )
{
 boost::timer t;
 t.restart();
 size_t size = list.size();
 for( size_t i = 0 ; i < size; ++i )
 {
  list[i]->Run();
 }
 std::cout << "shard_ptr Run Test : "<< t.elapsed() << std::endl;
}
*/
void main()
{  
 std::tr1::unordered_map<int , int > tr1Map;
 std::cout << "- TR1 -\n";
 Insert( tr1Map );
 Search( tr1Map );
 Erase( tr1Map );

 boost::unordered_map<int , int > boostMap;
 std::cout << "- Boost -\n";
 Insert( boostMap );
 Search( boostMap );
 Erase( boostMap );
/*
 std::cout << "- Boost -\n";
 std::vector< boost::shared_ptr<Test> > boostShared;
 boostShared.resize(1000000);
 SharedCreate< boost::shared_ptr<Test>, Test >( boostShared );
 SharedGetTest( boostShared );

 std::cout << "- TR1 -\n";
 std::vector< std::tr1::shared_ptr<Test> > tr1Shared;
 tr1Shared.resize(1000000);
 SharedCreate<  std::tr1::shared_ptr<Test>, Test >( tr1Shared );
 SharedGetTest( tr1Shared );
 */
}

---

http://npteam.net/779

Map Container Iterating

::NPTEAM:: Network Programer Team

프로그래밍/STL

2010/04/11 21:20, 글쓴이 TTF

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

지난번 블로깅에서 Functor가 가장 빠른 Iterating 속도를 보여줬으므로,

모든 Map Container에 대해서 Functor Iterating을 이용하여 측정하였다.

측정 환경 : Visual Studio 2008

측정 컨테이너 :

    1. std::map

    2. stdext::hash_map

    3. boost::unordered_map

측정 방법 : Functor

(1/1)   

(1/1)   

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 및 검색속도가 떨어지는 문제점이 있다.