배열 시리즈 중 4번째 글입니다.
- 배열에 대해 알아봅시다. 링크
- row major와 column major에 대해 알아봅시다. 링크
- 배열 주요 연산 시간복잡도를 대해 알아봅시다. 링크
- dynamic array에 대해 알아봅시다. [현재글]
이 글에서는 자료구조 동적배열에 대해 알아보겠습니다.
1칸씩 확장하기
정적 배열이란, 크기가 정해진 배열을 말합니다. 반면, 동적 배열은 크기가 변하는 것을 의미합니다. 그러면, 아래 연산이 추가됩니다.
- 배열의 크기를 증가시키는 grow
이 연산에 대해서 깊게 파헤쳐 보겠습니다.
먼저 크기가 4인 배열이 있어요. 배열의 맨 뒤에 추가하는 것은 O(1)이라고 했어요. 그런데, 크기가 4인 배열이 꽉 찼기 때문에, 더 이상 추가할 수 없어요. 공간을 확장해야 겠지요. 하나 늘려보겠습니다.
5를 추가하기 위해, 길이가 5인 배열을 만듭니다. 그리고, 길이가 4인 배열에 있었던 원소들을 모두 복사합니다. 다음에 길이 4인 배열을 버립니다.
길이 5짜리 배열에 추가하려니, 공간이 없어요. 그렇기 때문에 공간 6짜리 배열을 만듭니다. 다음에, 길이 5짜리 배열에 있던 것을 복사합니다. 그 다음에 길이 5인 배열을 버립니다. 이렇게 grow를 할 때, 1개씩 확장하면 굉장히 비효율적으로 동작합니다.
길이 n짜리 배열을 1칸만 확장하는 경우
- 길이 n+1의 새로운 배열을 만듭니다.
- 길이 n에 있는 원소 n개를 새로운 배열에 복사합니다.
- 새로운 배열의 n+1번째 위치에 새로운 원소를 추가합니다.
- 길이 n의 배열을 버립니다.
1칸씩 확장할 때 마다 비효율의 끝을 달리게 됩니다.
k 배 만큼의 공간을 추가로 확장하기
대신에, k배 만큼의 공간을 추가로 grow가 될 때 마다 확장하게 할 수 있습니다. 기존 배열 대비, 확장된 배열이 x배율이 되었을 때, 이 x를 grow rate라고 합니다. 예를 들어, 크기가 4인 배열이 확장될 때, 1배 만큼의 공간을 추가로 확장해서 8이 되는 식입니다. 이 때, grow rate는 2가 되겠네요. 8을 4로 나누면 2이기 때문입니다.
크기가 n인 배열이 있습니다. n+1번째 원소를 추가하려고 하는 데 공간이 없어요.
기존 배열보다 kn개의 원소를 더 담을 수 있는 배열을 만듭니다. 그리고, n+1번째 위치에 n+1을 추가합니다. 여기까지 보면 1개씩 확장할 때와 별 다를 것이 없어 보여요. 오히려 더 비효율적인 거 같습니다. 중요한 것은 n+kn번째 원소가 추가될 때 arr이 확장이 되지 않는다는 것입니다.
배열이 한 번 확장되었습니다.
- 크기가 n + kn인 배열이 새로 생성되었습니다.
- 원소 n개를 복사했습니다.
- 크기가 n인 배열이 버려집니다.
그리고, kn개의 원소를 추가할 때까지 확장이 되지 않았습니다. 오로지 뒤에 추가하는 비용만 있을 뿐입니다. 뒤에 원소를 추가할 때 마다 발생하는 비용을 계산해 봅시다. 이 3개의 비용을 kn으로 나눠 볼까요?
- 평균적으로 크기가 1 + 1/k 인 배열을 생성하였습니다.
- 평균적으로 1/k개의 원소를 복사했습니다.
- 평균적으로 크기가 1/k 인 배열이 버려집니다.
k는 적당히 큰 실수이기 때문에, 이 3개의 비용이 상수에 가깝게 됩니다.
Java의 ArrayList
이제 동적 배열을 쓰는 ArrayList를 간단하게 보도록 합시다.
grow 메서드는 원소를 추가하는 과정에서 공간이 부족하면 아래와 같은 일을 합니다.
- 새로운 배열을 만듭니다.
- 기존 배열의 원소들을 새로운 배열에 복사합니다.
여기서 6번째 줄을 봅시다. oldCapacity >> 1 이 부분입니다. 이는, 기존 배열 길이의 0.5배만큼 추가로 할당한다는 의미입니다.
newLength 메서드 안으로 들어가 봅시다. prefGrowth와 minGrowth의 최댓값만큼 기존 Length에서 증가시킴을 알 수 있습니다. 1.5 배율에 가깝게 확장하는 것입니다.
soft_max_array_length는 21억이 넘는 꽤나 큰 수입니다.
나머지 부분을 봅시다. 현실적으로, prefLength가 21억이 넘어갈 일은 거의 없기 때문에, 보통 else절이 아닌 if절을 타게 됩니다. 그렇기 때문에 grow가 될 때, 최소 1.5 배율만큼 뻥튀기가 될 수 있습니다.