개요
vector는 요소들을 메모리상 연속적으로 저장하고,
필요할 때 자동으로 메모리를 늘려주는 컨테이너
동적 할당 배열
vector는 기본적으로 동적 할당 배열의 형태를 가진다. 따라서 배열 특유의 인덱스 기반 접근 $O(1)$이 가능하며, 동적 할당이므로 런타임에서 사이즈를 유동적으로 할당할 수 있다. 하지만, 배열의 고질적인 문제 역시 똑같이 가져 자료의 검색은 빠르지만 삭제와 삽입에 있어서 느린 편 $O(n)$이다.
그럼 기존의 동적 배열과 Vector의 차이는 뭐지?
동적 배열과 vector의 차이점을 이야기하기 위해서는 동적 배열의 재할당시 문제점에 대해서 이야기할 필요가 있다.
동적 배열의 경우 기존의 할당된 크기를 넘어선 요소의 추가 시 새로운 크기의 동적 배열을 할당하고 값들을 복사 $O(n)$해야 한다. 재할당 과정이 빈번하게 반복되면 복사가 자주 일어나므로 일련의 과정 후 사이즈가 n일 때 시간 복잡도가 $O(n^2)$에 가깝게 늘어난다.
그럼 처음 할당할 때나 추가 할당 시 메모리를 넉넉하게 주면 되지 않나?
물론 메모리를 넉넉하게 주는 방법이면 시간 복잡도를 $O(n)$에 가깝게 유지 가능하다. 하지만 메모리를 먼저 할당하는 것은 좋지만 그 할당할 메모리가 어느 정도인지 아는 것은 다른 문제이다. 가장 베스트인 상황은 필요한 최대 배열의 크기를 사전에 알아서 딱 그만큼만 할당하는 것이다. 하지만 현실 상황에서 필요한 배열의 최대 크기를 항상 안다는 것은 불가능한 일이다.
Vector의 등장 배경
그럼 필요한 최대 배열의 크기를 몰라도 $O(n)$의 시간복잡도를 유지하면서
메모리 사용은 최소화시킬 수 있는 방법은 없을까?
이러한 상황에서 나온 게 바로 vector라는 컨테이너이다. vector는 geometric growth라는 특유의 재할당 방식을 통해 재할당의 시간 복잡도를 $O(n)$으로 유지한다. 마지막 질문을 염두에 둔 체 작동방식으로 넘어가자.
작동 방식
geometric growth
우선 Size와 Capacity의 개념을 정리하겠다. Vector에서 Size는 실제 값이 있는 유효한 element의 수를 의미한다. Capacity는 실제 element가 존재하지는 않지만 현재 할당가능한 용량을 의미한다. 예를 들어, Vector내에 element를 추가한다고 하면 Capacity를 넘지 않는 한 단순히 Size를 하나 늘리고 맨뒤에 element를 추가하면 되지만 Capacity를 넘는 범위에 element를 할당하는 경우는 배열 자체의 Capacity를 늘려서 재할당하는 과정이 필요하다.
Vector의 작동 방식은 간단하다. 요소를 추가할 때 배열의 크기가 부족하면 Linear 하게 특정 고정된 수치만큼 Capacity을 늘리는 게 아니라 기존 Capacity의 특정 배수(주로 1.5~2.0)로 Capacity의 크기를 늘리는 방식이다. 이러한 Vector의 Capacity을 늘리는 방법을 geometric growth라 부르고 그 특정 배수를 growth factor라고 부른다. $($실제 stl vector 라이브러리상 명칭법이다.$)$ 아래는 growth factor를 2로 두고 element를 순차적으로 추가하는 예시이다.
이러한 Capacity 증가 방식으로 초기 Capacity의 크기를 작게 시작하여 요소를 추가하며 천천히 Capacity을 증가하더라도 Vector의 최대 크기 n에 대해서 $O(n)$의 시간복잡도를 만족한다. 또한, 최대 메모리 역시 최대 크기 n의 특정 배수만큼만 가지므로 $O(n)$의 공간 복잡도를 만족한다.
아니 근데 특정 수치만큼 용량을 증가시키는 게 아니라
기존 용량의 비율만큼 증가하는 게 시간복잡도를 $O(n)$으로 만드는 거랑 무슨 상관이냐?
당연한 의문이다. 왜 geometric growth 방식이 $O(n)$의 복잡도를 보장하는지 그걸 바로 아래에서 증명해 보도록 하겠다.
증명
초기 벡터사이즈 1에서 요소를 하나씩 추가하여 최종적으로 $n=2^k$에 도달한다고 생각해 보자. 이때, growth factor는 2이다. n에 도달할 때까지 새로 할당되는 메모리의 크기는 다음과 같다. 간단한 등비수열의 합을 계산하면 2n-1로 $O(n)$의 시간복잡도를 가지는 것을 확인가능하다.
총 메모리 할당 크기$=2^0+2^1+ \dots + 2^k$
$=\sum_{i=0}^k 2^i$
$=2^{k+1}-1=2*n-1$
그럼 이번에는 growth factor를 일반화하여 $R(R>1)$로 두자, n 역시 $n=R^k$라고 생각해 보겠다. 이 역시 결국, $O(n)$의 시간복잡도를 가지는 것을 확인가능하다.
총 메모리 할당 크기$=R^0+R^1+ \dots + R^k$
$=\sum_{i=0}^k R^i$
$=\frac {R^{k+1}-1}{R-1}=\frac {R}{R-1} x-\frac {1}{R-1}$
마지막으로 정리하면 R이 커질수록 시간복잡도는 개선되고 $(\because O(f(n)) \propto \frac {R}{R-1})$ 할당되는 메모리는 R에 비례하므로 공간 복잡도는 나빠진다. R이 작아질 경우 반대를 만족한다.
최종적으로 시간과 공간 복잡도 모두 growth factor R에 대해서 $O(n)$ 을 만족한다.
다시 말해 필요한 최대 배열의 크기를 몰라도 시간과 공간 복잡도 모두 안정적으로 가져갈 수 있는 것이다. 염두에 두라던 질문의 답이 바로 이것이다.
구현
메서드
구현한 주요 메소드이다. 기본적으로 stl vector의 기능을 그대로 따라 구현했으므로 자세한 설명은 생략하겠다.
| Member Variable | |
| size | vector내 유효한 element의 개수이다. |
| capacity | vector내 현재 할당 가능한 element의 개수이다.(할당된 거 포함) |
| data | 실제 할당되는 동적 배열의 포인터이다. |
| size/capacity manipulation | |
| resize | size를 원하는 수치로 재조정하고 필요시 capacity도 늘려준다. |
| clear | size를 0으로 둔다. |
| reserve | 최소 보장 capacity를 확보한다. |
| shrink_to_fit | size에 맞춰서 capacity를 줄인다. |
| element access | |
| push_back | 배열 마지막에 element를 할당한다. |
| pop_back | 배열 마지막에 element를 제거한다. |
| insert | 특정 위치에 element를 삽입한다. |
| erase | 특정 위치의 element를 삭제한다. |
코드
#include<cstring>
#include<iostream>
template<typename T>
class MyVector{
public:
MyVector(){
_size=0;
_capacity=10;
_data=new T[_capacity];
}
MyVector(int N, const T& val=T()){
_size=N;
_capacity=N;
_data=new T[N];
for (int i = 0; i < _size; i++) _data[i]=val;
}
~MyVector(){
delete[] _data;
}
//member access
int size(){return _size;}
int capacity(){return _capacity;}
T* data(){return _data;}
//capacity modification
void resize(int newsize){
if (_capacity< newsize){reserve(newsize);}
for (int i = _size; i < newsize; i++) _data[i]=T();
_size= newsize;
}
void resize(int newsize, const T& val){
if (_capacity< newsize){reserve(newsize);}
for (int i = _size; i < newsize; i++) _data[i]=val;
_size= newsize;
}
void clear(){_size=0;}
bool empty(){return (_size==0);}
void reserve(int newcapacity){
if (_capacity < newcapacity) {
T* newData = new T[newcapacity];
//memcpy(newData, _data, sizeof(T) * _size);
for (int i = 0; i < _size; ++i) newData[i] = _data[i];
delete[] _data;
_data = newData;
_capacity = newcapacity;
}
}
void shrink_to_fit(){
if (_capacity>_size){
T* _containerPtr=new T[_size];
memcpy(_containerPtr,_data, sizeof(T)*_size);
delete[] _data;
_data=_containerPtr;
_capacity=_size;
}
}
static void set_growth_factor(double growth_factor) {
_growthFactor = growth_factor;
}
//element manipulation
void insert(int pos, const T& val){
if (pos>=_size) return;
if (_size>=_capacity){reserve(_capacity*2);}
for (int i = _size; i > pos; i--){_data[i]=_data[i-1];}
_data[pos]=val;
_size++;
}
void erase(int pos){
if (pos<0 || pos>=_size) return;
for (int i = pos; i < _size-1; i++){_data[i]=_data[i+1];}
_size--;
}
void pop_back(){
if (!empty()){_size--;}
}
void push_back(const T& val){
if (_size >= _capacity) { reserve(ceil(_capacity * _growthFactor)); }
_data[_size++]=val;
}
void linear_push_back(const T& val){
if (_size>=_capacity){reserve(_capacity+10);}
_data[_size++]=val;
}
//element access
T& operator[] (int ind){
return _data[ind];
}
T& front (){
return _data[0];
}
T& back (){
return _data[_size-1];
}
//utility
void print(bool printElements=true){
std::cout << "Size : " << _size << " / Capacity : " << _capacity << "\n";
if (printElements){
std::cout << "elements : ";
for (size_t i = 0; i < _size; i++) std::cout << _data[i] << " ";
std::cout << "\n";
}
}
private:
int _size;
int _capacity;
static double _growthFactor;
T *_data;
};
template<typename T>
double MyVector<T>::_growthFactor = 2;
실험
실험 환경
시간 측정은 Google Benchmark 방식을 따라 10번의 실행 후 시간의 평균이 아닌 최솟값을 취하는 방식을 사용하였다. 최솟값을 사용한 이유는 평균의 경우 충분한 횟수를 시행해도 잡음 등으로 인해 왜곡된 결괏값을 가지게 되고 최솟값은 잡음이 제거된 “최상의 실행 조건”에서의 성능이라 볼 수 있기 때문에 이를 사용하게 되었다.
$($실제로도 두 방식 모두 그래프 찍어내니 최솟값이 훨씬 깔끔하다. 깔끔한 정도가 아니라 평균의 경우 제대로 된 분석이 불가능한 수준으로 나왔다.$)$
시간 측정은 1부터 N까지 element를 N번 추가하는 함수의 시간을 측정하였으며 라이브러리는 chrono를 사용했다. N은 간격을 1000으로 하여 100000까지 100번의 경우를 측정하였으며 측정한 시간을 로깅하여 엑셀을 통해 시각화하였다.
element 추가 방식은 Geometric Growth로 Growth Factor를 1.5, 2, 3으로 둔 Exp 케이스와 Linear Growth로 고정된 100의 수치만큼 Capacity를 증가시키는 Linear 케이스와 사전에 Capacity를 n으로 미리 reserve 하는 ReserveFirst 케이스 총 3가지를 비교하였다.
추가적으로 실제 vector 라이브러리를 통한 결과역시 커스텀 vector와의 비교를 위해서 추가하였다.
시간 복잡도
첫 번째 그래프는 앞서 말한 각 케이스별 소요시간을 입력크기에 대하여 꺾은선그래프로 표현한 것이다.
그래프상에서 Linear 한 케이스와 exp 한 케이스와 꽤 차이가 커 log 스케일을 사용하였다. 마지막에는 대략 1000배쯤 차이가 난다. 원래 이론적 시간복잡도인 차이인 n(100000)만큼 차이가 나는 것은 아니지만$(\because O(n^2)=n*O(n))$ 그렇더라도 굉장히 큰 수치가 차이가 난다. 이걸 통해 geometric growth가 방식이 단순한 Linear 방식과 비교했을 때 굉장히 빨리 작동한다는 것을 알 수 있다.
또 주목할 만한 것은 reservefirst의 속도이다. 해당 케이스는 사전에 최대 배열의 크기를 알았을 때의 사용가능한 케이스라 보면 된다. Exp 케이스와 비교했을 때 3배 정도 빠른데, 두 방식 모두 시간복잡도는 $O(n)$으로 동일하지만 실제적으로는 꽤 큰 차이가 난다는 것을 알 수 있다. 우리가 vector를 쓰는 이유는 최대 배열의 크기가 모호해서라는 사실을 잊으면 안 된다. 아무리 시간 복잡도가 동일하더라도 미리 배열을 크게 할당하는 방식이 훨씬 빠르게 작동한다.
뭐 결국 말하고 싶은 것은 무지성으로 vector를 쓰지 말고
최대 배열의 크기를 알면 이를 미리 reserve 하는 게 훨씬 효율적이라는 것이다.
Linear 케이스 때문에 1번째 그래프는 부득이하게 log 스케일로 나타냈지만 이번에는 Linear 케이스를 제거하여 그래프의 개형을 더 자세히 볼 수 있다. 기본적으로 reservefirst는 가장 빠르고 growth factor에 비례해서 소요시간이 감소하는 것을 그래프에서는 확인 가능하다,
한 가지 특이한 점은 단순 선형이 아니라 가우스 함수처럼 급격하게 복잡도가 증가하는 지점이 있다는 것이다. 이 급상승 지점들은 vector가 새롭게 reserve를 하는 시점이다. 반대로, 급상승 지점이 아닌 두 지점 사이의 직선은 단순히 reserve 없이 element를 할당만 하는데 드는 시간으로 보면 된다.
실제 라이브러리와 비교했을 때는 꽤나 큰 차이를 보이는데 이는 메모리에 정확히 복사에서 발생하는 문제인제 아니면 메모리 자체에서 발생하는 문제인지 정확히 모르겠다. 일단은 대체적인 경향성만 봐주면된다.
3번째 그래프는 2번째 그래프를 단순히 직선으로 근사 한 것이다. 뭐 이론적 시간 복잡도는 N앞의 계수가 근사한 직선의 기울기가 되어야 하는 게 맞다. 아쉽게도 실제 구현한 그래프의 성능이 라이브러리에 비해 떨어지는 관계로 실제 라이브러의 근사 직선과 비교하자면 기울기 차이가 1.5배로 증명의 유도식을 따라가는것을 확인가능하다.
reserve first : N
growth factor 3 : 1.5N - 0.5
growth factor 2 : 2N - 1
growth factor 1.5 : 3N - 2
공간 복잡도
위 그래프는 공간복잡도를 보기 위해 입력사이즈에 따른 Capacity의 크기를 시각화한 것이다. 보시다시피 특정 지점에서 reserve를 통해 Capacity 가 증가하는 것을 확인 가능하다. 그리고 Linear의 경우 공간복잡도가 모든 다른 경우의 하한으로 훌륭하게 나오는 것을 확인 가능하다. $($물론 시간복잡도는 제일 떨어지겠지만$)$
또한, Exp3.0의 경우 reservefirst인 경우보다 오히려 특정시점 이후에는 메모리가 크게 뛰는 것을 확인가능하다. 이처럼 growth factor가 커질 경우 시간 복잡도 자체는 개선되지만 메모리를 필요이상으로 잡아먹어 심한 경우 reservefirst인 경우보다 3배 가까이 차이가 날 때도 있다. 아마 이러한 메모리 문제 때문에 growth factor를 1.5에서 2.0으로 비교적 낮다 느낄 수 있는 수치로 사용하는 가장 큰 이유라고 본다.
결론
아마 vector라는 자료구조는 c++을 사용하는 사람이라면 어느 정도 내부 구조를 알고 작동방식을 이해하고 있을 것이다. 또한, 본 포스팅을 제외하고도 vector에 대한 많은 포스팅이 이미 존재한다. 그래서 이 포스팅에서는 단순 vector의 작동방식과 장점뿐만 아니라 주의점을 중심적으로 다루고 싶었다.
여기서 다룬 vector의 주의점은 재할당으로 인한 시간 소요 문제와 사전에 reserve 하는 방식보다 메모리를 더 소요할 수있다는 문제 2가지이다. 본 포스팅을 통해 독자들이 vector에 대해 좀 더 심도 깊게 사용할 수 있는 계기가 되면 좋겠다.
PS. 제대로 된 글 쓴 거는 이번이 처음인데 피드백 사항이나 질문 사항이 있으면 자유롭게 댓글로 남겨주면 좋겠다.
실구현과 라이브러리의 성능 차이는 원인파악되면 수정하겠다.
참고 자료
지금까지의 그래프(csv)나 실제 테스트 코드 등은 아래 git에 정리돼있으니 그대로 reproducing이 가능하다.