구름

[팁]2차원 배열의 할당 본문

👨‍💻 C++

[팁]2차원 배열의 할당

라탄 2016. 9. 2. 19:05

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

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


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

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


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



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

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

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

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


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

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

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


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


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

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

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

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

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

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

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

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

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


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


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


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

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

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



1 Comments
댓글쓰기 폼