"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에 비례합니다.

 

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

 

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

 

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

 

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

 

요소()x 로부터 어떠한 일의인 값(버켓 번호)을 도출하는 함수를 「해쉬 함수 h(x)」라고 이름 붙입시다.

해쉬 함수 h가 채우지 않으면 안 되는 조건은:

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

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

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

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

 

클래스 템플릿: unordered_set

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

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

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

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

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

 

 

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

namespace std {

namespace tr1 {

// [6.3.4.3] Class template unordered_set

template < class Value,

class Hash = hash,

class Pred = std::equal_to,

class Alloc = std::allocator >

class unordered_set;

}

}

 

unordered_set 의 템플릿 인수는4.

Value : 컨테이너 요소의 형태

Hash : Value 로부터 해시 값을 요구하는 함수 오브젝트

Pred : Va lue 가 동일할 때 true 되는 함수 오브젝트

Alloc : allocater

 

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

 

 헤더: functional 에 정의된 hash

namespace std {

namespace tr1 {

template < class T>

struct hash : public std::unary_function size_t >

{

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

};

 

template <> struct hash< bool >;

template <> struct hash< char >;

template <> struct hash< signed char >;

template <> struct hash< unsigned char >;

template <> struct hash< wchar_t >;

template <> struct hash< short >;

template <> struct hash< unsigned short >;

template <> struct hash< int >;

template <> struct hash< unsigned int >;

template <> struct hash< long >;

template <> struct hash< unsigned long >;

template <> struct hash< float >;

template <> struct hash< double >;

template <> struct hash< long double >;

template<class T> struct hash<T*>;

template <> struct hash<std::string>;

template <> struct hash<std::wstring>;

}

}

 

컨테이너에 대한 요소의 삽입/삭제/검색 및 열거에 관한 인터페이스는 종래의 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백만개 삽입했을 때의 각각의 소요 시간을 계측합니다.

 

set    unordered_set 속도 비교

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

#define NOMINMAX

#include <windows.h>

#include <iostream>

#include <set>

#include <unordered_set>

#include <unordered_map>

#include <random>

 

using namespace std;

 

int main()

{

set< int > s;

tr1::unordered_set< int > us;

const int N = 100000;

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

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

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

 

long t;

const int TIMES = 2000000;

rng.seed(12345);

t = GetTickCount();

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

s.insert(sample());

}

t = GetTickCount() - t;

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

 

rng.seed(12345);

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

t = GetTickCount();

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

us.insert(sample());

}

 

t = GetTickCount() - t;

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

}

}

 

< 실행 결과 >

1562(set)

1188(unordered_set)

 

 

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

 

1563(set)

875(unordered_set)

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

 

 

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

 

 

저작자 표시
신고
by 흥배 2010.03.17 08:30
| 1 |

티스토리 툴바