std::map insertion

Standard Template Library에 잘 구현한 map(tree)과 string(char[]). 아무래도 map이 tree구조이기 때문에 insertion에서 list에 비해 느리다. 어따 끼워넣어야할지, 나무 균형 맞춰주기 등으로 좀 버벅이겠지. 근데 그게 어느 정돌까... 쓸만은 할까? 아래와 같은 상황에서 대충대충 짜봤다.

$ uname -s -r
Linux 2.6.18-8.1.3.el5

$ cat /proc/cpuinfo
Intel(R) Xeon(TM) CPU 3.06GHz 2장(생략했음)

$ free -m
             total       used       free     shared    buffers     cached
Mem:          2027       1330        697          0        283        690
-/+ buffers/cache:        356       1670
Swap:         4102          0       4102

$ g++ --version
g++ (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ rpm -qi libstdc++-devel
Name        : libstdc++-devel              Relocations: (not relocatable)
Version     : 4.1.1                             Vendor: CentOS
Release     : 52.el5.2                      Build Date:
Install Date:       Build Host: builder7.centos.org
Group       : Development/Libraries         Source RPM: gcc-4.1.1-52.el5.2.src.rpm
Size        : 45926400                         License: GPL
Signature   : DSA/SHA1, 2007년 04월 11일 (수) 오후 09시 06분 43초, Key ID a8a447dce8562897
URL         : http://gcc.gnu.org
Summary     : C++ 개발에 사용되는 헤더 파일과 라이브러리.
Description :
표준 C++ 라이브러리의 GNU 구현.  이 패키지는 C++ 개발에 필요한
헤더 파일과 라이브러리가 포함합니다. 이것은 다시 쓰여진 STL의 구현을
포함하고 있습니다.


STL버전이 다시 쓰여졌다네... -_- 뭐 몇몇가지 패치하거나 뭔가 우겨넣은거겠지? 아래는 mapstr.cpp라는 소스. 역시 개발괘발 만들어서 테스트.

#include <string>
#include <map>
#include <sys/time.h>
#include <unistd.h>
#include <iostream>
using namespace std;

int64_t
getTimestamp(void)
{
        static struct timeval tv;
        gettimeofday(&tv,NULL);
        return tv.tv_sec*1000000LL + tv.tv_usec;
}

typedef map<string,void*>       map_type;

const
string&
makeRandString(void)
{
        static string str;
        str.clear();
        size_t i(0), end(rand()%20+6);

        while ( i != end )
        {
                str += (rand()%26)+'a';
                ++i;
        }

        return str;
}

int
main(int,char**)
{
        map_type strmap;
        uint64_t i(0);
        const uint64_t end(2000000LLU);

        cerr << "start!" << endl;
        int64_t t1(getTimestamp());
        while ( i != end )
        {
                strmap.insert(make_pair(makeRandString(), (void*)NULL));
                ++i;
        }
        int64_t t2(getTimestamp());
        cerr << "end!" << endl;

        cout << "Total time: " << (t2-t1)/1000.0 << " ms" << endl;
        return 0;
}

컴파일하고 실행하자.

$ g++ -O2 -g -o mapstr mapstr.cpp

$ ./mapstr >> res.txt (16회 반복)


저 값 가운데 앞에 6개는 가볍게 버려주고 평균을 구했다.

13,633.25 ms

뭐, 대충 200만 건에 14초 정도 걸린다는 이야기네.

원본 위치: http://purewell.egloos.com/3244734