Section I: Swift Standard Library(Array, Dictionary, Set)

Swift 표준 라이브러리가 제공하는 기본 데이터구조를 이해해보기

이 장에서는 세 가지 주요 데이터 구조인 Array, Dictionary 및 Set에 중점을 둘 것입니다.

 

1. Array

배열은 각 요소가 순서를 가지고 있는 데이터 모음 즉 요소 컬렉션을 저장하기 위한 컨테이너라고 합니다.

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

이런식으로 배열을 만들 수 있습니다.

 

배열은  Sequence, Collection 프로토콜을 준수하여 정의 되어 있습니다.

그러므로 시퀀스 프로토콜에 의해 적어도 한번은 iterate 할 수 있고,  콜렉션 프로토콜에 의해 비파괴적??으로 여러 번 탐색할 수 있으며,

subscript operator를 사용하여 액세스 할 수 있습니다. 그리고 또한 배열은 효율성을 보장하는 RandomAccessCollection  이기도 하고 제네릭(당연히 여러 타입을 배열로 만들 수 있으니)입니다.

 

* subscript operator 란 콜렉션, 리스트, 스퀀스 등 집합의 특정 element 에게 간단하게 접근 할 수 있는 문법

Ex.) array[index]로 배열의 인스턴스 항목과 dictionary[key]로 딕셔너리 인스턴스 항목에 접근하는 것

펌) https://medium.com/@jgj455/%EC%98%A4%EB%8A%98%EC%9D%98-swift-%EC%83%81%EC%8B%9D-subscript-2288551588f9

 

* randomAccessCollection 은 프로콜이며, 어느 위치에 있던 임의의 인덱스 접근을 할 때 시간복잡도가 데이터 양과 상관없이 일정한 것

 

 

 

!!!!!!!!!!!!!!STOP!!!!!!!!!!!!!!

위에서 계속 여러 프로토콜을 언급했는데 결론은 Array는 여러 프로토콜을 준수하여 만들어 진 데이터구조이다. 정도로 이해하고 넘어가자.. 모두 하나하나 다 이해하고 넘어가다 보면 끝을 못본다..

 

!!!!!!!!!!!!!!START!!!!!!!!!!!!!

 

 

 

모든 데이터 구조와 마찬가지로 사용자가 알고 있어야 하는 특정 특징이 있다. 그 중 첫 번째는 Order(순서)의 개념입니다.

 

배열은 0부터 시작하는 인덱스 값으로 순서를 매깁니다.

배열의 순서를 가지는 것에 대해서 당연하게 생각하지 마세요.

딕셔너리 같은 데이터 구조는 순서의 개념이 약합니다.

 

 

    Random-access

위에도 적었지만, 어느 위치에 있던 임의의 인덱스 접근을 할 때 시간복잡도가 데이터 양과 상관없이 일정한 것. Constant amount of time 의 시간 복잡도를 갖는것을 의미 하며, 이것 또한 당연하게 생각하지 말세요.

linked list, tree 같은 데이터구조는 constant time 의 시간 복잡도를 가지고 있지 않습니다.

 

Array performance

Insertion location

배열을 추가할 때 어느 배열 위치에 추가하는지 따라 소요되는 시간이 달라집니다.

가장 빠른 시나리오는 배열 가장 끝에 Element를 할 때 입니다.

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

배열 가장 끝에 추가하는 append 작업은 배열 크기와 상관없이 일정한 시간이 걸립니다.

그러나 배열의 가운데 또는 특정 위치에 추가해야 하는 경우가 있습니다.

 

직관적으로 어느 놀이동산에서 사람들이 표를 구매하기 위해서 줄을 서있습니다.

맨 끝에 사람이 줄을 섰을 경우에는 앞사람이 전혀 영향을 받지 않습니다.

하지만 중간에 섰을 때는 그 중간에서 뒷사람들은 한번씩 움직여야 할것입니다.

최악의 시나리오는 맨앞에 서려고 할테고 그게 바로 모든 사람들이 움직여야하는 경우입니다.

 

이것이 바로 배열이 작동하는 방식입니다.

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

insert 속도를 결정하는 또 하나의 요소는 배열의 총 용량입니다.

배열은 이미 처음 결정된 공간에 할당되어 있습니다.

하지만 그 용량이 insert로 달라지게 된다면 배열 자체를 재구성해야 합니다. 

그러면 메모리에 더 큰 메모리 공간을 확보하여 현재 모든 요소를 복사하여 수행됩니다.

배열의 각 요소를 방문하여 복사해야 합니다.

 

이 의미는 끝에 추가하던지 중간에 하던지 배열의 총 용량 n 단계 만큼 복사를 하는데 시간이 소요됩니다.

 

 

그러면 앞에서 이론적으로 append 가 insert보다 소요 시간이 적다고는 했지만 결국 모든 요소를 복사해서 새로운 메모리에 할당해야 하므로 똑같은거 아닌가요??;; 최악의 시나리오를 설명한 이유가 없지않나..싶은데..ㅠㅠㅠ 

/// Adds a new element at the end of the array.
    ///
    /// Use this method to append a single element to the end of a mutable array.
    ///
    ///     var numbers = [1, 2, 3, 4, 5]
    ///     numbers.append(100)
    ///     print(numbers)
    ///     // Prints "[1, 2, 3, 4, 5, 100]"
    ///
    /// Because arrays increase their allocated capacity using an exponential
    /// strategy, appending a single element to an array is an O(1) operation
    /// when averaged over many calls to the `append(_:)` method. When an array
    /// has additional capacity and is not sharing its storage with another
    /// instance, appending an element is O(1). When an array needs to
    /// reallocate storage before appending or its storage is shared with
    /// another copy, appending is O(*n*), where *n* is the length of the array.
    ///
    /// - Parameter newElement: The element to append to the array.
    ///
    /// - Complexity: O(1) on average, over many calls to `append(_:)` on the
    ///   same array.

애플 배열 append 주석을 보면 append 는 시간복잡도가 O(1) 이고, insert는 O(n) n은 배열 길이라고 합니다.

append일 때는 배열의 용량을 늘릴 때 exponential  strategy 전략을 사용하기 때문에.. O(1)이 된다라고 되어있네요..

exponential  strategy 구글링 해봤지만.. 잘 모르겠어서 그냥 이정도만 이해하고 넘어가려고 합니다..

결론은 append일 때는 용량만 늘려서 가능하고, insert일 때는 모든 배열 데이터들이 새로운 메모리 스토리지로 옮겨지는 작업이 수행 된다. 정도네요.

 

Dictionary

사전은 키-값 쌍을 보유하는 일반적인 컬렉션 데이터 구조입니다.

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

사전은 순서(Order)의 개념이 없습니다.

insert 할 때 constant time 이 걸립니다.  조회작업 또한 마찬 가지입니다.

 

 

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)
}

집합 또한 순서의 개념은 없습니다.

 

 

Deque

배열와 똑같은 기능을 갖습니다. 하지만 insert delete 데이터의 수정에 대해서  O(1)의 시간 복잡도를 갖습니다.

하지만 그 외에 기능에 대해서 배열보다는 약간씩 떨어집니다.

만약 데이터의 수정이 잦은 작업이라면 배열보다는 Deque을 사용하는 것이 더 효율적입니다.

 

* 또한 Swift Collections 패키지에 OrderedDictionary, OrderedSet 과 같은 추가 데이터 구조가 입니다. 말 그대로 순서를 제공하는 사전과 집합니다. 이러한 다양한 데이터구조 및 성능은 https://www.swift.org/blog/swift-collections/ 여기에서 살펴 볼 수 있습니다.

 

 

 

 

흥미진진 하네요. ㅋㅋ 아무 생각없이 썻던 데이터 구조가 이런 특징을 가지고 있다니, 또 내가 모르던 데이터 구조까지 다양하게 알게됐습니다.