본문 바로가기
프로그래밍

[펌] Boost 로 C++0x의 라이브러리 「TR1」을 미리 사용 해 보 자 (5)

디비노 2012. 8. 13. 09:32

[중급] unordered containers

C ++의 새로운 규격 「C++0x」에 추가 예정의 라이브러리군 「TR1」의 개요를,Boost판을 사용해 해설합니다(Visual Studio 2008에도 추가 패키지로서 공급될 예정).

최종회는 「unordered컨테이너」에 대해서 입니다 

 

 

"unordered"의 의미　

"표준 C++ 라이브러리에는 set ,multiset ,map ,multimap 의 4개의 컨테이너가 준비되어 있습니다. 이것들은 binary-tree를 그 구현에 이용한 것입니다. 대소 관계에 근거해 요소를 binary-tree로 나누어 내린 것으로, 삽입이나 검색에 필요로 하는 시간 계산량은 Ο(logN) 즉 요소 수의 log에 비례합니다.

이번 TR1에서 새롭게 추가된 unordered_set, unordered_multiset, unordered_map, unordered_multimap은 종래의set, multiset, map, multimap 과 각각 기능적으로는 같습니다. 다른 것은 그 구현, binary-tree는 아니고 해시표(hash-table)가 이용되고 있습니다. 최대의 특징은 그 스피드에 있습니다.

 

해시표가 빠른 이유

　해시표는 간단하게 말하면 「일렬로 줄선 버켓」입니다.각각의 버켓에는 일련 번호가 붙어 있어 각 버켓에는 복수의 볼(요소)을 저장 할 수 있습니다. 버켓은 볼을 요소로 하는 가변장 배열이라고 생각해도 좋을 것입니다.

여기에 버켓이 한 개 있고 N개의 볼이 들어가 있다고 합시다. 볼에는 번호가 써 있습니다. 이 때 적당한 번호를 지정하고, 그 번호가 쓰여진 볼을 버켓안에서 찾아오는 것을 생각합니다.

버켓 안의 볼은 무 순서이기 때문에 목적의 볼을 찾아내려면 한개씩 꺼내어 그것이 목적의 것일까를 조사하지 않으면 안됩니다. 행운이 있다면 첫번째에 바로 찾을 수 있지만 최악의 케이스는 끝까지 조사했지만 발견되지 않았을 때입니다. 평균하면 볼 찾기에 필요한 비교 회수는 N/2 즉 검색에 필요로 하는 시간은 N에 비례합니다.

그럼 버켓을 두 개 준비해, 짝수 차례의 볼을 0 번 버켓에 / 홀수 차례의 볼을 1 번 버켓에 넣는다고 약속해 둡니다. 그러면 적당한 번호의 볼을 찾아내려면 그 번호가 짝수라면 0 번 버켓 / 홀수라면 1 번 버켓의 내용만을 조사하면 된다. 볼의 번호에 큰 편향이 없으면 각 버켓 내의 볼은 거의 동수의 N/2 그러니까, 검색에 필요로 하는 시간은 버켓 한 개의 경우의 반입니다.

이 상태로 버켓 수를 M개로 해, 각 볼은 거기에 붙은 번호를 M으로 나눈 나머지가 나타내 보이는 버켓에 넣읍시다. 그렇다면 검색 시에 조사하지 않으면 안 되는 볼의 수, 즉 검색에 필요로 하는 시간은 N/M으로 단축됩니다.

그 말은 M을 N과 같은 정도로 해 두면 N/M이 대체로 1이 됩니다. 이것은 볼의 총수에 관계없이 거의 순간에 검색이 종료하는 것을 의미합니다. 요소의 검색 대상이 되는 모집단의 요소 수를 1로 접근하는 것으로 검색 스피드를 올리려는 전략입니다.

여기서 중요한은 각 볼을 어느 버켓에 저장 할까를 결정하는 수단입니다. 상기의 예에서는 「볼 번호를 버켓 수로 나눈 나머지」라고 하고 있습니다만, 만약 볼 번호에 큰 편향이 있으면 버켓 내의 볼수에 편향이 생겨 검색 시간이 성장해 버립니다. 볼이 많이 찬 버켓과 거의 텅 빔의 버켓이 가능하게 되니까요.

요소(볼)x 로부터 어떠한 일의인 값(버켓 번호)을 도출하는 함수를 「해쉬 함수 h(x)」라고 이름 붙입시다. 해쉬 함수 h가 채우지 않으면 안 되는 조건은:

  1. x = y 이라면 h(x) = h(y)

입니다. 그렇지 않으면 볼 검색시에 들어가 있어야할 "모레의 버켓"안을 찾아 버리게 될테니까.

다만, x ≠ y 가 h(x) = h(y) 되는 일이 있습니다. 해쉬 함수 h 가 버켓 번호를 결정하므로 x 와 y는 같은 버켓에 저장 됩니다.

해쉬 함수가 돌려주는 값(해시 값)이 같은 요소군을 동의어(synonym:동의어)라고 부르고 있습니다.


클래스 템플릿: unordered_set

　TR1에는 해시표를 사용했다4종의 컨테이너가 정의되고 있습니다.

unordered_set : 요소의 중복을 허락하지 않는 집합

unordered_multise t: 요소의 중복을 허락하는 집합

unordered_map : 요소의 중복을 허락하지 않는 사전

unordered_multimap : 요소의 중복을 허락하는 사전

　이것들을 대표해 unordered_set에 대해서, 그 개요를 설명합니다. 

  1. namespace std {

  2. namespace tr1 {

  3. // [6.3.4.3] Class template unordered_set 

  4. template < class Value,

  5. class Hash = hash,

  6. class Pred = std::equal_to,

  7. class Alloc = std::allocator >

  8. class unordered_set;

  9. }

  10. }


　unordered_set 의 템플릿 인수는4개.

Value : 컨테이너 요소의 형태

Hash : Value (으)로부터 해시치를 요구하는 함수 오브젝트

Pred : 두 Va lue 하지만 동일할 때 true 되는 함수 오브젝트

Alloc : allocater

　Hash 의 디폴트 인수는 hash 그리고, Value (을)를 인수로 해 size_t (을)를 돌려준다 operator() (을)를 실장합니다.편입형과 문자열에 대해서는 표준 헤더 functional 에 정의되고 있습니다.이것들 이외의 형태를 요소로 한다unordered컨테이너를 이용할 때는 적절한 해쉬 함수 오브젝트를 주지 않으면 안됩니다.

 

   헤더:functional 에 정의된 hash

  1. namespace std {

  2. namespace tr1 {

  3. template < class T>

  4. struct hash : public std::unary_function size_t >

  5. {

  6. std:: size_t operator ()(T val) const ;

  7. };


  9. template <> struct hash< bool >;

  10. template <> struct hash< char >;

  11. template <> struct hash< signed char >;

  12. template <> struct hash< unsigned char >;

  13. template <> struct hash< wchar_t >;

  14. template <> struct hash< short >;

  15. template <> struct hash< unsigned short >;

  16. template <> struct hash< int >;

  17. template <> struct hash< unsigned int >;

  18. template <> struct hash< long >;

  19. template <> struct hash< unsigned long >;

  20. template <> struct hash< float >;

  21. template <> struct hash< double >;

  22. template <> struct hash< long double >;

  23. template <<span style="font-family:굴림체; font-size:9pt; color:#0000ff;"> class T> struct hash;

  24. template <> struct hash;

  25. template <> struct hash;

  26. }

  27. }


컨테이너에 대한 요소의 삽입/삭제/검색 및 열거에 관한 인터페이스는 종래의 set (와)과 다르지 않습니다:
insert : 요소의 삽입
erase : 요소의 삭제
clear : 전요소를 삭제해 컨테이너를 비운다
find : 요소의 검색
count : 검색에 의해서 일치한 요소수
equal_range : 검색에 의해서 일치하는 요소 위치의 범위

unordered 컨테이너 독자적인 멤버 함수를 이하에 나타냅니다:
bucket_count
size_type bucket_count() const
   컨테이너 내의 버켓의 수를 돌려줍니다.

max_bucket_count

size_type max_bucket_count() const

　컨테이너 내에 내포 할 수 있는 버켓의 최대수를 돌려줍니다.


bucket

size_type bucket(k)

　요소 k가 저장 될 버켓의 번호를 돌려줍니다.


bucket_size
size_type bucket_size(n)
　n번째의 버켓에 격납된 요소수를 돌려줍니다.

begin

local_iterator begin(n)

const_local_iterator begin(n) const

　n번째의 버켓에 저장된 요소의 선두 위치를 돌려줍니다.


end

local_iterator end(n)

const_local_iterator end(n) const

　n번째의 버켓에 격납된 요소의 말미 위치를 돌려줍니다.


load_factor

float load_factor() const

　버켓에 저장 되고 있는 요소 수의 평균치, 즉 요소 수/버켓 수를 돌려줍니다.


max_load_factor

float max_load_factor() const

　버켓에 저장되는 요소 수의 평균치의 상한을 돌려줍니다. 요소의 삽입에 의해서 이 상한치를 넘었을 때, 새로운 버켓이 추가되어 각 요소가 물통에 재배분됩니다.

void max_load_factor( float z)

　버켓에 저장 되는 요소수의 평균치의 상한을 z로 설정합니다.


rehash

void rehash(size_type n)

　버켓 수가 적어도  n이 되도록 버켓 수가 조정되어 각 요소가 재배분됩니다.

 

 

set 와의 속도 비교

마지막으로 해시표에 의한  unordered_set 과 binary-tree에 의한 set 과의 속도를 비교해 봅시다. 1~100000의 난수를 2백만개 삽입했을 때의 각각의 소요 시간을 계측합니다. 난수의 생성에는 같은 TR1에 수록된 메르센누·트이스타를 이용했습니다.

     set  대  unordered_set 속도 비교

  1. // min/max매크로의 간섭 방지

  2. #define NOMINMAX

  3. #include <windows.h>

  4. #include <iostream>

  5. #include <set>

  6. #include <unordered_set>

  7. #include <unordered_map>

  8. #include <random>


  10. using namespace std;


  12. int main() {

  13. set< int > s;

  14. tr1::unordered_set< int > us;

  15. const int N = 100000;

  16. tr1::mt19937 rng; // 메르센누·트이스타 

  17. tr1::uniform_int<> dice(1,N); // 정수일 모양 분포 

  18. tr1::variate_generator
         <tr1::mt19937&, tr1::uniform_int<> > sample(rng, dice);

  19. long t;

  20. const int TIMES = 2000000;

  21. rng.seed(12345);

  22. t = GetTickCount();

  23. for ( int i = 0; i < TIMES; ++i ) {

  24. s.insert(sample());

  25. }

  26. t = GetTickCount() - t;

  27. cout << t << "(set)\n" ;


  29. rng.seed(12345);

  30. //us.rehash(N);　/* 버켓수의 조정 */ 

  31. t = GetTickCount();

  32. for ( int i = 0; i < TIMES; ++i ) {

  33. us.insert(sample());

  34. }

  35. t = GetTickCount() - t;

  36. cout << t << "(unordered_set)\n" ;

  37. }


실행 결과

1562(set)

1188(unordered_set)

　

25% 정도 unordered_set 쪽이 빠른 것 같습니다. 그다지 큰 속도 차이가 나지 않았습니다만 이것은 컨테이너 내에 요소가 추가되는에 따라서 버켓수의 확장과 요소의 재배분이 자주 행해지는데 필요로 하는 시간을 포함하고 있습니다. 코드중 정도의 //us.rehash(N); 의 코멘트를 없애, 최초부터 충분한 수의 버켓을 확보했을 경우 실행 결과는:

  1. 1563(set)

  2. 875(unordered_set)

되어, set 의 약2배의 속도를 얻을 수 있었습니다.

 

정리정리

5회에 걸쳐서 새로운 C++: C++0x 에서 제공되는 표준 C++ 라이브러리의 확장:TR1의 개요를 해설했습니다. TR1 이 제공하는 기능은 이것으로 모두가 아닙니다.상기 샘플로 아주 조금 보여드리고 있는 난수나 컴파일 시에 형태를 판정하는type_traits 등도 포함됩니다.

현재의 표준 C++ 라이브러리는 컨테이너/알고리즘/이테레이타 및 함수 오브젝트를 중심으로 한 것이었습니다. TR1은 이것들에 더해 이용 빈도가 높음에도 불구하고 지금까지 표준의 존재하지 않았던 기능군을 강화해, 표준 라이브러리를 거의 2배의 양으로 확장합니다.

Java 나 C#, VB.NET 등에 비해 압도적으로(?) 복잡/난해하기 때문에 경원 되기 십상인 C++ 이지만, C++의 활약하는 분야는 계속 여전히 있습니다.

 

 

 

번역 후기........

번역된 글을 퍼 갈 때는 꼭 아래의 글을 같이 복사 해 주세요.

번역은 원 저자에게 허락을 받은 것은 아니므로 상업적으로 사용할 경우에는 꼭 원저자에게 허락을 받기를 바랍니다.

출처 : http://codezine.jp/a/article/aid/2171.aspx

 

번역 :   choi_2.jpg   최흥배 ( jacking75@gmail.com ).

             (주) 다이슨 파이퍼스튜디오에서 서버 프로그래머로 근무 중.

저작자표시

'프로그래밍' 카테고리의 다른 글

[펌] ACE 강의(1)  (0) 2012.08.13
[펌] ACE_Message_Block Pool 만들기  (0) 2012.08.13
[펌] Boost 로 C++0x의 라이브러리 「TR1」을 미리 사용 해 보자 (4)  (0) 2012.08.13
[펌] Boost 로 C++0x의 라이브러리 「TR1」을 미리 사용 해 보자 (3)  (0) 2012.08.13
[펌] Boost 로 C++0x의 라이브러리 「TR1」을 미리 사용 해 보자 (1)  (0) 2012.08.13

'프로그래밍' Related Articles

티스토리툴바