배열(Array)

정의

Array란 ordered된, random-access collection이다.

Swift에서 배열은 generic structure로 구현되어 있다. 따라서 Element에 따라 다양한 타입이 저장될 수 있고, 타입 유추를 통해 Element type을 정의할 수 있다.

구현

다음은 배열의 구현체이다.

@frozen
public struct Array<Element>: _DestructorSafeContainer {
  #if _runtime(_ObjC)
  @usableFromInline
  internal typealias _Buffer = _ArrayBuffer<Element>
  #else
  @usableFromInline
  internal typealias _Buffer = _ContiguousArrayBuffer<Element>
  #endif

  @usableFromInline
  internal var _buffer: _Buffer

  /// Initialization from an existing buffer does not have "array.init"
  /// semantics because the caller may retain an alias to buffer.
  @inlinable
  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}

선언

선언법은 다음과 같다.

접근

For-in, ForEach를 사용하여 배열의 요소에 순차적으로 접근할 수 있다.

isEmpty로 배열이 비어있는지 여부, count로 배열의 크기를 알 수 있다.

.first, .last 프로퍼티로 첫번 째, 마지막 원소를 가져올 수 있다. (없으면 nil)

subscript를 사용하여 individual한 배열의 원소에 접근할 수 있다.
index는 0부터 시작하며, 정해진 범위 내에 요소가 없을 경우 Index out of range 런타임 에러를 방출한다.

Growing the Size of an Array

모든 배열은 특정한 양의 메모리를 가지고 있다. 배열에 요소가 추가되고, reserved된 메모리를 초과하면 배열은 더 큰 메모리를 할당해 새로운 스토리지에 복사한다.

Capacity(_:) 메소드를 통해 정해진 capacity를 설정할 수 있다.

대부분의 element 타입에 대하여 저장소는 contiguous block of memory이다.

Modifying Copies of Arrays

Int같은 값 타입의 배열은 다음과 같이 복사된 배열과 원본 배열은 다른 값을 가진다. 즉 값 타입의 복사가 일어난다.

하지만 instance of a class를 요소로 가진 배열의 경우 레퍼런스 참조에 의해 복사된 배열과 원본 배열이 하나의 주소를 참조하게 된다.

아래 예시를 보면 firstArr과 secondArr은 같은 IntClass의 instance를 참조하고 있다. 따라서 firstArr[0].test = 1000을 하게되면 참조값이 바뀌기 때문에 secondArr의 값 또한 바뀐다.

firstArr[0] = IntClass() 구문이 실행되면 새로운 instance가 생성되어 서로 다른 참조를 바라보기 때문에 10과 1000이 출력된다.

class IntClass {
    var test = 10
}

var firstArr = [IntClass(), IntClass()]
var secondArr = firstArr

print("firstArr: \(firstArr[0].test)") 
print("secondArr: \(secondArr[0].test)")

// firstArr: 10
// secondArr: 10

firstArr[0].test = 1000

print("firstArr: \(firstArr[0].test)")
print("secondArr: \(secondArr[0].test)")

// firstArr: 1000
// secondArr: 1000

firstArr[0] = IntClass()

print("firstArr: \(firstArr[0].test)")
print("secondArr: \(secondArr[0].test)")

// firstArr: 10
// secondArr: 1000

Copy-on-Write

배열은, 다른 모든 variable-size인 collections와 같이, copy-on-write 최적화 기법을 쓰고 있다.
여러 개의 배열의 복사본은 수정하기 전까지 같은 저장소를 공유하고 있다.
수정이 일어나면 수정이 일어난 배열은 그것의 저장소를 uniquely owned copy로 replace한다.
이러한 최적화는 amount of copy를 reduce할 수 있다.

아래 예제를 보면 numbers, firstCopy, secondCopy는 같은 저장소를 공유하고 있고, numbers[0] = 100이 실행되면 numbers가 modification을 만들기 전에 유니크한 복사본을 만든다. 따라서 numbers의 값이 변경되더라도 복사본들의 값은 그대로 원본 저장소를 공유한다.

Bridging Between Array and NSArray

NSArray로 브릿징하려면 as 로 캐스팅하면 되고, 배열의 element가 이미 class의 인스터스이거나 @objc 프로토콜을 준수하면 O(1)의 시간 복잡도와 공간복잡도를 가진다. 이외의 경우에는 O(N)이 걸린다.

ContiguousArray와 ArraySlice는 브릿지되지 않는다.

ArraySlice

ArraySlice는 새로운 storage를 할당받지 않고 원본의 배열을 참조하고 있다.

주의해야할 점은 위 사진처럼 test[1..<4]를 가져왔을 경우 test[0]으로 접근하면 out of bounds 에러가 나온다.

또 하나 주의해야할 점은 ArraySlice는 Long term memory에 저장되는 것을 장려하지 않는다.
왜냐하면 원본 배열의 참조를 가지고 있어 참조 카운트가 증가해 memory leak이 생길 가능성이 있기 때문이다.

ContiguousArray

ContiguousArray는 배열의 요소를 연속적인 메모리 공간에 저장하는 specialized된 배열이다. 이것은 연속적인 메모리 공간에 저장하거나, NSArray instance에 요소를 저장할 수 있는 Array타입과 상반된다.

만약 배열의 element가 class타입이거나 @objc 프로토콜을 준수하고, NSArray로 브릿징할 필요가 없다면 ContiguousArray를 사용하는 것이 그냥 Array보다 효율적이다.

만약 배열의 element가 struct이거나 enum이면(값 타입이면) Array와 ContiguousArray는 같은 효율을 가진다.

Swift Array의 시간 복잡도

Swift는 다양한 최적화 기법을 통해 C에서의 성능을 가질 수 있다.

subscript로 접근해 element를 읽는데에는 O(1)의 시간이 걸린다.
하지만 다른 배열과 공유하거나 NSArray로 브릿징 될 경우 O(N)이 걸린다.

append는 평균 O(1) 최악의 경우(메모리를 재할당 해야할 경우) O(N)을 가진다.
removeLast, count, isEmpty 같은 경우 O(1)의 시간 복잡도를 가지고,
removeFirst는 특정 상황(self.subsequence: RangeReplaceableCollection)일 경우 등에는 O(n), 다른 경우는 대부분 O(1)을 가지고
insert(at:), remove(at:) 같은 경우 O(n)의 시간 복잡도를 가진다.

https://demian-develop.tistory.com/30

배열 정리

정리하자면 위 그림과 같이 배열은 연속적인 메모리에 할당된다.
값타입의 요소가 저장될 경우 Array와 ContiguousArray는 같은 성능을 가진다.
하지만 Array는 NSArray로 브릿징 될 가능성이 있어 참조 타입의 요소를 가질 때는 다르게 동작한다.
구현체에 나오듯 런타임이 옵씨일 경우 어레이 버퍼에, 이 외의 경우 contiguous 버퍼에 저장된다.
할당된 메모리가 모두 찼을 경우 해당 배열을 복사하여 새로운 메모리에 할당시킨다.
여기서 배열의 길이가 일정 크기 이상이 되었을 경우에는 stack메모리에서 heap메모리로 이동하며 배열의 시작 주소를 stack메모리에 참조한다.

틀린 점 있으면 댓글로 알려주세요 :)

연결리스트(Linked List)

연결 리스트란 메모리의 주소값을 가지는 header와 실제 데이터인 value를 가지는 노드 구조로 되어있다.

연결리스트의 특징으로는 자료의 추가와 삭제에서 O(1)의 시간을 가진다.
하지만 특정 위치의 데이터를 검색하는데에는 O(n)의 시간이 걸리는 단점을 가지고 있다.

연결리스트의 시간복잡도는 다음과 같다.

스택(Stack)

스택은 마지막에 들어온 원소가 처음 나오는 Last In First Out (LIFO)구조를 가진다.

위에 언급한 바와 같이 stack의 경우 popLast, removeLast, append와 같은 함수를 통해 배열로 충분히 만들 수 있다. 따라서 Swift에서는 따로 구현되어있지 않다.

큐(Queue)

큐는 처음 들어온 원소가 처음 나오는 First In First Out(FIFO)구조를 가진다.

Stack과 마찬가지로 removeFirst, append를 통해 배열을 queue처럼 쓸 수 있다. 다만 linkedList로 queue를 만들면 enqueue와 dequeue에서 모두 O(1)을 가지지만 Array에서 removeFirst는 상황에 따라 O(N)의 시간 복잡도를 가지므로 동일하게 동작한다고 확신할 수 없다.