[Effective STL] 23. 이진 탐색 트리 vs 정렬된 vector

항목 23. 연관 컨테이너 대신에 정렬된 vector를 쓰는 것이 좋을 때가 있다

 

 

 

빠른 데이터 검색을 하고 싶다

• 보통은 연관 컨테이너를 생각하게 된다.
• 그 중 해시 컨테이너를 선택하는 것이 좋다.(항목 25 참조)
  • map(로그 시간), hashmap(상수 시간)
• 탐색이 로그 시간 정도가 적당하다고 판단했더라도, 연관 컨테이너보단 벡터가 나을 수 있다.

 

 

 

균형 이진 탐색 트리(balanced binary search tree)

• 데이터 노드의 삽입, 삭제, 탐색이 언제 이루어질지 예측할 수 없는 상황에 적합한 자료구조.
• 어떤 식으로 사용해도 안정적인 성능을 보여준다.
  • 즉, 삽입, 삭제, 탐색의 수행이 일정한 순서를 따르지 않으며, 다음에 어떤 동작이 이루어질 지 예측할 수 없더라도 안정적인 성능을 보장한다.
• 하지만 대부분은 그렇게 혼란스럽게 사용하지 않는다.
• 보통은 아래 세 단계 순서로 사용하게 될 것이다.
  1. 데이터 셋업(setup) : 요소 삽입
  2. 데이터 탐색(lookup) : 요소 탐색
  3. 데이터 재구성(reorganize) : 요소 변경
• 이런 순으로 자료 구조를 사용하는 상황이라면
  • 정렬되었다는 가정 하에, 벡터가 연관 컨테이너보다 나은 수행성능(수행 시간, 메모리 공간 모두)을 제공할 가능성이 높다.
  • 정렬되어 있어야 탐색 알고리즘(binary_search, lower_bound, equal_range  등)을 제대로 적용할 수 있다.(항목 34 참조)

 

 

 

벡터가 이진 탐색보다 나은 이유
1. 메모리 크기

• 이진 탐색 트리의 각 노드는 기본적으로 아래를 포함하게 된다.
  • 노드 왼쪽 자식, 오른쪽 자식 노드의 포인터
  • 대개 부모 노드에 대한 포인터까지
  • 즉, 요소별 최소 세 개의 포인터를 담는 메모리가 오버헤드로 걸린다.
• 벡터 역시 메모리 오버헤드는 있다.
  • 메모리의 여유 분이 예약되기 때문이다.(항목 14 참조)
  • 하지만 보통 세 개의 포인터 혹은 두 개의 포인터와 int 하나 정도 분일 뿐이다.
  • 더군다나 swap trick으로 잘라낼 수도 있다.(항목 17 참조)
  • 탐색시 그 부분을 건드리지도 않으므로 수행 성능에 영향도 없다.

 

 

 

벡터가 이진 탐색보다 나은 이유
2. 메모리 참조 위치의 근접성(locality of reference)

• 만약 데이터 크기가 무지하게 크다고 가정해보면, 요소들은 여러 메모리 페이지에 걸쳐서 저장될 것이다.
• 페이지 사용량을 볼 때, 벡터가 이진 탐색 트리보다 훨씬 적은 양을 소비한다.
  • 벡터는 요소 하나에 별도의 오버헤드가 걸리지 않으므로 당연한 이야기이다.
• 예컨대, 요소의 메모리 크기가 12 바이트, 작업하는 시스템의 포인터의 크기가 4 바이트, 메모리 페이지 하나의 크기가 4096(4K)라고 가정해보자.
  • 컨테이너 자체의 오버헤드를 무시하고 계산할 때,
  • vector의 경우 한 페이지에 341개의 요소가 들어간다.
  • 연관 컨테이너(이진 탐색 트리)의 경우 170개 가량이 들어간다.
  • 약 두 배의 차이가 난다!
• 사용 메모리가 많아지만 페이지 오류(page fault)도 그만큼 많아지며, 그만큼 속도에서 손해를 보게 된다.
• 벡터처럼 연속 메모리 구조를 취하지 않는 노드 기반 컨테이너는, 이동 경로가 가까운 노드 사이라도 반드시 물리 메모리 위치도 가까울 거리는 보장을 할 수 없다.
  • 이진 탐색 시의 페이지 오류를 최소화하려면 가까운 도드들은 인접한 물리 메모리에 저장하도록 구조를 만드는 것이 정석이다.

 

 

 

벡터의 단점

• 늘 정렬된 상태로 있어야 한다.
• 요소가 삽입, 삭제될 때마다 위치 뒷쪽 요소는 모두 한 칸씩 움직여야 한다.
• 여유 메모리가 없다면 재할당까지 발생한다.(항목 14 참조)
• 하지만, 삽입, 삭제 동작과 탐색 동작이 거의 섞이지 않는 경우에는 정렬된 벡터가 훨씬 낫다.

 

 

 

set 대신 vector 사용하기

vector<Widget> vw; // set<Widget> 대신 쓰인 벡터

... // 데이터 셋업

sort(vw.begin(), vw.end());

Widget w;
{
    ... // 객체 탐색 시작

    // binary_search로 탐색
    if(binary_search(vw.begin(), vw.end(), w)) ...

    // lower_bound로 탐색
    vector<Widget>::iterator i =lower_bound(vw.begin(), vw.end(), w);
    if(i != vw.end() && !(*i < w)) ...

    // equal_range로 탐색
    // range의 타입은 pair<vector<Widget>::iterator, vector<Widget>::iterator>
    auto range = equal_range(vw.begin(), vw.end(), w);
    if(range.first != range.second) ...

    ... // 객체 탐색 끝
}

sort(vw.begin(), vw.end()); // 데이터 재구성

• 각 탐색 알고리즘(binary_search, lower_bound 등)은... (항목 45 참조)

 

 

 

map 대신 vector 사용하기

• 만약 vector로 map을 대체하려고 한다면?
• 벡터에는 pair<K, V> 를 넣어야 한다.
• map<K, V>는 사실 pair<const K, V>가 저장되지만...
• 하지만 벡터는 정렬할 때 각 요소의 값이 대입(assignment) 연산을 통해 이동하므로 const를 제거해야 한다.
  • 즉, 두 데이터는 '수정 가능'해야 한다.
• 벡터 정렬 시, pair의 기본 버전 operator<는 K, V를 모두 고려하므로
  • K, V 중 V만 비교하도록 비교 함수를 커스텀해야 한다.
• 또한 정렬용 비교 함수 외에 탐색(lookup)용 비교 함수를 따로 두어야 한다.
  • 정렬에 사용하는 비교함수는 두 개의 pair를 매개 변수로 받지만,
  • 탐색은 키 값만 가지고 이루어지기 때문이다.
  • 즉, 탐색용 비교 함수는 키 타입의 객체와 페어 객체를 매개변수로 받는 형태가 되어야 한다.
  • 근데 첫 매개변수가 키 타입인지 페어 타입인지 미리 알 수 없으므로 양쪽 경우를 모두 고려하여 함수를 만들어야 한다..

using Data = pair<string, int>;

class DataCompare
{
public:
    // 정렬용 비교 함수
    bool operator()(const Data& lhs, const Data& rhs) const
    {
        return keyLess(lhs.first, rhs.first);
    }
    
    // 탐색용 비교 함수 1
	bool operator()(const Data& lhs, const Data::first_type& k) const
    {
        return keyLess(lhs.first, k);
    }
    
    // 탐색용 비교 함수 2
	bool operator()(const Data::first_type& k, const Data& rhs) const
    {
        return keyLess(k, rhs.first);
    }
    
private:
    bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const
    {
        return k1 < k2;
    }
};

vector<Data> vd; // map<string, int> 대신 쓰인 벡터

... // 데이터 셋업

sort(vd.begin(), vd.end(), DataCompare());

string s;
{
    ... // 객체 탐색 시작

    // binary_search로 탐색
    if(binary_search(vd.begin(), vd.end(), s, DataCompare())) ...

    // lower_bound로 탐색
    vector<Data>::iterator i =lower_bound(vd.begin(), vd.end(), s, DataCompare());
    if(i != vd.end() && !(*i->first < s)) ...

    // equal_range로 탐색
    // range의 타입은 pair<vector<Data>::iterator, vector<Data>::iterator>
    auto range = equal_range(vd.begin(), vd.end(), s, DataCompare());
    if(range.first != range.second) ...

    ... // 객체 탐색 끝
}

sort(vd.begin(), vd.end(), DataCompare()); // 데이터 재구성