STL의 컨테이너 중에서 Hash 검색 알고리즘을 사용하고 있는 map 컨테이너를 테스트 해보았다. Hash 검색 알고리즘은 검색 항목의 개수에 상관없이 검색시간은 항상 일정하다라고 되어 있다. 바로 이것을 테스트해 보고자 했다.
N의 개수는 천만(10,000,000)개를 생성했으며 hash key는 unsigned long 타입으로 했다. 0, 2000000, 5000000, 7000000, 9999999 hash key 값을 검색하여 그곳에 -1을 넣었다. 과연 상수 시간이 나올 것인가? 나올 경우 시간은 얼마나 걸릴것인가...
아래는 그 결과다..
#include <map>
#include <sys/timeb.h>
#include <time.h>
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<unsigned long, unsigned long> 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;
}
이 글이 도움이 되셨다면, 짧은 댓글이라도 달아주시길, 큰 힘이 됩니다. ^^*
|
Commented by
