기본 콘텐츠로 건너뛰기

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초 정도 걸린다는 이야기네.

댓글

이 블로그의 인기 게시물

Bash Array, Map 정리

Bash에서 Array, Map에 대한 정리. (매번 찾기 귀찮) 찾아보진 않았지만, Bash에서 Array든 Map이든 동일하게 Map(C++에서 Unordered Map)으로 동작하는 것 같다. 왜냐하면, Array의 Index가 연속하지 않아도 동작한다. 그저 Key가 0 이상의 정수인 Map이랑 비슷하게 동작한다. 예) 1, 2, 3, 9, 10 Array # 생성 declare -a empty_array declare -a ar=(haha hoho baba "long string haha hoho") # 접근 echo "ar[0]=${ar[0]}" echo "all as array=${ar[@]}" # 큰따옴표 안에서 각 원소를 따로따로 전달한다. echo "all as one=${ar[*]}" # 큰따옴표 안에서 각 원소를 문자열 하나로 합쳐 전달한다. echo "indexes=${!ar[@]}" echo "indexes=${!ar[*]}" echo "length=${#ar[@]}" echo "length=${#ar[*]}" echo "last=${ar[-1]}" echo "last=${ar[@]: -1}" # 콜론 뒤에 빈 칸이 꼭 필요하다. 옛 방식 # 현재 상황 declare -p ar #(출력) declare -a ar=([0]="haha" [1]="hoho" [2]="baba" [3]="long string haha hoho") ar[100]=hello # 인덱스를 건너 뛰어도 동작한다. declare -p ar #(출력) declare -a ar=([0]="haha" [1]="hoho" [2]="baba" [3]=&

설치한 패키지에서 RPM 추출하기

오래된 패키지를 관리할 저장소가 없어졌고, 기존 패키지로 다른 서버를 세팅해야할 일이 생겼다면 RPM의 리패키지 기능을 이용해보자. $ rpm -e --repackage [PACKAGE_NAME] 위와 같이 리패키지하면, /var/spool/repackage/ 에 생성한 RPM파일이 있다. :-)