어찌됐듯 STL의 대표적인 컨테이너인 벡터(vector)에 대한 성능에 대해 논하고자 한다.
다들 알다시피 벡터는 동적배열의 추상화된 자료구조이다.
벡터는 메모리 공간에서 선형적으로 존재하며, 상수 시간에 가장 끝에 데이타를 삽입할수있고, O(1) 상수시간에 접근이 가능하다. 반면 가장 앞에 삽입이 거의(?) 불가능하고(가능더라도 O(N)이므로 왠만하면 deque를 사용하자) 중간에 데이타를 삽입,삭제할경우 그 뒤에 있는 녀석들(O(N))이 모두 이동되어야 한다.
자 이정도로 기억을 되살리고...
std::vector _vector;
for(int i...)
_vector.push_back(i);
우리는 위 코드에서 상수시간안에 데이타를 모두 삽입해 줄것이라는 실수를 하곤한다.
그러나 _vector.reserve()를 적절히 사용했을 경우만 해당된다.
알다시피 상수시간만에 가장끝 원소를 찾아갈수는 있지만 삽입을 위해서는 필연적인 메모리 공간이 요구되기 때문에 당연히 미리 할당이 되어있어야 한다.
그러나 기본생성자로 생성한 _vector는 과연 어느정도의 메모리 공간을 할당하는가?
VS2005에 포함된 STL 라이브러리의 경우 기본생성자가 할당해주는 공간은 0 바이트이다.
이말의 뜻은 매번 push_back() 호출시마다 메모리가 할당되는것인가?
특이하게도 위 테스트에서 6개의 원소를 삽입하는동안 매번 메모리가 할당되었다.
그러나 7개째를 삽입하게 되면 메모리 할당전략이 본색을 드러낸다. - 필요할 때마다 50% 씩 추가할당하는 모습을 지켜 볼수있다.
결국 대량의 데이타 삽입이 필요할 경우에는 _vector.reserve()를 꼭 사용해 불필요한 메모리 할당 오버헤드를 줄어야 한다는 것이다.
.NET , Java와 같이 동적배열을 지원하는 프레임웍의 경우도 별반다르지 않다.
그 이유는 Java의 Vector를 예로든 왼쪽의 도표에 나온 성능처럼, Vector 에 후위 삽입하는 경우 상수(O(1))에 근접한 성능을 보여주지만, 전위삽입의 경우 엄청난 성능하락(O(N*N))을 보여주고 있기 때문이다.
결국 표현하고자 하는 데이타가 어떤 컨테이너(벡터, 덱, 리스트,...)에 적합한지 충분히 고려해서 결정하는것이 필요하다는 것이다.
또다른 예를 들어보자.
집앞 운동장에 사는 개미들의 숫자 통계를 분석하라는 사장님의 지시(?)가 있었다. 백만*백만개의 좌표로 표현하도록 하라는 당부(!)와 함께 말이다.
몇일 생각해 보니 직교좌표계를 사용하면 알맞을것 같다. 해당 좌표계를 표시하는데 어떤 자료구조를 사용하겠는가? 간단히 생각해 보면 BYTE[백만][백만] 의 2차원배열로 처리하면 손쉬울것 같다.
백만은 약 2^20(1M) 이므로 2^40 = 약 1TBytes 메모리가 필요할 것이다.
이건 아니다. 뭔가 다른 방법이 필요해 보인다.
운동장을 아무리 살펴보아도 개미는 별로 없다. 결국 필요없는 공간이 많다는 것이다. 이런 공간을 표시하기 위해 비싼 메모리를 구매해 달라는 청구서를 쓸수도 없는 노릇이다.
결국 2차원의 배열구조가 아닌 다른방법이 필요한것이다. 결국 성능을 위해서 뿐만 아니라 밥줄을 위해서도 배열이 아닌 다른 자료구조가 필요한 셈이다.
당신이라면 어떤 선택을 하겠는가?
댓글 없음:
댓글 쓰기