스위프트에서 리스트를 뒤집는 것은 Swift Standard Library의 .reversed() 를 활용할 수 있다.
놀랍게도 이 메서드는 시간복잡도가 O(1)이다. 왜냐하면 이건 lazy이고, 원래 컬렉션을 거꾸로 뒤집는 뷰를 생성하기만 하기 때문이다. 정확히 말하자면 ReverseCollection이라는 래핑객체를 반환한다. 따라서 우리는 O(n) 시간 복잡도로 리스트를 순회할 수 있게된다. 하지만 이것을 인덱스로 접근하면 O(1)이라는 시간복잡도를 잃게된다.
let arr = [1, 2, 3, 4]
let i = arr.reversed()[1] // lose O(1) efficiency.
먼저 알아둘 것은, reversed() 메서드는 구체적으로 다음 두가지 정의 중에 선택하여 오버로드 된다는 점이다.
- BidirectionalCollection.reversed() → ReversedCollection을 반환한다.
- Sequence.reversed() → [Element]를 반환한다.
이 시점에서 오버로딩은 굉장히 혼란스워진다. 왜냐하면 오직 Sequence 타입만이 type(of: x) == type(of: x.reversed()) 이다.
Swift 타입 체커는 덜 구체적인 오버로드 보다는 구체적인 오버로드를 선호한다. 따라서 일반적으로 컴파일러는 가능하다면 Sequence의 오버로드보다는 BidirectionalCollection의 오버로드를 사용한다. BidirectionalCollection은 opaque한 인덱스 유형인 Int를 가지며, 이것은 Int를 사용해 인덱스접근을 할 수 없다. 그래서 만약 Int로 인덱싱을 하려고 시도한다면 이 시점에 컴파일러는 강제적으로, 대신 Sequence의 오버로드를 선택한다.
또한 Swift의 코드 추론은 다른 줄의 주변 문맥을 고려하지 않는다.
그래서 다음과 같은 것은 컴파일에러다.
let arr = [1,2,3,4]
let rev = arr.reversed() // ReversedCollection<Array<Int>> 이것은 Int인덱싱이 불가능하다.
let i = rev[1] // compile error!
다음 예시를 참고하자.
func collType1<T: Collection>(_: T) {
print(T.self) // ReversedCollection<Array<Int>>
print(T.Index.self) // Index
}
func collType2<T: Collection>(_: T) where T.Index == Int {
print(T.self) // Array<Int>
print(T.Index.self) // Int
}
let x: [Int] = [1, 2, 3]
collType1(x.reversed())
collType2(x.reversed())
다음엔 불명확 타입과 BidirectionalCollection, ReversedCollection, Sequence에 대해 정리해야 겠다.
결론: Swift의 Array.reversed()의 시간 복잡도는 놀랍게도 O(1)
https://stackoverflow.com/questions/68332664/is-swift-array-reversedn-efficient-or-not
Uploaded by N2T
