Collection Data Structures Swift - KR

Collection Data 스위프트 구조를 소개합니다.좋은 글이라 생각되어 번역합니다. 핵심적인 부분을 제외하고는 번역을 제외하고 의역했습니다. 본문은 여기를 참고해주세요.

Introduction

많은 데이터를 처리하는 어플리케이션을 만들고 있을 때를 생각해보세요. 언제 데이터를 넣고 어떻게 그 많은 데이터를 효율적으로 핸들링을 하실 건가요? 많은 데이터를 처리 할 경우에는 Array, Dictionary, Sets 에 대한 근본적인 개념을 알고 있는게 중요합니다. 이 collection data structures 에 명확한 개념을 가질 경우 처리 속도는 어마어마하게 빨라 질 것 입니다.

튜토리얼의 순서는 다음과 같습니다.

데이터 구조에 대해 개념을 가지고, Big-O표기법에 대해 배워봅니다.
여러가지 자료 구조들에 대해 숙지합니다.
데이터 구조들의 퍼포먼스를 비교해봅니다.
추가의 팁으로 다른 구조들을 조금 더 알아봅니다.

What is `Big-O` Notation?

컴퓨터에서 데이터를 처리할 때 걸리는 * 시간 * 또는 차지하는 * 메모리 공간 * 은 일반적으로 * 데이터의 양 * 에 비례하게 됩니다. Big-O 표기법은 이 때 필요한 시간, 공간을 * 점근적으로(asymptotically) * 표현하는 방법이며, 이렇게 표현한 것을 시간복잡도(time complexity), 공간복잡도(space complexity)라고 부릅니다.

아래는 자주 만날 수 있는 시간복잡도의 Big-O 표기법과 설명을 빠른 것부터 나열한 것입니다.

O(1): 제일 이상적입니다. 처리하는 데이터의 양(n)에 관계 없이 상수 시간만큼 소요되는 경우입니다.
O(log n): 좋은 퍼포먼스를 보여주는 그래프입니다. 데이터 구조에 있는 아이템이 늘어나도 매우 천천히 연산의 횟수가 늘어나게(=걸리는 시간도) 됩니다.
O(n): 중간 단계의 퍼포먼스를 보여주는 그래프입니다. 데이터 구조랑 연산횟수가 일차함수(linear)를 그리며 증가합니다.
O(n (log n)): (데이터가 10M~100M 넘어갈 경우) 낮은 단계의 퍼포먼스를 보여주는 그래프입니다. 비교 기반 정렬(comparison based sort)의 시간복잡도 하한(lower bound)이기도 합니다.
O(n²) : 데이터구조에 있는 아이템수의 제곱에 비례하여 늘어납니다. 여기서 부턴 성능이 매우 떨어지고, 추천하지 않습니다.
O(2^n): 2의 데이터 구조의 갯수 제곱만큼 증가합니다. 매우 나쁜 퍼포먼스를 보여줍니다. 원소 n개 집합의 모든 부분집합을 출력하는 경우의 시간복잡도와 같습니다.
O(n!): 최악의 케이스입니다. 이렇게 코딩이 될 경우에는 답이 없습니다.

Common iOS Data Structures

Arrays, Dictionaries, Sets 가 가장 흔한 데이터 구조입니다. 각각의 구조와 성능에 대해 알아봅니다. 또한 Objective-C와Swift에서 각각의 데이터구조를 비교해봅니다.

Arrays

Array는 순서를 가지고 있는 배열입니다. index를 통해서 각각의 아이템에 접근 할 수 있습니다. 인덱스를 가지고 아이템을 가져오는 것을 subscripting이라고 합니다.
Objective-C의 NSArray는 Swift에서 let으로 선언된 Array와 같습니다. NSMutableArray는 var로 선언된 Array와 같습니다.
최악의 케이스는 O(log n)이 실행되지만 보통 O(1)이 연산됩니다.
모르는 오브젝트를 찾을 경우 최악은 O(n (log n))이 실행되지만 보통 O(n)만큼 연산됩니다.
데이터를 삭제하거나 넣는 경우 최악은 O(n (log n))이 걸리지만 보통 O(1)만큼 실행됩니다.

이럴때 쓰면 좋습니다.

item이 어디있는지 아는 경우 동작은 빠르게 작동 할 것입니다.
아이템이 어디있는지 모를 경우 처음부터 끝까지 동작해야하기 때문에 검색결과가 느립니다.
아이템을 어디에 넣고 삭제해야 하는지 알고 있다면 어렵지 않겠지만, 배열을 앞뒤로 살펴야 한다는 것은 시간 소비가 큽니다.

Swift는 2015년 12월부터 오픈소스입니다. Swift Code로 들어가셔서 구조가 어떻게 되어있는 지 확인해보시는 것도 좋은 방법입니다.

아래는 Objective-C와 Swift의 비교 결과입니다.

Creating a Swift Array and an NSArray degrade at roughly the same rate between O(log n) and O(n). Swift is faster than Foundation by roughly 30 times. This is a significant improvement over Swift 2.3, where it was roughly the same as Foundation!
Adding items to the beginning of an array is considerably slower in a Swift Array than in an NSArray, which is around O(1). Adding items to the middle of an array takes half the time in Swift Array than in an NSArray. Adding items to the end of a Swift Array, which is less than O(1), is roughly 6 times faster than adding items to the end of an NSArray, which comes in just over O(1).
Removing objects is faster in a Swift Array than a NSArray. From the beginning, middle or end, removing an object degrades between O(log n) and O(n). Raw time is better in Swift when you remove from the beginning of an Array, but the distinction is a matter of milliseconds.
Looking up items in Swift is faster for the first time since its inception. Look ups by index grow at very close rates for both Swift Arrays and NSArray while lookup by object is roughly 80 times faster in Swift.

상기 글은 스위프트가 얼마나 잘 최적화 되었는지 보여줍니다. Swift쓰세요. 두번 쓰세요.

Dictionaries

Dictionary(사전)는 특정 순서와 상관없이 key값을 통해서 값을 찾을 수 있는 데이터 구조입니다.
Dictionary는 subscripting을 지원하기 떄문에, dictionary["hello"] 와 같은 방법으로 hello라는 key값을 통해서 값에 접근 할 수 있습니다.
NSDictionary와 NSMutableDictionary의 차이는 Array일 경우와 같습니다.
Swift의 Dictionary는 타입을 지정해줘야 합니다. (NSDictionary가 NSObject를 갖는 것 처럼)

이럴때 쓰면 좋습니다.

순서가 없을 경우 Dictionary를 사용하시면 됩니다.
순서가 아닌 key값으로 접근 할 경우 좋습니다. cats["Ellen"]이렇게 사용할 경우 Optional이 return되기 때문에 if let 이나 guard로 풀어주는 것을 권장합니다.

if let ellensCat = cats["Ellen"] {
    print("Ellen's cat is named \(ellensCat).")
} else {
    print("Ellen's cat's name not found!")
}

아래는 Objective-C와 Swift의 비교 결과입니다.

In raw time, creating Swift Dictionaries is roughly 6 times faster than creating NSMutableDictionaries but both degrade at roughly the same O(n) rate.
Adding items to Swift Dictionaries is roughly 100 times faster than adding them to NSMutableDictionaries in raw time, and both degrade close to the best-case-scenario O(1) rate promised by Apple’s documentation.
Removing items from Swift Dictionaries is roughly 8 times faster than removing items from NSMutableDictionaries, but the degradation of performance is again close to O(1) for both types.
Swift is also faster at lookup, with both performing roughly at an O(1) rate. This version of Swift is the first where it beats Foundation by a significant amount.

퍼포먼스가 크게 차이가 나지 않는다고 합니다.

Sets

Set(집합)은 순서가 없고 유일한 값을 저장하는 데이터 구조입니다. 중복으로 데이터를 등록 할 수 없습니다.
Set에 선언되어있는 값들은 모두 같은 type 이어야 합니다.
Objective-c 에서는 각각 NSSet과 NSMutableSet이 있습니다.

이럴때 쓰면 좋습니다.

Set은 유니크한 값을 중복없이 뽑을 경우 좋습니다.
Snippet을 하나 보겠습니다.

let names = ["John", "Paul", "George", "Ringo", "Mick", "Keith", "Charlie", "Ronnie"]
var stringSet = Set<String>() // 1
var loopsCount = 0
while stringSet.count < 4 {
    let randomNumber = arc4random_uniform(UInt32(names.count)) // 2
    let randomName = names[Int(randomNumber)] // 3
    print(randomName) // 4
    stringSet.insert(randomName) // 5
    loopsCount += 1 // 6
}
// 7
print("Loops: " + loopsCount.description + ", Set contents: " + stringSet.description)

Set을 초기화 합니다.
아이템를 랜덤으로 뽑습니다
인덱스에 있는 아이를 가져옵니다
로그를 남깁니다
mutable set에 값을 저장합니다. 만약 값이 저장되어 있는 경우에는 값을 저장하지 않습니다.
루프 카우트를 늘려서 루프를 다 돌게 합니다
루프가 끝나면 값을 로그에 남깁니다

John
Ringo
John
Ronnie
Ronnie
George
Loops: 6, Set contents: ["Ronnie", "John", "Ringo", "George"]

로그에는 6개의 값이 찍혔지만 결론적으로 Set에는 4개의 값이 들어가 있습니다.

덜 알려졌지만 있는 데이터 구조들

NSCache

NSCache를 사용하는 것은 NSMutableDictionary를 사용하는것과 매우 유사합니다.
다른 점은 메모리가 낮아질 경우 NSCache데이터는 지워 질 수 있습니다. 그리고 항상 재생성됩니다.

캐시는 화면뒤에서 비동기적으로 자동으로 메모리에 상주 할 지, 남을지 결정합니다.

NSCountedSet

NSMutableSet을 상속받아서 만들어진 데이터 구조로, 얼마나 많은 오브젝트가 mutable set에 더해해졌는지 알 수 있게 해줍니다.
하단 코드를 참고해주세요

let countedMutable = NSCountedSet()
for name in names {
    countedMutable.add(name)
    countedMutable.add(name)
}

let ringos = countedMutable.count(for: "Ringo")
print("Counted Mutable set: \(countedMutable)) with count for Ringo: \(ringos)")

Counted Mutable set: {(
    George,
    John,
    Ronnie,
    Mick,
    Keith,
    Charlie,
    Paul,
    Ringo
)}) with count for Ringo: 2

NSOrderedSet

NSOrderedSet은 개별적인 오브젝트들의 그룹을 순서대로 저장 할 수있게 해줍니다.

ordered set을 Array의 대안으로 테스팅할 때 사용해보시면 배열보다 더 빠른것을 느낄 수 있습니다.

NSHashTable and NSMapTable

NSHashTable은 NSMutableSet과 비슷하지만 몇가지 다른점이 있습니다
NSHashTable은 오브젝트 뿐만 아니라 non-object또한 더할 수 있습니다. NSHashTableOptions로 메모리 또한 관리 할 수 있습니다.
NSMapTable은 dictionary 같은 자료구조이지만, NSHashTable과 비슷하게 메모리를 관리한다는 측면이 있습니다.

Author

younatics 🇰🇷

KimDarren/Collection-Data-Structures-Swift-KR

Collection Data Structures Swift - KR

Introduction

튜토리얼의 순서는 다음과 같습니다.

What is Big-O Notation?

Common iOS Data Structures

Arrays

이럴때 쓰면 좋습니다.

Dictionaries

이럴때 쓰면 좋습니다.

Sets

이럴때 쓰면 좋습니다.

덜 알려졌지만 있는 데이터 구조들

NSCache

NSCountedSet

NSOrderedSet

NSHashTable and NSMapTable

Author

What is `Big-O` Notation?