2007-03-082017-01-29 글쓴이 김 형준

STL의 map 컨테이너 테스트

STL의 컨테이너 중에서 Hash 검색 알고리즘을 사용하고 있는 map 컨테이너를 테스트 해보았다. Hash 검색 알고리즘은 검색 항목의 개수에 상관없이 검색시간은 항상 일정하다라고 되어 있다. 바로 이것을 테스트해 보고자 했다.

N의 개수는 천만(10,000,000)개를 생성했으며 hash key는 unsigned long 타입으로 했다. 0, 2000000, 5000000, 7000000, 9999999 hash key 값을 검색하여 그곳에 -1을 넣었다. 과연 상수 시간이 나올 것인가? 나올 경우 시간은 얼마나 걸릴것인가…

아래는 그 결과다..

소요 시간은 분명 상수이긴 한데…. 0초다. 분명 0초는 아니겠지만 거의 0초가 걸린다. 사실 믿기지가 않는다. 아래는 테스트한 코드인데… 잘못된 부분이라도 있는건가? 옳바르다면 stl의 map 컨테이너는 정말 물건이다…

<#include 
#include <sys/timeb.h>
#include 

using namespace std;

void PerformanceTest(bool bStart, const char *szTitle="") {
    static timeb start;
    static timeb stop;

    if(bStart) {
        ftime(&start);
    } else {
        ftime(&stop);

        double gab;
        gab = 1.0e3 * difftime(stop.time, start.time);
        gab+=(double)(stop.millitm - start.millitm);

        double ReturnValue = gab/1.0e3;
        printf( "%s: %.10lf sec required.\n", szTitle, ReturnValue);
    }
}

map container_;

int _tmain(int argc, _TCHAR* argv[])
{
    PerformanceTest(true);
    for(unsigned long i=0; i<10000000; i++) {
        container_[i] = i;
    }
    PerformanceTest(false, "generating 10000000 data");

    printf("Now container has %ld items.\n\n", container_.size());

    for(size_t i=0; i<5; i++) {
        PerformanceTest(true);
        container_[0] = -1;
        PerformanceTest(false, "finding index 0:");

        PerformanceTest(true);
        container_[2000000] = -1;
        PerformanceTest(false, "finding index 2000000:");

        PerformanceTest(true);
        container_[5000000] = -1;
        PerformanceTest(false, "finding index 5000000:");

        PerformanceTest(true);
        container_[7000000] = -1;
        PerformanceTest(false, "finding index 7000000:");

        PerformanceTest(true);
        container_[10000000-1] = -1;
        PerformanceTest(false, "finding index 9999999:");
    }

    printf("\n[%ld %ld %ld %ld %ld]\n", 
        container_[0], 
        container_[2000000], 
        container_[5000000], 
        container_[7000000], 
        container_[9999999]
    );

    return 0;
}

“STL의 map 컨테이너 테스트”에 대한 6개의 댓글

잿빛날개 댓글:

2007-03-09, 3:20 오후

아무래도 함수 한번 호출에 걸리는 시간이 너무 짧아서
타이머가 시간을 제대로 측정 못하는게 아닐까요?
그리고 타이머 함수를 호출하는 자체에도 어느정도 시간이
걸리므로 결과값이 나온다고 해도 부정확할 가능성이
높을듯 합니다. 적어도 루프를 돌아서 수백, 수천번 검색하는
시간을 측정 하는게 옳을듯 싶네요.

댓글달기
잿빛날개 댓글:

2007-03-09, 3:29 오후

그리고 해시맵의 경우 이론상으로는 상수 시간이지만
해시 함수의 알고리즘과 해시맵 테이블의 크기등에 따라 값의
충돌이 일어나므로 현실적인 성능은 좀 떨어집니다.
그래도 항상 많은수의 비교가 일어나는 트리로 구현된
map과 비교하면 단 한번의 비교만 일어날 확율이 높은 해시맵이
성능상에서 상당한 우위을 차지하죠.^^

댓글달기
잿빛날개 댓글:

2007-03-09, 3:51 오후

아, 근데 소스를 다시보니 그냥 map을 include하셨군요.;;
stl에서 그냥 map은 해시를 사용 하는게 아니라
적흑트리를 사용합니다.
hash를 사용하는 stl의 맵은 unordered_map인데
아직은 네임 스페이스가 tr1이며 정식 std네임 스페이스로
들어오지 않은걸로 알고 있습니다.
그나마도 아직 tr1을 지원하는 컴파일러가 별로 없고요.
st구현l에 따라서 비표준으로 hash_map을 제공하는
경우도 있는데 제 컴파일러의 hash_map은 버그가 있더군요.
간혹 잘못된 값을 찾아서 활용 못하고 그냥 방치하고 있습니다.^^;;

댓글달기
김형준 댓글:

2007-03-10, 9:16 오전

그렇군요, map은 해시가 아니라 트리군요.. 방문 책을 찾아보니 트리 구조라고 되어있네요. 저는 지금까지 해시로 구현되어진줄알았답니다. 좋은 지적감사합니다..

댓글달기
김형준 댓글:

2007-03-10, 9:22 오전

그리고 다시 테스트를 해보았습니다. 검색하는 코드를 백만번 호출하는 것으로 변경해서해보았구요.. 테스트 코드는 ..

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의 성능은 정말 놀랍다는 생각이 듭니다.

댓글달기
잿빛날개 댓글:

2007-03-10, 9:45 오전

트리로 구성된 map도 검색에 걸리는 시간이 O(logN)이므로
왠만한 경우에선 충분히 빠르죠.
hash_map보다 메모리도 덜 낭비하고요.^^

댓글달기

“STL의 map 컨테이너 테스트”에 대한 6개의 댓글

답글 남기기 응답 취소