글
"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가 채우지 않으면 안 되는 조건은:
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에 대해서 그 개요를 설명합니다.
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
RECENT COMMENT