고정 크기 배열

초기 프로그래밍 언어들은 배열 기능이 그리 뛰어나지 않았다. 특정 크기로 배열을 생성하면 이후 크기가 늘어나거나 줄어들지 않았다. C와 Objective-C의 표준 배열도 여전히 이런 방식을 따른다.

다음과 같이 배열을 정의하면,

int myArray[10];

컴파일러는 40바이트의 연속된 메모리 블록을 할당한다(int가 4바이트라고 가정할 때):

10개의 요소를 담을 수 있는 배열

이 배열은 항상 이 크기로 유지된다. 10개 이상의 요소를 저장하려면 공간이 부족해 불가능하다.

배열이 가득 찼을 때 크기를 늘리려면 Objective-C의 NSMutableArray나 C++의 std::vector 같은 동적 배열 객체를 사용하거나, Swift처럼 필요에 따라 용량을 늘리는 언어를 선택해야 한다.

고정 크기 배열의 주요 단점은 크기를 미리 충분히 설정해야 한다는 점이다. 너무 작으면 공간이 부족하고, 너무 크면 메모리가 낭비된다. 또한 버퍼 오버플로우로 인한 보안 취약점이나 충돌에 주의해야 한다. 요약하면 고정 크기 배열은 유연하지 않고 오류에 대한 여유가 없다.

그럼에도 고정 크기 배열은 간단하고 빠르며 예측 가능하기 때문에 좋아한다.

배열의 일반적인 연산은 다음과 같다:

고정 크기 배열에서 추가 연산은 배열이 가득 차지 않았다면 간단하다:

새로운 요소 추가

인덱스로 조회하는 것도 빠르고 간단하다:

배열 인덱싱

이 두 연산은 **O(1)**의 복잡도를 가지며, 배열 크기와 상관없이 일정한 시간이 걸린다.

크기가 늘어나는 배열의 경우 추가 연산은 더 복잡하다. 배열이 가득 차면 새로운 메모리를 할당하고 기존 내용을 새 메모리 버퍼로 복사해야 한다. 평균적으로 추가 연산은 여전히 **O(1)**이지만, 내부적으로는 예측하기 어렵다.

비용이 많이 드는 연산은 삽입과 삭제다. 끝이 아닌 위치에 요소를 삽입하면 나머지 배열을 한 칸씩 이동시켜야 한다. 이는 상대적으로 비용이 큰 메모리 복사 작업을 수반한다. 예를 들어 배열 중간에 값 7을 삽입하는 경우:

삽입은 메모리 복사를 필요로 함

삽입 지점 이후의 인덱스를 사용하는 코드가 있다면 이제 그 인덱스들은 잘못된 객체를 가리키게 된다.

삭제도 비슷한 방식으로 메모리 복사를 필요로 한다:

삭제도 메모리 복사가 필요함

이것은 NSMutableArray나 Swift 배열에도 해당된다. 삽입과 삭제는 O(n) 연산으로, 배열이 클수록 더 많은 시간이 걸린다.

고정 크기 배열은 다음과 같은 경우에 적합하다:

  1. 필요한 최대 요소 수를 미리 알고 있을 때. 게임에서 동시에 활성화될 수 있는 스프라이트 수가 그 예시다. 이를 제한하는 것은 합리적이다. (게임에서는 필요한 객체를 미리 할당하는 것이 좋다.)
  2. 배열을 정렬할 필요가 없을 때, 즉 요소의 순서가 중요하지 않을 때.

배열을 정렬할 필요가 없다면 insertAt(index) 연산이 필요하지 않다. 배열이 가득 차기 전까지 새로운 요소를 끝에 추가하면 된다.

요소를 추가하는 코드는 다음과 같다:

func append(_ newElement: T) {
  if count < maxSize {
    array[count] = newElement
    count += 1
  }
}

count 변수는 배열의 크기를 추적하며, 마지막 요소 바로 다음 인덱스로 간주할 수 있다. 이 인덱스에 새로운 요소를 삽입한다.

배열의 요소 수를 확인하는 것은 단순히 count 변수를 읽는 것으로, O(1) 연산이다.

요소를 삭제하는 코드도 간단하다:

func removeAt(index: Int) {
  count -= 1
  array[index] = array[count]
}

이 코드는 삭제할 요소를 마지막 요소로 덮어쓰고, 배열 크기를 줄인다.

삭제는 단지 하나의 요소를 복사하는 것

이 때문에 배열은 정렬되지 않는다. 잠재적으로 큰 부분을 복사하는 비용을 피하기 위해 단 하나의 요소를 복사하지만, 이는 요소의 순서를 변경한다.

이제 배열에는 요소 6의 복사본이 두 개 있지만, 이전의 마지막 요소는 더 이상 활성 배열의 일부가 아니다. 이는 단지 쓰레기 데이터일 뿐이며, 다음에 새로운 요소를 추가할 때 이전 버전의 6은 덮어쓰여진다.

이 두 제약 조건(요소 수의 제한과 정렬되지 않은 배열) 하에서 고정 크기 배열은 여전히 현대 소프트웨어에서 사용하기에 적합하다.

다음은 Swift로 구현한 예제다:

struct FixedSizeArray<T> {
  private var maxSize: Int
  private var defaultValue: T
  private var array: [T]
  private (set) var count = 0
  
  init(maxSize: Int, defaultValue: T) {
    self.maxSize = maxSize
    self.defaultValue = defaultValue
    self.array = [T](repeating: defaultValue, count: maxSize)
  }
  
  subscript(index: Int) -> T {
    assert(index >= 0)
    assert(index < count)
    return array[index]
  }
  
  mutating func append(_ newElement: T) {
    assert(count < maxSize)
    array[count] = newElement
    count += 1
  }
  
  mutating func removeAt(index: Int) -> T {
    assert(index >= 0)
    assert(index < count)
    count -= 1
    let result = array[index]
    array[index] = array[count]
    array[count] = defaultValue
    return result
  }
  
  mutating func removeAll() {
    for i in 0..<count {
      array[i] = defaultValue
    }
    count = 0
  }
}

배열을 생성할 때 최대 크기와 기본값을 지정한다:

var a = FixedSizeArray(maxSize: 10, defaultValue: 0)

removeAt(index: Int)는 남은 "쓰레기" 객체를 정리하기 위해 마지막 요소를 defaultValue로 덮어쓴다. 일반적으로 이 중복 객체를 배열에 남겨두는 것은 문제가 되지 않지만, 클래스나 구조체라면 다른 객체에 대한 강한 참조를 가질 수 있으므로 이를 초기화하는 것이 좋다.

Swift Algorithm Club을 위해 Matthijs Hollemans가 작성