GIS Developer

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;
}

2달전에 구입한 MP3 플레이어. 살까말까 고민에 고민을 거듭하다가 샀다. 처음엔 오로지 MP3 기능에 충실한 iRiver의 S7을 사려고 했으나, 화이트노이즈가 있다는 말에 여타 다른 MP3 플레이어 중에서 가장 음장이 좋다는 F2로 결정했다.

MP3만 넣고 듣는 용도에 사용하려고 1기가로 결정했으나, 지금은 USB 저장장치로써 온갓 데이터와 인증서는 물론이고 가끔 영화도 넣고 본다. 영화를 넣고 볼때 대대적인 MP3 숙청 작업이 이뤄질때 1기가로 결정한 것을 후회한다. 무척 작은 화면에서 보는 영화지만 전철이나 버스 안에서 혼자 보기엔 뭐… 그런대로 봐줄만하다.

지난주에 교보문고에 가서 산 볼륨있는 하트 스티커를 9개의 버튼에 붙여 놓았다. 이쁜 모양은 물론이거니와 버튼을 누를때 보다 더 정확하게 눌를 수 있어서 대만족이다. 다만 저 스티커 가격이 3천원 ㅜ_ㅜ 이라는게 가슴 미어지긴 하지만 말이다….

처음엔 MP3 플레이어 보호를 위한 쉴드에 넣고 다녔으나, 이왕산거 맘편이 마구 마구 아껴(?) 사용하려고 쉴드를 제거했다. 나름대로 장식도 해 넣고 애지중지하지 않고 맘 편하게 그래도 나름 소중하게 사용해서 그런지 지금은 무척 애착이 가는 내 분신같은 물건이 되었다.

아래는 이 MP3 플레이어에서 사용하는 2개의 바탕화면 이미지이다. 처음엔 오른쪽 이미지를 사용했으나, 지금은 왼쪽 이미지를 사용하고 있다. 참고로 이 이미지 크기로 동영상이 나온다.

글

STL의 map 컨테이너 테스트

My MP3 Player, Cowon F2