[Swift] Deque, OrderedSet, OrderedDictionary

안녕하세요 Hani입니다.

21년 4월 5일, 스위프트에서 사용할 수 있는 자료구조를 확장한 오픈소스 패키지인 Swift Collections가 등장했습니다.

그래서 이번엔 Swift Collections에 대하여 알아보겠습니다. 

 

 

 

기존 Swift Standard Library에는 Swift로 앱을 만드는 데 사용되는 데이터 타입, 함수, 프로토콜 등이 구현되어 있습니다.

이 라이브러리에는 기본적인 자료구조인 Array, Dictionary, Set만이 구현되어 있었습니다. 🥺

 

 

새롭게 등장한 Swift Collections는 Deque, OrderedSet, OrderedDictionary를 제공한다고 하네요. 🔥

Swift Collections를 추가하는 방법은 아래와 같습니다.

 

 

 

이제 이 패키지가 우리에게 새롭게 제공해주는 자료구조들을 하나씩 알아볼 차례입니다.

---

Deque

Deque는 배열처럼 인덱스를 활용하며, 자료의 양쪽 끝의 삽입과 삭제는 배열보다 뛰어난 성능을 보여줍니다.

또한, 배열과 같이 RangeReplaceableCollection, MutableCollection 그리고 RandomAccessCollection를 준수하여 자료를 다루는데 친숙한 인터페이스를 제공합니다.

var colors: Deque = ["red", "yellow", "blue"]

colors.prepend("green")
colors.append("orange")
// `colors` is now ["green", "red", "yellow", "blue", "orange"]

colors.popFirst() // "green"
colors.popLast() // "orange"
// `colors` is back to ["red", "yellow", "blue"]

 

배열의 경우 contiguous buffer에 데이터를 저장하여, 배열의 맨 앞에 원소를 추가하면 배열의 모든 원소를 한 칸씩 뒤로 밀어야 합니다.

따라서 배열은 O(n)의 시간이 소요되지만 Deque에서는 circular buffer에 원소를 저장하여 O(1)에 가능한 작업이 됩니다. 🥰

 

// `colors` is now ["red", "yellow", "blue"]
colors[1] // "yellow"
colors[1] = "peach"
colors.insert(contentsOf: ["violet", "pink"], at: 1)
// `colors` is now ["red", "violet", "pink", "peach", "blue"]
colors.remove(at: 2) // "pink"
// `colors` is now ["red", "violet", "peach", "blue"]
colors.sort()
// `colors` is now ["blue", "peach", "red", "violet"]

 

하지만 맨 앞이 아닌 임의의 인덱스에 대한 작업을 주로 할 때는 Deque의 도입을 조금 더 고민해봐야 합니다.

그래프 상에서 볼 수 있듯, 인덱스를 통한 접근은 Deque가 배열보다 속도가 약간 느리기 때문에

모든 것을 Deque로 바꾸는 것은 좋지 않습니다.

---

OrderedSet

OrderedSet은 Hashable Protocol을 준수하는 원소 타입을 가진 정렬된 집합을 제공해줍니다.

원소의 정렬이 중요한 집합이 요구될 때, 기존에 있던 Set의 좋은 대안이 됩니다.

 

let a: OrderedSet = [1, 2, 3, 4]
let b: OrderedSet = [4, 3, 2, 1]
a == b // false
b.sort() // `b` now has value [1, 2, 3, 4]
a == b // true
a.unordered == b.unordered // true

두 OrderedSet의 원소들이 같지만, 정렬된 순서가 다르면 두 OrderedSet은 다른 집합이 됩니다.

원소만 같은지 비교하기 위해선 unordered를 통해 비교해야 합니다.

 

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]

원소를 OrderedSet에 추가할 때, 해당 원소가 Unique 한 지 판별하고 집어넣는 과정은 O(1)의 시간 복잡도를 가집니다.

 

for i in 0 ..< buildingMaterials.count {
  print("Little piggie #\(i) built a house of \(buildingMaterials[i])")
}
// Little piggie #0 built a house of straw
// Little piggie #1 built a house of sticks
// Little piggie #2 built a house of bricks

buildingMaterials.append("straw") // (inserted: false, index: 0)
buildingMaterials.contains("glass") // false
buildingMaterials.append("glass") // (inserted: true, index: 3)
// `buildingMaterials` is now ["straw", "sticks", "bricks", "glass"]

 

특정 원소가 데이터에 있는지 찾아내는 시간은 배열은 O(n), OrderedSet은 O(1)이 소요됩니다.

---

OrderedDictionary

OrderedDictionary는 Hashable Protoco을 준수하는 원소 타입으로 정렬된 Dictionary을 제공해줍니다.

요소의 순서가 중요하거나 컬렉션 내의 다양한 위치에서 요소에 효율적으로 액세스 할 수 있어야 할 때 Dictionary의 유용한 대안이 됩니다.

 

let responses: OrderedDictionary = [ 200: "OK", 403: "Forbidden", 404: "Not Found", ]

OrderedDictionary는 Key-Value쌍을 추가하는데 O(1)이 소요됩니다. 

 

responses[200] // "OK"
responses[500] = "Internal Server Error"

OrderedDictionary는 Key에 대한 Value를 찾는데 O(1)이 소요됩니다.

 

responses[0] // nil (key-based subscript)
responses.elements[0] // (200, "OK") (index-based subscript)

if let i = responses.index(forKey: 404) {
  responses.keys[i] // 404
  responses.values[i] // "Not Found"
  responses.remove(at: i + 1) // (500, "Internal Server Error")
}
// `responses` is now [200: "OK", 403: "Forbidden", 404: "Not Found"]

OrderedDictionary는 인덱스를 통한 참조를 할 수도 있지만 키를 통한 참조와 구별되어야 합니다.

인덱스를 통한 참조를 위해서 무엇을 참조할지 Keys, Values 같은 요소를 경유해야만 합니다.

---

Reference

swift.org/blog/swift-collections/

github.com/apple/swift-collections