[Data Structures & Algorithms in Swift ] Swift Standard Library

스위프트 표준 라이브러리는 스위프트 언어의 핵심 구성요소를 포함하는 프레임워크입니다. 이 안에는 스위프트 앱을 구축하는데 도움이 되는 다양한 툴과 타입이 있습니다.

사용자 정의 자료구조를 구축하기 전에, 스위프트 표준 라이브러리가 이미 제공하는 기본 자료 구조를 이해하는 것이 중요합니다.

🥑 Array

Array는 범용의 일반 컨테이너로 정렬된 요소들의 컬렉션을 저장하며, 스위프트 프로그램에서 일반적으로 사용됩니다. 대괄호로 둘러싼, 쉼표로 구분한 값들의 목록인 배열 리터럴 array literal 을 이용하여 배열을 생성할 수 있습니다.

let people = ["Brian", "Stanley", "Ringo"]

스위프트는 프로토콜을 이용하여 배열을 정의합니다. 이 각 프로토콜은 배열에 더 많은 기능을 부여합니다.

• 예를 들어 Array 은 Sequence 입니다. 이 말은 한번 이상 반복할 수 있다는 뜻입니다.
• 또한 Array는 Collection 입니다. 이 뜻은 비파괴적으로(nondestructively) 여러번 순회할 수 있고, 첨자 연산자(subscript oerator)를 이용하여 접근할 수 있습니다.
• 배열은 또한 효율성을 보장하는 RandomAccessCollection 이기도 합니다.
• 스위프트의 Array는 generic collection 으로도 알려져 있습니다. 어떤 타입에서도 작동할 수 있기 때문입니다.
• 실제로 대부분의 스위프트 표준 라이브러리는 제네릭 코드로 구축되어 있습니다.

🍞 Order

배열의 요소는 명시적으로 정렬되어 있습니다. 위의 people 배열을 예시로 들자면, "Brian" 은 "Stanley" 의 앞에 옵니다.

배열의 요소들은 모두 0 기반의 정수 인덱스를 가지고 있습니다. 예를 들어 people 배열은 3개의 인덱스를 가지고 있습니다. 각각 요소에 대응됩니다. 아래와 같이 작성해서 배열의 요소값을 검색할 수 있습니다.

people[0] // "Brian"
people[1] // "Stanley"
people[2] // "Ringo"

배열의 자료구조에서 순서가 정의되며 이 개념을 당연하게 여겨서는 안됩니다. Dictionary 와 같은 일부 자료구조는 순서에 대한 개념이 약합니다.

🍞 Random-access

Random-access 는 정해진 시간에 요소검색을 처리할 수 있을 경우 거론할 수 있는 특성입니다. 예를 들어 people 배열에서 "Ringo" 라는 요소를 가져오는데는 일정한 시간이 걸립니다. 다시 말해서 이 성능을 당연하게 여겨서는 안됩니다. linked list 나 tree는 일정한 시간동안 접근(constant time access)하는 권한이 없습니다.

🥑 Array performance

랜덤 액세스 외에도 다른 성능 영역들은 여러분들이 개발자로서 관심을 가질 영역입니다. 특히나 데이터의 양이 증가할 때 자료구조가 얼마나 잘 작동하는지 혹은 작동하지 않는지 말입니다. 배열의 경우 두가지 요인에 따라 달라집니다.

🍞 Insertion location

첫번째 요인은, 새로운 요소를 배열 어디에 삽입할 지 결정하는 것입니다. 가장 효율적인 시나리오는 새로운 요소를 추가할 때 배열 가장 뒤에 추가하는 것입니다.

people.append("Charles")
print(people) // prints ["Brian", "Stanley", "Ringo", "Charles"]

append 메소드를 이용하여 "Charles" 를 삽입하면 배열의 가장 끝에 위치하게 됩니다. 이를 constant-time 작업이라고 합니다. 이는 배열이 얼마나 커지든 상관없이 작업이 수행하는데 동일한 시간이 걸린다는 뜻입니다. 하지만 배열의 한 중간과 같이 특정 위치에 요소를 삽입해야될 때도 있습니다.

이 케이스가 왜 생기는지 설명하기 위해 아래의 유추를 생각해봅시다. 극장에서 여러분은 줄을 서서 기다리고 있습니다. 이 때 새로운 사람이 와서 줄을 서려고 합니다. 여기서 가장 간편한 위치가 어딜까요? 당연히 바로 마지막이죠.

새로온 사람이 줄의 가운데 끼어들려고 한다면, 그 줄에 있는 사람 중 절반을 설득해서 공간을 만들도록 해야할 것입니다.

만약 그 새로온 사람이 매우 무례하다면 줄의 맨 앞에 끼어들려고 할 것입니다. 최악의 시나리오입니다. 왜냐하면 줄에 서 있는 모든 사람들이 새로온 사람을 위한 맨 앞자리를 만들기 위해 뒤로 이동해야하니까요.

이게 바로 배열이 작동하는 원리입니다. 새로운 요소를 배열의 가장 끝이 아닌 다른 곳에 삽입한다면 기존의 요소들의 위치를 뒤로 교체해야합니다.

people.insert("Andy", at: 0)
// ["Andy", "Brian", "Stanley", "Ringo", "Charles"]

정확하게 하자면 모든 요소는 반드시 인덱스 하나만큼 뒤로 이동해야합니다. n 번의 단계가 필요합니다. 만약 배열의 요소가 두배라면 삽입 insert 작업에는 두배의 시간이 듭니다.

만약 요소를 배열에 맨 앞에 삽입하는 것이 여러분 프로그램의 일반적인 작업이라면, 데이터를 유지하기 위해서 다른 자료구조를 고려해봐야 할 것입니다.

삽입의 속도를 결정하는 두번째 요소는 배열의 용량 capacity 입니다. 보이진 않지만(underneath the hood) 스위프트의 배열은 안의 요소를 위한 공간을 미리 결정하여 할당됩니다. 이미 최대 용량인 배열에 새로운 요소를 추가한다면 배열은 더 많은 공간을 만들기 위해 재구조화 해야합니다. 배열의 기존 요소들을 모두 메모리상으로 더 큰 새 컨테이너에 복사하는 것입니다. 하지만 이것은 배열의 각 요소에 접근하고 복사하는 비용이 발생합니다.

어떤 삽입이든, 심지어 끝에 삽입하더라도, 사본이 만들어지는 순간 n개의 단계가 걸린다는 것입니다. 하지만 표준 라이브러리는 이 복사가 발생할 때 필요한 시간을 최소화하는 전략을 차용하고 있습니다. 스토리지가 부족하여 복사를 행할 때마다, 용량은 두배로 늘어납니다.

🥑 Dictionary

딕셔너리는 키-값key-value 의 쌍을 가지고 있는 또 다른 제네릭 콜렉션입니다. 예를 들어 사용자의 이름과 스코어를 보유하는 딕셔너리가 있습니다.

var scores: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]

딕셔너리는 순서를 보장하지 않고, 특정한 인덱스에 삽입할 수도 없습니다. 또한 키 Key 타입이 해시 가능 Hashable 해야 합니다. 다행히도 거의 대부분의 표준 타입은 해시가능 Hashable 하며, 최근 버전의 스위프트에서 Hashable 프로토콜을 채택하는 것은 대수롭지 않은 일이 되었습니다. 아래 구문을 이용하여 딕셔너리에 새 항목을 추가할 수 있습니다.

scores["Andrew"] = 0

딕셔너리 내에 새로운 키-값 쌍을 생성합니다.

["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1]

"Andrew"키는 딕셔너리의 어딘가에 삽입되어 있습니다. 딕셔너리는 순서가 지정되지 않으므로 새 항목이 어디에 들어가는지 보장할 수 없습니다.

Collection 프로토콜이 가능하므로, 딕셔너리의 키-값을 여러번 순회하는 것이 가능합니다. 순회의 순서는 지정되지는 않았지만, 콜렉션이 변경되기 전까지는 동일합니다.

명시적인 순서가 없다는 단점은 일부 특성[redeeming traints]이 함께 따라갑니다.

배열과 다르게 딕셔너리는 요소가 섞이는 것에 대해 걱정할 필요가 없습니다. 딕셔너리에 삽입하는 것은 항상 일정한 상수시간이 듭니다.
조회(Lookup)작업에도 똑같이 상수시간이 걸립니다.이는 배열에서 특정 요소를 찾을 때 배열의 처음부터 삽입 위치까지 가야되는 것보다 현저하게 빠릅니다.

🥑 Set

Set은 고유한 값을 가진 컨테이너입니다. 아이템을 넣을 수 있지만 이미 가지고 있는 아이템은 거부하는 가방을 떠올려보세요.

var bag: Set<String> = ["Candy", "Juice", "Gummy"]
bag.insert("Candy")
print(bag) // prints ["Candy", "Juice", "Gummy"]

Set은 고유성을 적용하므로, 콜렉션에 중복값을 찾는 등, 다양한 어플리케이션에 사용됩니다.

let values: [String] = [...]
var bag: Set<String> = []
for value in values {
  if bag.contains(value) {
    // bag already has it, therefore it is a duplicate
  }
  bag.insert(value)
}

딕셔너리나 배열처럼 세트를 자주 사용하지는 않을 것입니다. 그러나 여러분의 도구함[toolbelt]에 보관해야하는 중요한 자료구조가 될만큼 일반적입니다. 그러나 한 가지 유의사항이 있습니다. 딕셔너리와 유사하게, 세트의 값들은 순서라는 개념이 없습니다.세트를 이용하여 데이터를 모을 때 이를 유념하세요.

🥑 The Swift Collections package

스위프트 표준 라이브러리는 가장 중요한 3개의 자료구조인 Array, Set, Dictionary 만 구현합니다. 추가적인 자료구조는 스위프트 콜렉션 패키지 Swift Collections package 를 참고하세요. 이 패키지는 공식 표준 라이브러리가 되기 전의 새로운 콜렉션 타입을 커뮤니티에서 개발 및 테스트를 할 수 있습니다.

🍞 Deque

앞서 우리는 배열 Array 의 맨 앞에 요소를 삽입하는 것이 모든 요소의 이동을 야기한다고 배웠습니다.
언뜻 보기에 Deque 자료구조는 Array 와 동일한 목적으로 사용되는 것처럼 보입니다. Deque는 값을 순서대로 보관하는 범용 컨테이너로 사용할 수 있습니다. Array와 마찬가지로 append 를 호출하여 Deque 에 요소를 삽입하거나 remove(at:)을 사용하여 일부 인덱스의 특정 요소를 제거할 수 있습니다.

실제로 배열 Array 과 데크 Deque 둘 다 동일한 콜렉션 프로토콜을 구현하고 있기 때문에 인터페이스는 거의 동일합니다. 그렇다면 왜 배열 Array 보다 데크 Deque 를 사용하는 이유는 무엇일까요? 시간복잡성을 고려하기 전까지 트레이드오프 tradeoff 를 확인하긴 어렵습니다.

Deque는 double-ended queue 입니다. 그렇기때문에 Deque는 콜렉션의 앞과 뒤에서 수정이 최적화 되어있습니다. Array와 다르게 Deque 앞에서 요소를 삽입하거나 삭제하는 것은 저렴한 O(1) 로 수행됩니다.

그렇다면 단점은 무엇일까요? 프로그래밍 상의 모든 것들은 모두 트레이드오프 tradeoff 에 관한 것입니다.

Deque 의 경우, 데크의 앞부분에서 수정이 용이해진 대신, 나머지 모든 것들의 성능을 조금씩 저하시킵니다. 프로그래머로서 옵션을 평가하고 작업에 가장 적합한 도구를 고르는 것이 여러분의 일입니다. 만약 여러분이 콜렉션의 앞부분에서 자주 수정이 필요하다면 Deque가 Array 보다 훨씬 성능이 좋을 것입니다. 이는 더 나은 사용자 경험으로 치환될 수 있습니다. 이것이 바로 빠른앱과 느린 앱의 차이를 만들 수 있습니다.

스위프트 콜렉션 패키지는 OrderedDictionary , OrderedSet 와 같은 부가적인 자료구조를 가지고 있습니다. 접두어에서 보이는 바와 같이 이들은 요소의 순서를 유지하는 Dictionary 와 Set 의 변형입니다. Deque 와 같이 이런 자료구조들은 성능상의 트레이드오프를 가지고 있습니다.

이에 대해서는 https://swift.org/blog/swift-collections/ 이 링크에서 더 알아볼 수 있습니다.

👀 Key points

• 모든 자료구조는 각기 장점과 단점을 가지고 있습니다. 이를 아는 것은 좋은 성능의 소프트웨어를 작성하는데 핵심이 됩니다.
• Array 에서 insert(at:) 과 같은 메소드를 계획없이 사용하면 성능이 저하될 수 있는 성능특성이 있습니다. 배열의 앞부분과 가까운 인덱스에 insert(at:) 메소드를 자주 사용해야한다면 연결리스트 linked list 와 같은 자료구조를 고려해볼 수 있습니다.
• Dictionary는 순서를 가지는 대신 빠른 삽입과 검색을 할 수 있습니다.
• Set 는 값의 콜렉션에서 고유성을 보장합니다. Set은 속도에 최적화되어있으며 요소의 순서를 유지하는 기능은 포기하였습니다.
• 스위프트 콜렉션 패키지는 특정 시나리오에서 더 잘 수행하는 특별한 자료구조를 포함합니다.

해당 포스팅은 RaywenderLich의 ePub을 학습 후 정리한 포스팅입니다.