소개

표준 템플릿 라이브러리(STL)에서는 다양한 종류의 C++ 컨네이너 클래스와 알고리즘이 제공된다.

이들을 서로 적절히 조합하여 사용하면, 여러 방면에 걸쳐 유용한 기능들을 수행해 낼 수 있도록 설계되어 있다.

비록 제공되는 컨테이너 클래스의 개수가 그다지 많은 편은 아니지만, 벡터, 리스트, 셋, 맵 등과 같이 자주 사용되는 컨테이너들은 거의 대부분 포함되어 있다.

템플렛 알고리즘 컴포넌트에는 가장 흔한 데이터 조작에 해당되는 검색, 정렬, 머지 등을 위한 알고리즘들이 다양하게 포함되어 있다.

 

STL이 다른 C++ 컴테이너 클래스 라이브러리와 구분되는 가장 큰 차이점은 바로 STL 알고리즘은 모두 제네릭하다는 것이다.

즉, STL의 알고리즘은 내장 타입과 다양한 컨테이너 상에서 모두 수행이 가능하며, 심지어 모든 종류의 컨테이너에서 수행이 가능한 알고리즘들도 많다.

 

STL에서 채택한 가장 중요한 개념 중 하나는 알고리즘을 정의할 때, C/C++의 포인터를 일반화 시킨 반복자(iterator)를 사용했다는 점과, 반복자를 여러 종류로 정의해 둠으로써 다양한 종류의 컨테이너들을 순환할 수 있도록 했다는 점이다.

STL은 컨테이너, 제네릭 알고리즘, 반복자 이외에 함수 객체(function object)라는 것을 제공하는데, 이는 C/C++ 함수를 일반화시킨 것으로, STL의 다른 컴포넌트들(컨테이너, 제네릭 알고리즘, 반복자)을 각자의 쓰임새에 따라 효과적으로 변형시킬 수 있도록 도와준다.

뿐만 아니라, STL 라이브러리는 컨테이너와 반복자, 그리고 함수 객체의 인터페이스를 변경할 때 사용되는 다양한 종류의 어댑터(adaptor)도 제공한다.

그리고 STL에서는 할당기(allocator)라는 별도의 컴포넌트를 통해서 컨테이너의 메모리 관리를 제어하고 있다.

 

제네릭 프로그래밍의 개념과 중요성

STL은 지난 수년 간의 제네릭 프로그래밍 연구를 통해 얻은 산물이다.

이 연구의 목적은 제네릭한, 즉, 재사용이 가능한 소프트웨어 컴포넌트를 개발하고 구성하는 방법을 탐구하는 것이었다.

여기서 "재사용 가능하다."라는 것은 간단히 말해서, "광범위하게 이곳 저곳에 두루 전용될 수 있으며, 그러한 와중에도 효율(성능)은 떨어지지 않는다."는 것을 의미한다.

이때, 전용은 문서 편집과 같은 수작업을 통해서가 아니라, 전처리기나 프로그래밍 언어 자체의 메커니즘을 통해 이루어진다.

그 동안 소프트웨어 재사용에 관한 많은 연구가 있었지만, 오늘날의 STL을 있게 한 제네릭 프로그래밍에 관한 연구는 이들과는 뚜렷한 차이가 난다.

이러한 차이점을 만드는 STL의 특징에는 두 가지가 있는데, 바로 STL 컴포넌트가 지니고 있는 높은 수준의 전용성(adaptability)과 효율성(efficiency)을 들 수 있다.

 

 

STL의 성능 보증에 관한 이해

STL의 모든 컴포넌트의 인터페이스 요구 조건에는 성능 보증(performance guarantee)이 포함되어 있는데, 이러한 것을 봐도 STL은 기존의 다른 소프트웨어 라이브러리들에 비해 좀 특별한 라이브러리이다.

이러한 성능 보장은 여러 컴포넌트들 중에서 어떤 컴포넌트를 사용할지를 결정할 때 매우 중요한 기준이 된다.

컴포넌트의 성능을 언급할 때는 빅-오(big-Oh) 표기법을 사용한다.

빅-오 표기법과 관련정의

대부분의 경우, 알고리즘의 계산 소요 시간에 관해 언급할 때는 알고리즘의 모든 입력을 몇 가지 단순한 인자들로 처리하면 문제가 간단해진다.

컨테이너 상에서 작동하는 알고리즘의 경우에는 대개 컨테이너 사이즈 N을 인자로 선택하는 것이 보통이다.

사이즈가 N인 입력에 대해서, 알고리즘의 최대 소요 시간(maximum time), T(N)을 생각해 보자.

 

T(N)은 사이즈가 N인 입력에 대한 최악 소요 시간(worst-case time)이라고도 불린다.

 

문제를 좀 더 단순화하기 위해서는 T(N)의 공식을 정확하게 작성하려 하지 말고, N의 변화에 따라 T(N)이 어떻게 변화하는지에 주목하여 T(N)의 상계(upper bound)를 나타내는 간단한 함수를 찾아보도록 하자.

예를 들어, 어떤 상수 c와 충분히 큰 모든 N에 대해서, 다음을 만족하는 함수를 찾아냈다고 하자.

T(N) ≤ cN

위와 같은 경우에는 "알고리즘에 소요되는 시간이 입력의 사이즈가 커짐에 따라 최악의 경우에는 선형적으로 증가한다."는 것을 의미한다.

여기서, 상수 c는 알고리즘이 다른 컴퓨터에서 컴파일하여 실행할 때마다 달라지기 때문에, 이를 보다 더 단순화하기 위해서 알고리즘 소요 시간의 경계를 표현할 때는 상수를 숨겨서 표현한다.

 

이 때 사용하는 것이 빅-오 표기법(big Oh notation)인데, 예를 들어 앞에서의 관계식은 다음과 같이 작성할 수 있다.

T(N) ≤ O(N)

 

일반적으로 어떤 상수 c와 충분히 큰 모든 N에 대해서, 다음과 같은 관계식을 만족시키는 함수가 있을 때,

T(N) ≤ cf(N)

이는 다음과 같이 표현할 수 있다.

T(N) = O(f(N))

 

- T(N) = O(N) 이것은 위에서 방금 언급했던 경우에 해당한다. 이 경우에는 해당 알고리즘이 "선형 시간 바운드(linear time bound)를 가진다."라고 하거나, "선형 시간(linear time)이다." 또는 그냥 "선형적(linear)이다."라고 한다.   - T(N) = O(N²) 이 경우에는 해당 알고리즘이 "이차 곡선 시간 바운드(quadratic time)를 가진다."라고 하거나, "이차 곡선 시간(quadratic time)이다." 또는 그냥 "이차 곡선(quadratic)이다."라고 한다.   - T(N) = O(log N) 이 경우에는 해당 알고리즘이 "로그 시간 바운드(logarithimic time bound)를 가진다."라고 하거나, "로그 시간(logarithmic time)이다." 또는 그냥 "로그적(logarithmic)이다."라고 한다.   - T(N) = O(N log N) 이 경우에는 해당 알고리즘이 "N log N 시간 바운드(N log N time bound)를 가진다."라고 한다.   - T(N) = O 이 경우에 해당하는 알고리즘은 "O(1) 시간 바운드 (O(1) time bound)" 또는 "상수 시간 바운드(constant time bound)를 가진다."라고 한다. 이 경우의 빅-오 표기법은 어떤 상수 c와 충분히 큰 모든 N에 대한 T(N) ≤ c 함수에 해당하는 것이다.

여기서 반드시 명심해야 할 것은 위 각각의 경우에서 컴퓨팅 시간을 최악 소요 시간(worst-cast computing time)의 상계로 표현하고 있다는 점이다.

이것은 예를 들어 시퀀스를 정렬하는 퀵소트 알고리즘의 경우와 같이 최악조건에 해당하는 상황이 매우 드물게 발생하는 경우에는 오해의 소지가 있을 수 있다.

퀵소트(quicksort) 알고리즘의 최악 소요 시간은 이차원적인데, 이는 힙소트(heapsort)나 머지소트(mergesort)와 같은 다른 정렬 알고리즘에 비해 매우 느린 것이다.

하지만 퀵소트 알고리즘이 다른 알고리즘 보다 평균적으로 더 빠르기 때문에 대부분의 경우에는 퀵소트 알고리즘을 사용하는 것이 가장 좋은 선택이다.

이러한 경우에는 컴퓨팅 시간에 관해 설명할 때, 최악 소요 시간을 빅-오 표기법으로 간단히 표시한 경계 뿐만 아니라, 평균 소요 시간(average time)에 관해서도 언급해야 한다.

사이즈 N인 입력을 가지는 알고리즘에 대한 평균 소요 시간은 일반적으로, 사이즈가 N인 모든 입력이 동일한 호가률로 발생한다는 가정하에 계산되는 것이다.

그러나 어떤 상황에서는 다른 확률 분포(probability distribution)를 적용하는 것이 더 적절한 경우도 있다.

 

 

아모타이즈드 시간 복잡도

어떤 경우에는 알고리즘의 컴퓨팅 시간을 가장 현실적으로 규명해낼 수 있는 것이 최악 소요시간도 아니고, 평균 소요 시간도 아닌 아모타이즈드 시간(amortized time)인 경우가 있다.

이 개념은 부채 상환(amortization)이라고 하는 제조업계의 회계 방식과 유사한 것으로, 부채 상환에서는 일괄(one-time) 비용(설계 비용을 예로 들 수 있다)이 생산된 부품의 수로 나눠져서 각각의 유닛에 할당된다.

일련의 연산을 수행할 때 소요시간이 큰 폭으로 변화하고, N개 연산을 수행하는데 걸리는 총 소요 시간이 최악 소요 시간의 N배보다 더 나은 바운드를 가지는 경우에는 아모타이즈드 시간을 이용하여 컨테이너 상의 연산이 소비한 시간을 설명하는 것이 아주 유용하다.

예를 들어, STL 벡터의 맨 뒤에 원소를 삽입하는데 필요한 최악 소요 시간은 컨테이너의 사이즈를 N이라고 했을 때 O(N)이 된다.

삽입 연산에 필요한 메모리 공간이 없는 경우에는 새로 메모리 공간을 할당하고, 그 다음에 원소들을 새로 할당된 메모리 공간으로 모두 옮겨야 하기 때문이다.

그러나 길이 N의 벡터는 확장될 필요가 있을 때마다 2N의 메모리 공간을 할당하여, 이후 N-1번의 삽입 동안에는 재할당과 복사가 발생하지 않게 된다.

결과적으로, 이후에 발생할 N-1번의 삽입은 개별적으로는 상수시간(constant time)에 수행되므로, N개의 삽입 연산에 걸리는 총 시간은 O(N)이며, N개의 연산의 평균을 계산하면 삽입 연산의 소요 시간은 O(1) 시간이 되는 것이다.

 

따라서, 삽입 연산의 아모타이즈드 시간은 상수 즉, 삽입 연산의 소요 시간이 "아모타이즈드 상수(amortized constant)이다."라고 말 할 수 있는 것이다.

이 예에서는 삽입에 대한 아모타이즈드 상수 시간 바운드가 최악 조건에 대한 선형 시간 바운드보다 훨씬 더 정확하게 실제 비용을 반영하고 있다.

일반적으로, 어떤 연산에 대한 아모타이즈드 시간은 N개 연산의 시퀀스에 걸리는 총 소요 시간을 N으로 나눈 것에 해당한다.

비록 아모타이즈드 시간이 평균 값이기는 하지만 평균 소요 시간의 경우와는 달리,확률의 개념이 개입되어 있지 않다.

 

빅-오 표기법의 한계점

빅-오 표기법의 한계점은 이미 잘 알려져 있다.

빅-오 표기법은 단순히 소요 시간의 상계를 표시한 것이기 때문에, O(N) 알고리즘의 소요 시간은 선형적 증가 속도보다 더 느린 속도로 증가할 수 있으며, 또한 빅-오 표기법은 큰 N에 대해서만 성립하기 때문에, N값이 작은 경우에는 선형적 증가보다 빠른 속도로 증가할 수 있다.

서로 다른 두 개의 O(N) 알고리즘이 컴퓨팅 시간에서는 현격한 차이를 보일 수도 있다.

어느 한 알고리즘이 다른 알고리즘에 비해 2배 또는 10배 또는 100배 빠를 수도 있지만, 빅-오 표기법을 사용하면 그러한 차이점들은 모두 숨겨지게 된다.

예를 들어, 알고리즘 1과 알고리즘 2가 모두 O(log N)이고, 알고리즘 2의  상수값 c가 알고리즘 1의 두배라면, 특정 값 N에 대해서 알고리즘 2의 수행 시간은 알고리즘 1을 N²에 대해서 수행했을 때의 소요시간과 동일한 것이다.(log N² = 2 log N).

 

특정 컴파일러에서 다른 컴파일러로 또는 특정 하드웨어 아키텍처에서 다른 아키텍처로 옮겨갈 때는 빅-오 표기법에서는 나타나지 않는 상수 값이 변화될 수 있으며, 만약 이 상수 값의 변화량이 충분히 커서 다른 알고리즘을 선택하지 않고, 특정 알고리즘을 선택했던 경우와 상황을 뒤집어 놓을 수도 있다.

 

따라서, 이런 저런 이유를 모두 고려한다면, 프로그램 성능 테스트는 되도록이면 해당 프로그램이 실제로 수행되는 환경과 유사한 환경 하에서 실시하는 것이 바람직하다.

 

 

- STL 튜토리얼·레퍼런스 가이드 제2판 中 -