Introducing Swift Collections

 

안녕하세요 :) Zedd입니다.

오늘은..얼마전 나온 Swift Collections에 대해서 간단히 공부해보려고 합니다!

 

# Swift Collections

- Swift Algorithms, Swift Numerics 패키지와 같은 오픈소스 패키지

- Swift Standard library에는 가장 필수적인 범용 데이터 구조인 Array, Set, Dictionary를 구현하고 있음. 

➞ 하지만 때때로 더 큰 데이터 구조 라이브러리의 이점을 가져가고 싶을 때, Collections 패키지를 사용하면 된다.

 

# 사용법

1. 프로젝트 준비 

나는 그냥 Command line tool만듬

2. 패키지 추가 

왼쪽 아래 + 버튼 눌러서 github.com/apple/swift-collections URL입력해주고 

다 체크 

 

Swift Collections에는 3가지 데이터 구조에 대한 구현이 포함되어있음.

1. double-ended queue (= deque)

2. ordered set

3. ordered dictionary

 

# Deque

💡 Deque는 DequeModule import가 필요함. 

import DequeModule

- 순간 "디큐"라고 읽는 줄 알았지만, "덱"이라고 발음하는게 맞음. (Deque (pronounced “deck”))

- Array와 유사하게 동작하지만, Deque는 양쪽 끝에서 효율적인 삽입 및 삭제를 지원함. 

➞ 즉, first-in-first-out queue가 필요할 때 deque를 사용하는 것이 좋음. 

 

Deque가 양쪽 끝에서 효율적인 삽입 및 삭제를 지원한다고 했으니..관련 메소드가 있을 것.

[삽입]

prepend : 앞쪽에 삽입

append : 끝에 삽입 

[삭제]

popFirst : 가장 앞 요소 삭제

popLast : 끝 요소 삭제

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"]

prepend에 대한 시간 복잡도 그래프.

Array의 prepend라 하면 0번째 위치에 insert하는 것일텐데, 이 insert 작업은 

insert하고 싶은 위치 뒤에 있는 요소들이 한칸씩 밀려야 하기 때문에 최악의 경우 배열 전체 개수 n개 만큼의 시간이 걸릴 수 있음.

그러므로 O(n)이 나온다. (특정 index요소 삭제도 O(n)이 걸릴 수 있음. 반대로 한칸씩 땡겨와야하니까) 

하지만 deque의 prepend의 경우 O(1)이 나온다는 것!

Array와 비슷하게 동작한다고 했으니 

var colors: Deque = ["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"]

이런것들도 가능.

🙋: 배열이랑 비슷하고, 거기에 prepend, popFirst 이런것도 O(1)이면 무조건 deque쓰는게 개이득아님?;;;

🧑‍💻: 효율적인 삽입/삭제를 위해 deque는 인접한 buffer에서 요소를 유지하는 것을 포기하고 있다고 함.
이로 인해 front에 삽입/삭제를 하지 않는 일반적인 경우 Array보다 약간 느리게 동작하므로 모든 Array를 Deque로 무조건 대체하는 것은 안좋다는 거..

실제로 일반적인 경우(바로 위 코드스니펫같은) Deque가 Array보다 살짝 느린 것을 볼 수 있음. 

 

[참고로 보면 좋은 사항]

Swift and Tips on Twitter

어떤분이 Standard library에 있는 Array와 Swift Collections에 있는 deque를 가지고 Queue를 만들어봤는데, 

Deque (from new Collection): 0.045 secs

Array (from standard library): 4.373 secs

엄청난 성능차이를 보였다고..

 

이러한 시간차이는 pop연산에서 나는것으로 추측된다. 

 

# OrderedSet

💡 OrderedSet은 OrderedCollections import가 필요함

import OrderedCollections

- Array + Set 하이브리드

- Hashable을 준수하는 모든 element type으로 ordered set을 만들 수 있음

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

unique인지 확인하는 것을 포함하여 element를 추가하는 것은 O(1)이 걸린다. 

 

OrderedSet은  Array + Set 하이브리드이므로

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

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

요소를 사용자가 지정한 순서로 유지함. (Set과 달리 순서대로 나온다는 뜻)

let buildingMaterials: OrderedSet = ["straw", "sticks", "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"]

거기에 각 요소가 한번만 표시되도록 함. 

straw는 이미 존재하므로 append가 소용이 없고, glass는 없었으니 추가된 것을 볼 수 있음. 

Membership testing : collection에 특정 element가 포함되어있는지 확인하는 것을 의미. 위 코드스니펫에서는 contains가 되는 것.

OrderedSet의 경우 Membership testing에서는 O(1)이지만, Array에서는 O(n)임

OrderedSet은 standard array value를 사용한다. 따라서

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

func buildHouses(_ houses: Array<String>)

buildHouses(buildingMaterials) // error
buildHouses(buildingMaterials.elements) // OK

Array를 요구할 경우 OrderedSet의 elements 프로퍼티를 이용.

 

SetAlgebra 준수가 필요한 경우, unordered 프로퍼티를 통해 정렬되지 않은 요소들을 제공.

func blowHousesDown<S: SetAlgebra>(_ houses: S) { ... }

blowHousesDown(buildingMaterials) // error: `OrderedSet<String>` does not conform to `SetAlgebra`
blowHousesDown(buildingMaterials.unordered) // OK

 

# OrderedDictionary

💡 OrderedDictionary는 OrderedCollections import가 필요함

import OrderedCollections

- Hashable을 준수하는 Key Type으로 정렬된 Dictionary를 만들 수 있음. 

- OrderedDictionary는 다음 사항에 해당할 때 Dictionary의 유용한 대안이 될 수 있음.

1. element의 순서가 중요할 때

2. collection내의 다양한 위치에서 element에 효율적으로 접근해야할 때

 

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

OrderedDictionary에  key-value쌍을 insert하면 O(1)에 추가됨. 

OrderedDictionary는 Dictionary와 유사하고, 동일한 작업을 많이 제공. 

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

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

이런거 똑같이 가능. 이 작업도 역시나 O(1)

 

subscript setter를 사용하여 새 element를 추가하면 Dictionary끝에 추가됨.

기본적으로 Dictionary에는 삽입된 순서대로 element가 포함됨. 

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

responses[500] = "Internal Server Error"

for (code, phrase) in responses {
  print("\(code) (\(phrase))")
}
// 200 (OK)
// 403 (Forbidden)
// 404 (Not Found)
// 500 (Internal Server Error)

OrderedDictionary는 첫번째 element가 항상 0에서 시작하는 integer index를 사용.

key기반 및 index기반 subscripts간의 모호성을 피하기 위해 OrderedDictionary는 Collection을 직접 준수하지 않음.

대신 key-value pair에 대한 random access를 제공. 

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

표준 Dictionary와 마찬가지로 OrderedDictionary는 간단한 key 및 value 보기도 제공. 

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

responses[500] = "Internal Server Error"

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"]

 

끝! 안옮긴 내용도 있으니 자세한 사항은 아래 링크 참고. 

 

OrderedSet, OrderedDictionary는 PS할 때 진짜 간절한 것들인데...ㅎㅎㅎ Standard로 들어왔으면 좋겠네요..!!

참고로..글에 나와있는 모든 그래프는 log-log scale로 element당 평균 처리 시간을 표시했다고 합니다. 

Note: All graphs plot the average per-element processing time on a log-log scale. Lower is better.
The benchmarks were run on my 2017 iMac Pro.

문서에는 상수시간(constant time) , 선형시간(linear time) 이렇게 언급하는데, 

저는 상수시간 ➞ O(1), 선형시간 ➞ O(n) 이렇게 적었어요~ 참고 부탁드립니다.

 

틀린 부분이 있다면 댓글로 알려주세요!

 

참고

swift.org/blog/swift-collections/

github.com/apple/swift-collections