[팁]2차원 배열의 할당

c++ 에서 2차원 배열을 할당하는 방법은 아래와 같습니다.

int arr[100][100];

100*100 의 int 형 배열이 stack 영역에 잡히게 됩니다.

stack 의 크기(보통 1~8MB 정도) 가 넘어가는 배열을 잡으려면, data 영역(전역 변수) 혹은 heap 영역(동적 할당) 을 이용하여 메모리를 할당해야 합니다.

data 영역은 stack 영역에정의하는 방법이 같으므로 우리는 heap 에 메모리 공간을 잡는 것에 대해 알아보도록 하겠습니다.

int[3000][2000] 배열은 stack 영역에 잡히지 않으므로, 아래와 같이 동적할당을 통해 run time 에 메모리를 할당받아 사용합니다.

int **arr = new int*[3000]; for (int i = 0; i < 3000; ++i) arr[i] = new int[2000]; for (int i = 0; i < 3000; ++i) delete[] arr[i]; delete[] arr;

먼저 arr 이중 포인터 변수에 배열의 높이 만큼(여기서는 3000*2000사각형 배열) 을 할당합니다.

그리고 3000만큼 루프를 돌며 arr[n] 에 배열의 너비 만큼 메모리를 할당합니다.

모두 사용한 다음에는 할당한 것과 반대 순서로 메모리를 해제 해줍니다.

이렇게 2차원 배열을 만들게 되면 메모리 할당 연산을 높이+1 번 만큼 해주어야 합니다.

new 연산 혹은 malloc() 등 과 같은 heap 영역 메모리 할당 요청은 할당크기를 k 라 할때 O(k) 만큼의 비용이 들지만 할당크기-시간 그래프에서 기울기가 1보다 작은 형태로 나옵니다.

(실질적으로 많이 사용 될 수십MB 정도 까지의 할당 시간에서는 유의미한 데이터를 뽑아내기가 어려웠습니다.)

따라서 위와같이 높이만큼 동적 할당을 하게되면, O(n*k) 만큼의 비용이 들게 됩니다. 물론 메모리를 반환할때에도 O(n*k) 의 비용이 듭니다.

따라서 배열을 동적 할당 할 때에는 위와같은 방법이 아닌 아래 코드와 같은 방법으로 할당을 하여야 합니다.

int **arr = new int*[3000]; arr[0] = new int[3000*2000]; for (int i = 1; i < 3000; ++i) arr[i] = arr[0] + 3000*i; delete[] arr[0]; delete[] arr;

처음 포인터 배열을 높이 만큼 할당하는것은 기존의 코드와 같습니다.

다음으로 2차원 크기를 한번에 1차원 배열에 할당합니다.

마지막으로 포인터 배열의 각 원소에 2차원 크기로 할당한 1차원 배열을 배열의 너비 만큼 띄워서 연결시켜 주면, stack 영역에 선언한 배열과 완전히 동일한 메모리 구조를 가진 2차원 배열이 완성 됩니다.

단 두번만의 new 연산 호출로 2차원 배열이 완성되었습니다.

높이 만큼의 루프를 돌지만, 대입연산과 메모리 할당 연산을 비교해 본다면 대입연산은 거의 없는시간이라고 할 수 있습니다.

#include<iostream> #include<chrono> int main(int argc, char*argv[]) { int **arr = nullptr; int size = 1000, count = 1000; auto start = std::chrono::high_resolution_clock::now(); // case 1 : 2차원 배열의 동적 할당 기존의 할당 방법 for (int i = 0; i < count; ++i) { arr = new int*[size]; for (int j = 0; j < size; ++j) arr[j] = new int[size]; for (int j = 0; j < size; ++j) delete[] arr[j]; delete[] arr; } auto end = std::chrono::high_resolution_clock::now(); std::cout << "Allocate each columns : " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "us" << std::endl; start = std::chrono::high_resolution_clock::now(); // case 2 : 2차원 배열의 동적 할당 1차원으로 할당 for (int i = 0; i < count; ++i) { arr = new int*[size]; arr[0] = new int[size*size]; for (int j = 1; j < size; ++j) arr[j] = arr[0] + size * j; delete[] arr[0]; delete[] arr; } end = std::chrono::high_resolution_clock::now(); std::cout << "Allocate once : " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "us" << std::endl; return 0; }

위의 코드에서 size 를 1000, count 를 1000 으로 두고 실행하게 되면,

결과적으로 같은 크기의 메모리를 할당 하였는데, 드는 시간이 100배 이상 차이가 나는 것 을 볼 수 있습니다.

(물론, 사용자의 환경에 따라 차이가 있겠지만, 메모리 할당 연산이 오버헤드가 크다는 것 입니다.)

(g++ 에서 테스트 해보니 차이가 많이 나네요. 역시 g++ 의 최적화는 엄청난거 같습니다.)

여기서 포인터 배열이 없더라도 1차원 배열을 2차원처럼 사용하는것이기에, 인덱스를 연산하여 접근 할 수 있습니다.

int *arr = new int[height*width]; int *arr = new int[height*width]; for (int i = 0; i < height; ++i) { for (int j = 0; j < width; ++j) { arr[width*i + j]; // 기존 2차원 배열 접근을 arr[i][j] 라고 하였을 때. } }

같은 원리로 n차 배열을 new 연산 n번 호출 혹은 new 연산 단 한번의 호출 만으로 만들 수 있습니다.

1. 메모리 할당 연산은 오버헤드가 굉장히 크다.

   할당한 메모리는 해제하지 말고, 재사용 하자.

   할당 연산자를 최소한으로 하는 코딩을 하자.