[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터3. 스위프트 표준 라이브러리 Swift Standard Library

Raywenderlich.com 에서 나온 Data Structures & Algorithms in Swift 책의 데모 공개본을 번역하였습니다. 즐겁게 봐주세요. 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift

 

---

 

섹션 1. 소개 Introduction

챕터3. 스위프트 표준 라이브러리 Swift Standard Library

스위프트 표준 라이브러리는 스위프트 언어의 핵심 구성요소를 포함하는 프레임워크입니다. 이 안에는 스위프트 앱을 구축하는데 도움이 되는 다양한 툴과 타입이 있습니다. 사용자 정의 자료구조(your own custom data structure)를 구축하기 전에, 스위프트 표준 라이브러리가 이미 제공하는 기본 자료 구조를 이해하는 것이 중요합니다.

 

이번 챕터에서는 표준 라이브러리가 제공하는 세가지 주요 데이터 구조인 Array, Dictionary, Set 에 중점을 둘 것입니다.

 

---

 

배열Array

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

 

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

스위프트는 프로토콜을 이용하여 배열을 정의합니다. 이 각 프로토콜은 배열에 더 많은 기능을 부여합니다. 예를 들어 배열Array 은 시퀀스Sequence 입니다. 이 말은 한번 이상 반복할 수 있다는 뜻입니다. 또한 배열은 콜렉션Collection 입니다. 이 뜻은 비파괴적으로(nondestructively) 여러번 순회할 수 있고, 첨자 연산자(subscript oerator)를 이용하여 접근할 수 있습니다. 배열은 또한 효율성을 보장하는 RandomAccessCollection 이기도 합니다.

 

스위프트의 배열Array은 제네릭 컬렉션generic collection 으로도 알려져 있습니다. 어떤 타입에서도 작동할 수 있기 때문입니다. 실제로 대부분의 스위프트 표준 라이브러리는 제네릭 코드로 구축되어 있습니다.

 

모든 자료구조와 마찬가지로 여러분이 알아야 하는 특성이 있습니다. 첫번째는 바로 순서order 의 개념입니다.

 

순서 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

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

 

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

 

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

 

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 (”deck”덱으로 발음됩니다) 자료구조는 배열 Array 과 동일한 목적으로 사용되는 것처럼 보입니다. 데크는 값을 순서대로 보관하는 범용 컨테이너로 사용할 수 있습니다. 배열 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 는 속도에 최적화되어있으며 요소의 순서를 유지하는 기능은 포기하였습니다.
• 스위프트 콜렉션 패키지는 특정 시나리오에서 더 잘 수행하는 특별한 자료구조를 포함합니다.

 

---

🔗 번역 시리즈 링크

0️⃣ 섹션 0. 시작하기전에

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 0. 시작하기 전에

1️⃣ 섹션 1. 소개 Introduction

> 챕터 1.왜 자료구조와 알고리즘을 배워야할까요? / 챕터 2. 복잡도  Complexity

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터1. 왜 자료구조와 알고리즘을

> 챕터3. 스위프트 표준 라이브러리 Swift Standard Library

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터3. 스위프트 표준 라이브러리 S

 

1️⃣ 섹션 2. 기초 자료구조 Elementary Data Structure

> 챕터 4. 스택 Stacks /  챕터 5. 스택 도전과제 Stack Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전

> 챕터 6-1. 연결리스트 Linked List (연결리스트 정의, 요소 추가, 삭제)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-1. 연결리스트 (정

> 챕터 6-2. 연결리스트 Linked List (스위프트 표준 라이브러리의 콜렉션 프로토콜, 카우 Copy-On-Write,  밸류 시맨틱)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-2. 연결리스트

 

> 챕터 7. 연결리스트 도전과제 Linked List Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터7. 연결리스트 도전

 

---

마치며 

 

오늘도 읽어주셔서 감사합니다.

 

궁금한 점이 있다면 댓글로, 도움이 되셨다면 공감 부탁드립니다.

혹시 수정하거나 피드백하실  내용 있다면 언제든 댓글로 부탁드립니다.

 

감사합니다.