Swift | Array capacity, reserveCapacity

 

Swift의 모든 배열은 데이터를 저장할 수 있는 특정 양의 메모리를 예약합니다.

insert나 append와 같은 추가 작업에 대비하기 위해서인데요.

 

배열에 요소를 추가할 때 해당 배열이 예약된 용량(capacity)을 초과하기 시작하면

배열은 더 큰 메모리 영역을 할당하고 해당 요소를 새 메모리에 복사합니다.

 

새 메모리의 크기는 이전 메모리 크기의 배수입니다.

 

capacity를 초과해서 append 될 때마다 2배로 늘어나고 있습니다.

 

새 메모리를 할당할 때마다 성능이 문제되는거 아냐? 하겠지만 우리는 재할당에 대한 비용을 걱정하지 않아도 됩니다!

 

왜냐하면 이렇게 두배씩 증가하는, 기하급수적으로 메모리를 증가시키는 전략을 사용하기 때문입니다!

배열 크기가 커질수록 재할당 빈도는 줄어들게 되겠죠?

 

그런걸 amortized constant-time performance 이라고 하는데 그건 아래에 설명해볼게요ㅠ

 

 

위의 그래프와 같이요!! count는 일정한 기울기를 가지고 증가하지만 capacity는 계단식으로 일정 구간에만 점프하고 있습니다.

 

 

 

 

 

reserveCapacity(_:)

만약 추가할 데이터의 수를 미리 알고 있을 경우에 저장 공간을 예약해 둘 수도 있습니다. reserveCapacity 함수를 사용해서요!

values 배열의 capcity를 특정 숫자로 예약할 수 있습니다. 이 방법으로 초과 할당을 방지할 수 있습니다.

 

 

 

 

하지만 이 방법은 주의해서 사용해야 한다고 하네요!!

왜냐면 Swift에서 배열은 amortized constant-time 란 걸 달성하기 위해 기하학적 할당 패턴 즉 위에서 설명했던 두배로 용량을 늘리는 방법을 사용하는데요!

 

 

  var values: [Int] = [0, 1, 2, 3]

  // Don't use 'reserveCapacity(_:)' like this
  func addTenQuadratic() {
      let newCount = values.count + 10
      values.reserveCapacity(newCount)
      for n in values.count..<newCount {
          values.append(n)
      }
  }

요런 코드는 amortized constant-time performance  가 아닌 삽입이라고 하네요?

만약 이 함수가 많이 호출된다면 선형으로 성능이 감소할 수 있다고 합니다.

 

 

 

 func addTen() {
      let newCount = values.count + 10
      for n in values.count..<newCount {
          values.append(n)
      }
  }

이런 선형 증가에서는 위에서 말한 기하학적 할당 패턴을 사용하는 방법이 좋다고 합니다. 

 

 

 

그래서....amortized constant-time performance 가 과연 무엇이냐!!

 

만약 우리가 백만 번의 수술을 한다고 합시다.

그럴 때 한 번 엄청 오래 걸리는 경우도 있겠지만 대부분의 수술이 빠른 시간 내에 작업이 끝난다고 하면

- 수술 백만 번에 대해 최악의 경우나 최선의 경우-는 그 수술을 백만 번 반복했을 때

 

총 시간이 얼마나 걸리냐.. 에 그렇게 영향이 미치지 않겠죠?! 

 

 

즉 "가끔 느림"이 희석될 만큼 드문 경우면 수술이 가끔 느리더라도 문제가 되지 않습니다.

 

 

amortized time은 많은 작업을 수행하는 경우 작업당 소요되는 평균 시간을 의미합니다. 

 

 

자 이제 요소를 반복적으로 추가하는 동적 배열을 예로 들어 보겠습니다.

일반적으로 요소를 추가하는 데 일정한 시간이 걸립니다. (O(1))

 

그런데 배열이 가득 찰 때마다 두 배의 공간을 할당하고 데이터를 새 영역에 복사하고 이전 공간을 해제합니다.

할당 및 해제가 일정한 시간에 실행된다고 가정하면 이 확장 프로세스는 O(n) 시간이 걸립니다.

여기에서 n은 현재 배열의 크기입니다.

 

 

 

따라서 확장할 때마다 마지막 확장보다 두 배의 시간이 걸립니다. 하지만 확장이 일어나기까지 두배의 시간도 지났죠! 

 

위의 그래프처럼 말입니다. 점점 계단의 바닥이 길어지고 있죠?

따라서 평균을 생각한다면 각 확장 비용은 각 삽입사이에 "분산"될 수 있습니다.

 

즉 장기적으로 m개의 항목을 배열에 추가하는 데 걸리는 총 시간은 O(m)이므로 amortized time은 O(1)이 됩니다.

 

 

 

 

출처

• https://developer.apple.com/documentation/swift/array/1538388-capacity
• https://developer.apple.com/documentation/swift/array/1538966-reservecapacity
• https://stackoverflow.com/questions/200384/constant-amortized-time