표준 C++프로그램 라이브러리가 제공하는 컨테이너 set/map(multiset/multimap)는 통상 2진트리(binary-tree)로 설계되어 있습니다. 요소의 대소 관계에 근거해 트리를 관리하여 삽입/삭제/검색에 필요한 시간 계산량을 절약하도록 만들어진 뛰어난 구조입니다.
그럼 좀 더 고속의 컨테이너는 없는 것일까요? 해시표에 의한 컨테이너가 하나의 방법입니다. 해시표의 사이즈와 해쉬 함수를 적절히 선택하면 좀 더 빠르게 접근할 수가 있습니다.
그러나 유감스럽지만 표준 C++ 에는 해시·컨테이너는 받아들여지지 않았습니다. 다행스럽게도 표준은 되지 않기는 했지만, 해시·컨테이너는 몇개의 구현이 이루어지고 있습니다.
그 중에 대표적인 해시·컨테이너들의 구현에 대해, 실제로 그 퍼포먼스 측정을 시도했습니다.
측정 한 해시·컨테이너는 아래의 3종류입니다:
Dinkum Standard Library 2.33 (Dinkumware )
Visual C++에 OEM 제공되고 있는 STL의 제품입니다.
STLport 4.5. 1 (STLport )
SGI판을 베이스로, 각종 OS/컴파일러로 사용할 수 있도록 수정이 더해지고 있습니다.
SourcePro/Core (Rogue Wave )
C++ Builder에 OE공급되고 있는 STL의 제품판입니다.
Windows2000, Visual C++ 6.0의 환경에서 아래의 코드를 multi-thread/DLL로 컴파일 하여 측정했습니다.
함수 bench는 int를 요소의 형태로 하는 컨테이너에[0, N)의 범위의 N개의 요소를 삽입/삭제해, 거기에 필요로 하는 시간 및 요소 1개 당의 시간을 출력합니다.
main에서는 요소수 1000, 2000, 4000, ... 32000의 경우에 대해 해시·컨테이너와 2진트리 컨테이너를 bench에게 주어 각각을 비교하고 있습니다.
Dinkum정도는 아니지만 2진트리보다 늦은 결과가 나왔습니다.
해시는 정말로 빠른 것인지? 왜 이러한 결과가 되어 버렸을까요?
해시·컨테이너는 2진트리에 비해 복잡합니다. 해시값를 요구해 그 값에 대응하는 슬롯에 요소를 삽입합니다. 필요에 따라서 전요소의 재배치를 실시하지 않으면 안 되는 것도 있겠지요. 거기에 비교하면 요소의 비교를 반복하는 2진트리가 빠르다고 하는 결과로 비교에 큰 시간을 필요로 하는 요소에서는 스피드가 역전할지도 모릅니다.
다시 해 봅시다. 이번에는 요소를 길이를 8의 string로 변경합니다:
비교에 필요로 하는 시간이 긴 요소의 경우 2진트리의 처리 속도가 크게 떨어지는 것을 알 수 있겠지요. 해쉬 함수도 int의 경우와 비교하면 해쉬 함수 및 등치 판단이 복잡하게 되었으므로, 그 만큼 늦어지고는 있습니다만, 2진트리정도의 속도는 볼 수 없습니다.
그러나 그런데도 빨라야 할 해시가 2진트리에는 필적하지 않습니다. 해시는 빠르다고 하는 상식을 뒤집는 결과가 되었습니다.
Contents
1. 해시는 정말로 빠른 것인지?
1.1. int
1.1.1. Dinkum
1.1.2. STLport
1.1.3. SourcePro/Core
1.2. string
1.2.1. Dinkum
1.2.2. STLport
1.2.3. SourcePro/Core
1. 해시는 정말로 빠른 것인지?
1.1. int
1.1.1. Dinkum
1.1.2. STLport
1.1.3. SourcePro/Core
1.2. string
1.2.1. Dinkum
1.2.2. STLport
1.2.3. SourcePro/Core
Recent Posts
Archive Posts
Tags