[iOS] Sequence & Collection프로토콜을 자세히 알아보자

안녕하세요

 

 

'Swift컬렉션' 이라는 키워드에서 우리는 보통 Array, Dictionary, Set같은 자료형을 떠올립니다.

 

 

해당 자료구조들은 내부적으로 Collection프로토콜을 활용하여 만들어진 자료구조입니다.

 

 

그리고 Collection프로토콜은 Sequence프로토콜을 내부적으로 채택하고 있습니다.

 

 

이번 포스팅은 두 프로토콜에 대해 깊게 알아보며 알게된 점을 정리해보려고 합니다.

 

 

가장 상위 개념인 시퀸스 프로토콜부터 시작해 보겠습니다.

 

Sequnece프로토콜

해당 프로토콜의 공식 정의는 다음과 같습니다.

순차적으로 하나씩 요소들에 접근하는 것을 가능하게 하는 타입 😅(말이 어렵내요)

 

Sequence프로토콜의 경우 요소들의 순차적인 접근을 보장합니다.

 

시퀸스 프로토콜을 따르는 타입은 for-in 문을 사용하여 시퀸스 타입의 요소들을 순회할 수 있습니다.

 

하지만 시퀸스 프로토콜이 제공하는 것은 딱 거기까지입니다.

 

"요소를 순회할 수 있다."

 

아래 코드의 결과를 예측해봅시다.

 

for문은 항상 처음부터 모든 요소를 순회한다는 고정관념 때문이라도 두 반복문은 동일한 결과를 낼 것 같습니다.

for item in items { print(item) }

for item in items { print(item) }

 

하지만, 정답은 알 수 없다입니다.

 

시퀸스의 경우 요소들 사이의 순서를 보장하지 않습니다.

 

다시 말하자면 순서라는 개념이 없습니다.

 

단지 순차적으로 요소들에게 접근할 뿐입니다.

 

이 부분을 잘 이해하기 위해 Sequence프로토콜 타입을 직접 구현해 보겠습니다.

 

Sequence프로토콜의 요구사항은 makeIterator라는 함수입니다.

 

직접 이터레이터를 만들어 반환해주었습니다.

struct MySequence: Sequence {
    func makeIterator() -> some IteratorProtocol {
        MyIterator()
    }
}

struct MyIterator: IteratorProtocol {
    typealias Element = Int
    
    mutating func next() -> Int? {
        (0..<5).randomElement()
    }
}

 

이제 해당 시퀸스를 순회해 보겠습니다.

순회

무한 반복 실행되는 것을 알 수 있습니다.

 

결과를 통해 알 수 있는 것은

 

시퀸스는 단순히 값을 받으려는 수신자에게 다음 요소를 전달할 뿐입니다.

 

요소들 사이에는 어떠한 관계가 없으며, 요소의 수에도 제한이 없어 for문을 종료하지 못할 수 있습니다.

 

for-in문은 컴파일러에 의해 아래와 같이 변경됩니다.

var iterator = items.makeIterator()

while let item = iterator.next() {
    print(item)
}

 

단순히 이터레이터로 부터 전달된 값이 nil이 아니라면 무한정 반복하는 while문입니다.

 

for-in문은 처음부터 요소를 반복하는 반복문이 아니라, 이터레이터에게 전달받은 값으로 코드 블록을 실행 실행할 뿐입니다.

 

의도적으로 반환되는 요소의 수에 제한을 둬보겠습니다.

 

※ 동일한 이터레이터 인스턴스를 모든 반복문에서 공유시키기 위해 조금 억지스럽지만 이터레이터를 참조타입으로 생성했습니다.

struct MySequence: Sequence {
    let iterator = MyIterator()
    func makeIterator() -> MyIterator { iterator }
}

class MyIterator: IteratorProtocol {
    typealias Element = Int
    
    private var list: [Int] = [1,2,3,4,5]
    private var currentIndex = 0
    
    func next() -> Int? {
        if currentIndex >= list.count {
            return nil
        }
        defer { currentIndex+=1 }
        return list[currentIndex]
    }
}

 

이제 이것을 시퀸스로 전달 후 다음과 같이 for-in문을 동작시켜보겠습니다.

 

let items = MySequence()

for item in items {
    print(item)
    if item == 3 { break } // 1 2 3
}

for item in items {
    print(item) // 4 5
}

 

for문에 의해 이터레이터의 값 전달이 잠시 끊어졌다 재개 됬을 뿐이라는 것을 알 수 있습니다.

 

물론 매 반복마다 새로운 이터레이터 인스턴스를 반환하여 처음부터 순회를 시작할 수도 있습니다.

 

하지만 중요한 점은 프로토콜이 그것을 강제하지 않는다는 것입니다.

 

이터레이터 개념

iterator는 흔히 반복하다라는 뜻에서 파생되어 반복자라고 알려져있습니다.

 

하지만 프로그래밍 관점에서 iterate은 한번에 하나의 요소에 접근하는 것을 의미합니다.

 

즉, 이터레이터는 한번에 하나씩 요소를 외부로 전달해주는 객체입니다.

 

Collection 프로토콜

컬렉션 프로토콜은 스퀸스 프로토콜을 채택하는 하위 프로토콜입니다.

 

시퀸스 프로토콜의 이점을 모두 가지면서 새로운 개념을 탑재하고 있습니다.

• 요소들은 관계를 가집니다.
• 요소들은 수는 유한합니다.
• 순회없이 특정 요소에 접근할 수 있습니다.

컬렉션 프로토콜은 요소들 간의 관계인 순서를 각인(Index)을 통해 표현합니다.

 

그리고 컬렉션은 시퀸스와 달리 요소들의 유한성을 보장합니다.

 

앞서 시퀸스는 요소의수가 무한정 늘어날 수 있음을 보여줍니다.

 

하지만 컬렉션은 유한성과 요소들간의 관계를 강제함으로 for-in문을 사용한 순회에 있어 다음을 보장합니다.

 for-in문을 통해 요소를 순회할 때 첫 요소부터 시작해 마지막 요소가지 순차적으로 순회할 것을 보장한다.

※ 요소간의 순서가 있기에 '첫 요소' 라는 개념이 존재합니다.

 

Collection프로토콜 채택

컬렉션 프로토콜은 다음을 요구합니다.

 

제네릭 Index타입, startIndex, endIndex, index(after:), 그리고 색인을 통해 특정 요소를 접근할 수 있는 서브스크립트를 요구합니다.

 

정리하자면 컬렉션의 경우 다음과 같은 동작이 가능합니다.

 

요소의 순서를 알고 있다면 최초 인덱스(startIndex)로부터 index(after)과 같은 함수를 통해 특정 순서에 있는 요소의 색인을 획득할 수 있다.

 

그리고 그 색인을 서브스크립트로 전달하여 요소값을 획득할 수 있다.

 

즉, 컬렉션 프로토콜은 시퀸스의 무순서성, 무한성으로 인한 비일관된 순회 문제를 해결한 프로토콜입니다.

 

랜덤 엑세스 컬렉션

랜덤 엑서스 컬렉션이란 컬렉셔의 특정 순서의 요소에 접근할 때 그 시간 복잡도가 O(1)임을 보장하는 컬렉션입니다.

 

우선 컬렉션으로 부터 특정 요소를 획득하기 위해선 아래 과정이 필요합니다.

 

※ 색인을 통해 요소에 접근하는 과정은 컬렉션에서 O(1)을 강제하지는 않지만 클라이언트는 이를 기대함으로 국룰이라고 생각하면 됩니다.

 

즉 랜덤 엑세스의 조건을 충족하려면 위 그림의 1번과정의 시간 복잡도를 O(1)로 만들어야 합니다.

 

이 과정을 이해하기 위해 우선 순서와 색인 그리고 물리 공간의 관계에 대해 살펴봐야 합니다.

 

순서와 색인(Index) 그리고 물리 공간

예를들어 C++에서 "abcde"문자열에서 3번째 문자인 'c'를 출력하려면 아마 대부분의 경우 '문자열[2]'문법을 떠올리실 겁니다.

 

여기서 순서는 3번째 이고 문자열의 서브스크립트로 전달한 2는 색인(Index)입니다.

 

왜이러한 연산이 바로 되는 것일까요?

 

사람은 순서를 수치(Number)로 표현합니다.

 

C++문법에서 문자열의 색인은 int(Number)자료형으로 표현되고 인덱스 사이의 거리는 1로 고정되어 있습니다.

 

따라서 특정 요소의 순서만 안다면 색인을 직관적으로 알 수 있습니다.

 

첫 색인(0) + 순서(2) * 색인간 거리(1) = 2

 

상수 시간의 연산으로 색인을 산출할 수 있음으로 C++의 문자열은 랜덤 액세스 컬렉션입니다.

 

Swift문자열은 정수 Index접근법을 사용하지 않습니다.

 

C++은 사용하고 Swift는 사용하지 않는 이유가 무엇일까요?

 

앞서 Collection프로토콜에서 Index제네릭을 요구하는 것을 알 수 있었습니다.

 

C++와 달리 Swift 문자열은 Index의 자료형으로 정수를 사용하지 않습니다.

 

왜냐하면 모든 문자가 동일한 크기를 가지는 C++문자열과 달리 Swift의 문자열은 문자마다 크기가 다른 유니코드를 사용하기 때문입니다.

 

C++의 경우 색인 값이 물리 주소 값과 정비례하기에 색인과 순서 역시 정비례할 수 있습니다.

 

따라서 색인을 직관적인 정수로 표현할 수 있는 것입니다.

 

그림으로 보면 다음과 같습니다.

 

C++ 문자열

 

Swift문자열의 경우 문자마다 물리 공간의 크기가 달라 계층간의 정비례가 유지될 수 없습니다.

 

색인을 물리 공간으로 변화하는 과정은 O(1)이 보장되야 하기에 순서와 색인 사이의 정비례성을 깨트릴 수 밖에 없는 것입니다.

 

따라서 Swift문자열의 인덱스의 타입으로 정수형을 사용하는 것은 불가한 것은 아니지만 부적합 합니다.

 

왜냐하면 정수 자료형은 요소간 차이가 1로 명시적으로 구분되는 타입이기에

 

Swift문자열의 인덱스로 사용시 오히려 혼란스러울 수 있습니다.

(인덱스가 1씩 증가하는 0,1,2,3 이 아니라 0, 5, 8, 13, 14과 같이 표현됨으로)

 

Swift문자열을 그림으로 보면 다음과 같습니다.

Swift문자열

Swift문자열의 인덱스는 정수형 처럼 덧셈 뺄샘으로 특정 순서의 인덱스를 알아낼 수기 없습니다.

 

따라서 문자열의 특정 순서의 요소에 접근하려면 index를 구하기 위한 연산이 필요하게 됩니다.

let swiftStr = "Hello"

// 'o'에 접근하기
// - offsetBy에 전달하는 값은 순서와 관련된 값이다.
let oIndex = swiftStr.index(swiftStr.startIndex, offsetBy: 4)
print(swiftStr[oIndex])

 

해당 index연산은 상수시간 이상의 복잡도를 가짐으로 Swift의 문자열은 랜덤 엑세스 컬렉션이 아닙니다.

 

즉 랜덤 액세스 컬렉션의 조건은 다음과 같습니다.

순서를 기반으로 인덱스 값을 상수 시간에 구할 수 있어야 한다.
(= 인덱스간 거리를 상수 시간에 구할 수 있어야 한다.)

 

인덱스가 정수형인 경우의 오해

대부분의 언어에서 인덱스로 정수형을 많이 사용합니다.

 

Swift에서 배열역시 Int타입을 사용하는 것을 알 수 있습니다.

 

정수형을 주로 사용하는 이유는 요소간 차이가 1로 고정되어 있기 때문에

 

직관적으로 순서를 기반으로 인덱스를 연산할 수 있기 때문이라고 생각합니다.

 

시작은 0,

순서는 5번째,

인덱스간 차이는 1,

그럼 인덱스는 4(0+4-1)입니다.

let swiftArr = ["H", "e", "l", "l", "o"]

// 'o'에 접근하기
print(swiftArr[4]) // 'o'

 

하지만 이 경우 컬렉션 인덱스를 연산하는 과정에서 외부적인 연산(Int자료형 연산)이 개입됬다고도 볼 수 있습니다.

 

컬렉션의 정신을 따르는 정공법적 접근은 아래와 같다고 할 수 있습니다.

let swiftArr = ["H", "e", "l", "l", "o"]

// 'o'에 접근하기
let order = 5
let startIndex = swiftArr.startIndex
let oIndex = swiftArr.index(startIndex, offsetBy: order-1) // 여기서 상수시간이 걸리면 랜덤 엑세스
print(swiftArr[oIndex]) // 'o'

 

:D

 

오늘은 평소에 주의깊게 살펴보지 않았던 시퀸스, 컬렉션 그리고 랜덤 엑세스 컬렉션까지 다뤄보았습니다.

 

앞으로 컬렉션기반 자료구조를 다루는데 있어 큰 도움이 될지는 모르지만, 한가지 얻어간 점이 있습니다.

 

바로 앞으로 생겨날 공식 API에 대한 이해입니다.

 

Sequence의 의의를 알고나니 비교적 최신에 나온 타입인 AsyncSequence를 접할때 Sequence의 특성을 바탕으로 해당 타입의 특성을 빠르게 이해할 수 있었습니다.

 

역사공부가 필요한 이유는 그것으로 부터 파생된 새로운 것을 잘 받아들일 수 있게 하기 때문이라고 생각합니다.

 

종종 이런 상위 개념들에 대해 정리를 하는 시간을 많이 가져볼까합니다.

 

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