Resizing Array

기본적으로 C언어, Java 등에서 배열은 초기화할 때 크기를 지정해주고 그 크기로 고정됩니다.

이 경우, 데이터 크기를 미리 알기 어려운 상황도 많아 미리 크기를 지정하기가 불편합니다.

 

이에 대해 보완책으로 나온 것이 Resizing Array 입니다.

저장된 데이터 양에 따라 크기를 자동 조정하는 자료구조로 기본 배열처럼 index로 원소 접근이 가능합니다.

파이썬의 List, 자바의 ArrayList가 이에 해당합니다.

 

Resizing Array의 내부적 구현은 두가지가 있습니다.

1. 연결리스트

2. 기본 배열 사용한 구현

 

이중 1번은 인덱스를 이용한 원소의 접근이 O(N)이라 잘 사용하지 않습니다.

2번의 경우, 더 많은 공간이 필요하면 더 큰 배열을 만들어 기존의 데이터를 복사합니다.

 

위의 1, 2번을 좀더 자세히 비교해보겠습니다.

 

1. Linked List

(1) 메모리 사용량: 다음 노드의 reference를 저장할 추가공간 필요

(2) 메모리 간 전송 속도: 디스크 -> 메모리 -> 캐시로 읽어올 때 여러 노드가 다른 블록에 흝어져있어 읽어오는 시간이 오래 걸림

(3) 임의 위치 원소 접근이 O(N)

(4) 새 원소 추가는 O(1)

(5) 임의 원소의 추가/삭제 : 탐색에 O(N), 추가 및 삭제는 O(1)

 

2. 기본 배열 사용 구현

(1) 메모리 사용량: 다음 노드의 위치가 명확하여 이에 대한 reference를 저장할 필요 없음

(2) 메모리 간 전송 속도: 디스크 -> 메모리 -> 캐시로 읽어올 때 모든 노드가 메모리에서 인접해 있으므로 같은 블록에 속해 읽어오는 시간 빠름 (컴퓨터의 읽어들이는 작업은 블록 단위)

(3) 임의 위치 원소 접근이 O(1)

(4) 가끔 새 배열 만들고 기존 원소 복사할 필요 있으나 평균적으로는 O(1)에 추가 가능

(5) 임의 원소의 추가/삭제 : 탐색에 O(1), 추가/삭제는 뒤의 원소를 한 칸씩 이동시키는데 O(N)

 

 

3. 기본 배열 사용한 Resizing array 구현 시 Resize하는 비용 구하기

 

크기 1인 배열에서 시작해 원소가 가득 찼을 때 2배 크기 배열 만들고, 기존 원소를 복사한다고 가정해보겠습니다.

 

새 배열 만드는 비용 (메모리 할당): O(1)

기존 원소 복사 비용: 원소 개수에 비례 -> 이 때 이 resizing비용은 원소 추가 때마다 매변 일어나지 않고 한번씩 일어나므로, 평균적으로 비용이 어느 정도인지 분석해봅시다.

 

현재 원소가 N개라 가정해보겠습니다.

이 때 2^(k - 1) <= N < 2^k  (왜 그런지는 아래에서 설명하겠습니다.)

원소 추가에 드는 비용은 1 + 2 + ..... + 2^k = 2^(k + 1) - 1 이 됩니다. (by 등비수열의 합 공식)

즉, N에 비례합니다.

따라서 원소 추가 한번당 평균비용은 N / N = ~1이므로 평균적으로 Resizing Array에서 원소 추가비용은 상수비용이라고 생각하면 됩니다.

 

 

4. 초기화 & Doubling

 

처음에 N = 10 크기로 초기화했다고 가정해봅시다. (언어, 버전마다 조금씩 달라질 수 있으며 사용자가 초기 사이즈 지정도 가능합니다.)

 

이 때 배열이 가득 차면 2N 크기 배열을 만들어 기존 원소를 복사합니다.

원소를 삭제할 때도 비슷한데 차이가 있습니다.

원소를 삭제할 때는 원소 수가 N / 4개가 되면 N / 2의 크기의 배열을 만들어 기존 원소를 복사합니다.

이는 불필요한 메모리의 낭비를 줄이기 위함입니다.

(이 때, N은 2의 제곱수 입니다.)

 

크기 축소 임계치를 N / 4로 정한 이유가 궁금할텐데, 그 이유를 예를 들어 설명해보겠습니다.

 

크기 축소 임계치가 N / 2, 현재 크기가 32인 배열에서 원소 개수가 현재 17개라고 가정해봅시다.

여기서 원소 한개를 더 삭제하여 원소의 개수가 16개가 되면 크기가 16인 배열을 만들어 기본 원소를 복사하게 됩니다.

이 때, 원소 1개가 추가되면 다시 크기가 32인 배열을 만들어 기존 원소를 복사하게 됩니다.

 

이와 같은 작업이 반복되면, 배열의 복사가 매 과정 일어나게 되어 비효율적입니다.

 

이와 같은 특정 조건에서 나타나는 비효율적 작업의 반복을 Thrashing(같은 곳을 반복해서 세게 때림) 이라 합니다.

 

 

5. 삭제(pop)

 

pop(index): index 위치 원소를 삭제(하며 반환)하는 기능입니다.

삭제한 뒤 바로 뒤 원소 ~ 마지막 원소를 한칸씩 앞으로 옮겨담는 과정이 필요하기 때문에 O(N)의 비용이 듭니다.

 

이 작업이 비효율적이기 때문에 array 가장 앞 원소를 삭제하는 기능이 필요한 경우는 deque을 많이 사용합니다.

(다만, deque은 연결리스트로 구현되어 있기 때문에 임의의 원소의 탐색이 O(N)입니다. 이를 염두에 두고 사용하여야 합니다.)

Stack이 필요한 경우, 추가 역시 O(1), pop역시 O(1)의 비용이 소모되므로 효율적입니다.

 

 

정리

 

Resizing Array는 매우 편리하고 많은 경우 성능도 괜찮지만 현재 application에서 resizing array에 접근하는 방식을 생각해볼 때 더 효율적인 자료구조가 있지는 않을까 꼭 한번은 고민해볼 필요가 있습니다.