Swift의 Array는 무한대로 커질까?

궁금증 해결 시리즈 첫 번째!

Swift의 Array는 과연 무한대로 커질까?

어느날.. Array를 당연하게 사용하고 있던 필자는 흥미로운 생각을 하게됐다.
보통의 프로그래밍 언어는 배열에 크기를 정해놓고 사용하게 된다.
C만 보더라도 그렇게 행하기도 한다.

근데, Swift는 보통 크기를 정해놓고 사용하지는 않는다.
그리고 정하지 않아도 잘만 동작한다.
그럼, 과연 Array의 끝은 존재할까?

공식문서 찬쓰!

Array

Generic Structure
An ordered, random-access collection.
Array는 정렬된 랜덤 액세스 컬렉션입니다.
랜덤 액세스 컬렉션이 뭔지 모른다면?

Array는 랜덤 액세스 컬렉션이기 때문에, 시간복잡도가 O(1)이다.

그리고 공식문서를 보다보면 이런 목차가 나온다.

Growing the Size of an Array

모든 Array는 컨텐츠를 저장하기 위해 특정 양의 메모리를 예약한다. Array의 요소를 추가하고, 해당 Array가 예약된 용량을 초과하기 시작하면 Array는 더 큰 영역의 메모리를 할당하고 해당 요소를 새 스토리지에 복사한다.
새 스토리지는 이전 스토리지 크기의 배수이다.
이러한 기하급수적인 크기 증가는 요소 추가가 일정한 시간에 이루어지며, 많은 추가 작업의 성능을 평균화한다는 것을 의미한다.
재할당을 하는 것 자체가 성능 비용이 들기는 하지만, Array가 커질수록 발생하는 빈도는 점점 줄어든다.

그렇다. 결국에 Array의 크기는 무한대로 커질 수 밖에 없는 구조이다. (무한대라고 해서 ㄹㅇ 무한대가 아니라, 결국에는 컴퓨터 하드웨어의 한계에 도달하면 거기서 끝은 나겠지만 말이다.)

정리를 해보자면, Array는 초기 설정시 용량을 예약(미리 설정같은 느낌인듯)하고 점점 추가하면서 용량이 차게 되면 그의 배수, 그의 배수 만큼 용량을 확보하는 것이다.

코드로 확인해보자!

var numd = [10, 20, 30, 40, 50]
print(numd.count)    // 5
print(numd.capacity) // 5
numd.append(contentsOf: stride(from: 60, through: 90, by: 10))
print(numd)          // [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(numd.count)    // 9
print(numd.capacity) // 10

Swift는 요소를 셀수 있는 것이 2개가 있다.
count와 capacity인데, 이 두개는 분명한 차이가 존재한다.

위 코드를 보면, 초기화를 5개의 Int 로 하였다. 따라서 count가 5 capacity도 5 이다.
여기서 capacity는 어떤 것을 의미하냐면, 새 저장소를 할당하지 않고 배열에 포함할 수 있는 총 요소의 수를 가리킨다.

그렇다면, 우리가 위에서 본 정의대로라면 이 이상부터 하나라도 추가하면 전체 용량은 10이 될 테다.

다음 코드를 보면 stride를 통해 60,70,80,90을 추가했다.
stride() 함수는 from(여기서부터) , through(여기까지), by(이 간격만큼) 만들어주는 함수이다.
따라서 4개의 수를 만들어서 append 시켰다.
그리고 결과를 보니 count는 9, capacity는 10이 됐다!

정의대로 2배의 크기로 증가한 모습이 인상적이다.

정리

결과적으로 Swift의 Array는 무한대로 커지는 것을 확인하였고, 커지는 방법은 할당한 용량의 두배의 크기로 늘리고 새로 복사시키는 방법을 택하였다. (이를 Array Doubling이라고도 불리나보다)

이로써 궁금증 해결!