[Swift] RandomAccessCollection / BidirectionalCollection 의 Time Complexity

Collection 문서를 보면  Time Complexity 가 두개로 나온 부분이 많은데요,

 

예를들어

1) randomElement()

2) distance(from:to:)

 

3)  count

---

 

✓ RandomAccessCollection = 효율적인 random-access index  순회를 지원하는 콜렉션

✓ BidirectionalCollection  =  양방향 (forward, backward) 순회를 지원하는 콜렉션 

 

이렇게 두개의 콜렉션이 있는데, 

Expected Performance  에 잘 나와있는 것 처럼  bidirectional collection 는 전체 collection 을 순회해서 카운팅 해야하므로 

O(1) 의 시간복잡도를 가질 수 없기 때문입니다. 

 

 

각 콜렉션 문서에서도 차이를 잘 볼 수 있습니다.

RandomAccessCollection 에는

이를 채택하는 custom type 을 만들 때,

시간복잡도를 보장하기 위해  index(_:offsetBy:) and distance(from:to:) 를 O(1) 로 구현하라고 나와있습니다. 

 

BidirectionalCollection  에는

이를 채택하는 custom type 을 만들 때, index(before:) 를 구현하라고 나와있습니다.

또한 Bidirectional collection 은 추가적인 연산을 더 제공할 수 있는데,  마지막 요소에 대한 효율적인 접근,  reversed() 메소드 등이라고 합니다. 

 

 

[ String ]

대표적인 BidirectionalCollection 은 String 입니다.

 

https://developer.apple.com/documentation/swift/bidirectionalcollection

 

 

그래서  String의  index(_:offsetBy:) , distance(from:to:) , count 모두 O(n) 의 시간복잡도를 가집니다. 

 

 

[ String subscript ]

이제 메인입니다...! 이것 때문에 서두가 길었습니다. 

 

Swift에서 String subscript 은 Int가 아니라 String.Index 를 넘겨야하는데, (Swift 3부터였던 걸로 기억)

보통 제공되는 startIndex, endIndex 에 distance (offset) 을 구해서 String.Index 를 만들고

이걸 넘겨 subscript 연산을 합니다. 

 

 index(_:offsetBy:) 문서의 예제 입니다. 

let s = "Swift"
let i = s.index(s.startIndex, offsetBy: 4)
print(s[i])
// Prints "t"

 

 

이런 식으로 extension을 만들어 사용하기도 합니다.

extension String {
    subscript(i: Int) -> String {
        return String(self[index(startIndex, offsetBy: i)])
    }
}

 

이때 index 연산이 O(1)  이 아니기 때문에 subcript 연산을 다른 언어에서 처럼  O(1) 이라고 할 수 없습니다. 

n이 length 가 아니라 distance 이긴 한데,,,  

 

그래도 시간을 단축할 수 있는 방법이 있을까요? 

(우리가 String을 쓸 때,  최대한 count == 0 이 아니라 isEmpty 를 쓰는 것 처럼..?  참고)

 

[ String Subscript 시간 복잡도 개선 실험 ]

 

1) 기존에 쓰는 방식 

import Foundation

let str = String(repeating: "안녕하세요", count: 5000)
let time = ContinuousClock().measure {
    print(str[1]) // 녕
}
print(time) // 0.000764042 seconds

extension String {
    subscript(i: Int) -> String {
        return String(self[index(startIndex, offsetBy: i)])
    }
}

 

 

2) init(utf16Offset:in:) 로 Index 구하기

 

이거 정확히 뭔지 이해못했음;; 그래서 시간복잡도도 어떻게 되는 지 모르겠음  (근데 1번 보다 느리다) 

import Foundation

let str = String(repeating: "안녕하세요", count: 5000)
let time = ContinuousClock().measure {
    print(str[1]) // 녕
}
print(time) // 0.001277333 seconds

extension String {
    subscript(i: Int) -> String {
        let index = String.Index(utf16Offset: i, in: self)
        return String(self[index])
    }
}

 

구글링하다가 뭔가 찾으면 추가하겠음