[Swift] The Swift Arcade Data Structures and AlgorithmsBootcamp - Array

Array 특징 세가지

- Arrays can contain anything

 

- Arrays are of a fixed size

배열은 고정된 크기를 가지고 있다.

Swift 에서는 배열을 생성할 때 크기를 지정하지 않기 때문에 Swift에서는 그 크기를 볼 수 없음

다른 언어에서는 배열을 초기화할 때 크기를 지정하기도,, Swift는 좀 다르지만 주의해야할 사항이 있음

(근데 알고리즘 문제 풀 땐 꽤나 많이 사용하는 Array(repeating: , count: ) ...)

 

- Arrays support random access

연결리스트, 스택, 큐, 이진트리 모두 불가능하지만 Array는 가능한 것이 모든 요소에 접근 가능한 것

배열이 아무리 커지더라도 인덱스를 알면 O(1)로 그 인덱스의 값을 가져올 수 있다

 

---

Insert & Delete

Array에 값을 삽입하거나 삭제할 때는 복사 - 삽입/삭제 - 증가/감소 의 순서를 따른다

 

ex) Insert

인덱스1에 B를 삽입하려고 할 때

1 인덱스1의 요소와 그 뒤에 있는 모든 요소를 오른쪽으로 이동해서 복사

2 B 삽입

3 카운터를 증가시키고 크기를 변경

(Delete는 반대로 복사 - 삭제 후 크기 변경)

 

모든 요소를 복사 후 이동시켜야 할 수도 있기 때문에 최악의 경우는 O(n) 이라는 것을 알 수 있다

---

Swift 에서의 배열 크기 조정

배열이 충분히 크지 않은데 값을 넣으려고 할 때 일어나는 일 

 

1. 배열에 자리가 부족하다는 것을 판단

2. 기존 배열의 크기의 2배에 해당하는 크기의 새로운 배열을 만듬

3. 새로운 배열에 기존 배열 요소들을 복사

4. 포인터를 old 배열에서 new 배열로 옮김

5. 새로운 값을 Insert

 

 기존 배열 요소를 모두 복사해야 하므로 배열 크기 조정에 O(n)이 걸린다 

 

ex)

var array = ["a", "b", "c", "d"]
array.insert("e", at: 99)

이 배열에서  99번째 인덱스에 e를 넣으려고 하면 인덱스 예외가 발생해서 에러가 난다

 

array.append("e")

하지만 append를 사용하면 배열 끝에 e를 추가할 수 있다

 

 

그렇다면 항상 append 할 때 마다 O(n)이 걸릴까?

 

---

 

Swift 에서 Array는 지수전략으로 배열 크기를 늘린다

 append로 하나의 요소를 추가하는 작업은 평균 O(1) 이다.

- Array에 추가적인 수용공간이 있고 다른 인스턴스와 스토리지를 공유하지 않을 때, 단일 요소 추가는 O(1)

- Array에 요소를 추가하기 전 스토리지를 재할당 해야하거나 스토리지를 다른 복사본과 공유해야 하는 경우, 단일 요소 추가는 O(n)

 

 

여기에서 말하는 스토리지를 재할당 해야하는 경우란 ? -> 추가적인 수용공간이 없는 경우

 

좀 더 자세히 보자

 

https://developer.apple.com/documentation/swift/array

맨 윗 문단만 해석해보면

 

모든 배열은 그 내용들을 가지고 있기 위한 메모리 양을 가지고 있다.

 

배열에 요소들을 추가하려고 할 때 그 배열에 담을 수 없을 만큼 초과되면,

배열은 새로운 스토리지에 더 큰 메모리를 할당하고 그 스토리지에 요소들을 복사함 

 

이 때 새로운 스토리지는 이전 스토리지의 배수임

그러면 계속해서 배열이 커질수록 만들어지는 새로운 스토리지 메모리는 기하급수적으로 커질 것 ..!

그렇다는 말은 배열의 크기를 초과하는 횟수가 점점 줄어든다는 것이다

 

재할당을 발생하는 요소 추가 작업은 어느정도의 비용이 들지만, 배열이 커지면 커질수록 재할당은 더 적게 발생한다 !

그래서 전체적으로 평균을 내보면 O(1)이 된다