G.I.S Developer, 개발자 김형준(Dip2K): STL의-map-컨테이너-테스트에 달린 최근 댓글/트랙백 목록http://www.gisdeveloper.co.kr/2010-08-08T13:52:21+09:00Textcube 1.7.7 : Con moto잿빛날개님의 댓글(잿빛날개)http://www.gisdeveloper.co.kr/212#comment70502007-03-10T00:20:52+09:00아무래도 함수 한번 호출에 걸리는 시간이 너무 짧아서
타이머가 시간을 제대로 측정 못하는게 아닐까요?
그리고 타이머 함수를 호출하는 자체에도 어느정도 시간이
걸리므로 결과값이 나온다고 해도 부정확할 가능성이
높을듯 합니다. 적어도 루프를 돌아서 수백, 수천번 검색하는
시간을 측정 하는게 옳을듯 싶네요.잿빛날개님의 댓글(잿빛날개)http://www.gisdeveloper.co.kr/212#comment70512007-03-10T00:29:57+09:00그리고 해시맵의 경우 이론상으로는 상수 시간이지만
해시 함수의 알고리즘과 해시맵 테이블의 크기등에 따라 값의
충돌이 일어나므로 현실적인 성능은 좀 떨어집니다.
그래도 항상 많은수의 비교가 일어나는 트리로 구현된
map과 비교하면 단 한번의 비교만 일어날 확율이 높은 해시맵이
성능상에서 상당한 우위을 차지하죠.^^잿빛날개님의 댓글(잿빛날개)http://www.gisdeveloper.co.kr/212#comment70522007-03-10T00:51:23+09:00아, 근데 소스를 다시보니 그냥 map을 include하셨군요.;;
stl에서 그냥 map은 해시를 사용 하는게 아니라
적흑트리를 사용합니다.
hash를 사용하는 stl의 맵은 unordered_map인데
아직은 네임 스페이스가 tr1이며 정식 std네임 스페이스로
들어오지 않은걸로 알고 있습니다.
그나마도 아직 tr1을 지원하는 컴파일러가 별로 없고요.
st구현l에 따라서 비표준으로 hash_map을 제공하는
경우도 있는데 제 컴파일러의 hash_map은 버그가 있더군요.
간혹 잘못된 값을 찾아서 활용 못하고 그냥 방치하고 있습니다.^^;;김형준님의 댓글(김형준)http://www.gisdeveloper.co.kr/212#comment70532007-03-10T18:16:41+09:00그렇군요, map은 해시가 아니라 트리군요.. 방문 책을 찾아보니 트리 구조라고 되어있네요. 저는 지금까지 해시로 구현되어진줄알았답니다. 좋은 지적감사합니다.. 김형준님의 댓글(김형준)http://www.gisdeveloper.co.kr/212#comment70542007-03-10T18:22:46+09:00그리고 다시 테스트를 해보았습니다. 검색하는 코드를 백만번 호출하는 것으로 변경해서해보았구요.. 테스트 코드는 ..
PerformanceTest(true);
for(size_t i=0; i<1000000; i++) {
container_[0] = -1;
}
PerformanceTest(false, "finding index");
PerformanceTest(true);
for(size_t i=0; i<1000000; i++) {
container_[2000000] = -1;
}
PerformanceTest(false, "finding index");
PerformanceTest(true);
for(size_t i=0; i<1000000; i++) {
container_[5000000] = -1;
}
PerformanceTest(false, "finding index");
PerformanceTest(true);
for(size_t i=0; i<1000000; i++) {
container_[7000000] = -1;
}
PerformanceTest(false, "finding index");
PerformanceTest(true);
for(size_t i=0; i<1000000; i++) {
container_[10000000-1] = -1;
}
PerformanceTest(false, "finding index");
결과는 ..
finding index: 0.1090000000 sec required.
finding index: 0.2660000000 sec required.
finding index: 0.2660000000 sec required.
finding index: 0.2500000000 sec required.
finding index: 0.4370000000 sec required.
맨 마지막 요소를 찾는데 가장 많은 시간이 소요되는군요..
음.. 그래도 역시 map의 성능은 정말 놀랍다는 생각이 듭니다.잿빛날개님의 댓글(잿빛날개)http://www.gisdeveloper.co.kr/212#comment70552007-03-10T18:45:42+09:00트리로 구성된 map도 검색에 걸리는 시간이 O(logN)이므로
왠만한 경우에선 충분히 빠르죠.
hash_map보다 메모리도 덜 낭비하고요.^^