Swift의 Unique 알고리즘을 살펴봅시다.
1. UniquedSquence 구조체
UniquedSequence는 기본 시퀀스에서 중복된 값을 제외하고 고유한 값만을 포함하는 시퀀스입니다.
public struct UniquedSequence<Base: Sequence, Subject: Hashable> {
@usableFromInline
internal let base: Base // 원본 컬렉션
@usableFromInline
internal let projection: (Base.Element) -> Subject // 원본 컬렉션의 요소를 Subject로 변환하는 클로저
@usableFromInline
internal init(base: Base, projection: @escaping (Base.Element) -> Subject {
self.base = base
self.projection = projection
}
}
Base는 Sequence를, Subject는 Hashable을 준수하는 제네릭 타입입니다.
base 상수는 UniquedSequence를 만드는 원본 시퀀스를 의미합니다.
projection 상수는 원본 시퀀스를 Subject로 반환하는 클로저입니다.
위 구조체의 인스턴스는 아직 아무 일도 하지 않습니다.
2. UniquedSequence의 Iterator 생성
extension UniquedSequence: Sequence {
// UniquedSequence 인스턴스의 Iterator
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var base: Base.Iterator // 원본 컬렉션의 Iterator
@usableFromInline
internal let projection: (Base.Element) -> Subject
@usableFromInline
internal var seen: Set<Subject> = []
@usableFromInline
internal init(
base: Base.Iterator,
projection: @escaping (Base.Element) -> Subject
) {
self.base = base
self.projection = projection
}
UniquedSequence 구조체를 확장하여 Sequence 프로토콜을 채택합니다.
Sequence 프로토콜은 IteratorProtocol과 밀접한 관련이 있습니다.
Sequence는 Iterator를 생성하여 Sequence의 각 요소로의 접근이 가능하도록 합니다.
Iterator는 Sequence의 (각 요소) 순회 프로세스를 추적하고,
프로세스를 한 번 실행할 때마다 순회 중인 Sequence 요소 1개를 반환합니다.
2번 항목의 코드는 UniquedSequence의 각 요소에 접근할 수 있도록 Iterator를 생성하는 코드입니다.
@inlinable
public mutating func next() -> Base.Element? {
while let element = base.next() { // Base.Iterator.next() 실행
if seen.insert(projection(element)).inserted {
return element
}
}
return nil
}
} // Iterator 정의 종료
Iterator의 next() 함수를 정의합니다.
base.next() 실행 결과가 존재한다면 해당 요소를 seen 에 삽입합니다.
seen은 Set 타입으로, 삽입에 성공한다면 해당 요소는 고유한 값, 실패한다면 중복값이라는 뜻이 됩니다.
요소가 고유한 값이라면 UniquedSequence의 Iterator.next() 실행 결과로 반환합니다.
@inlinable
public func makeIterator() -> Iterator {
Iterator(base: base.makeIterator(), projection: projection)
}
}
Iterator를 생성하는 함수 makeIterator() -> Iterator를 정의합니다.
3. LazySequenceProtocol 채택
extension UniquedSequence: LazySequenceProtocol
where Base: LazySequenceProtocol {}
lazy로도 사용 가능하도록 LazySequenceProtocol을 채택합니다.
4. uniqued() 함수
extension Sequence where Element: Hashable {
@inlinable
public func uniqued() -> UniquedSequence<Self, Element> {
UniquedSequence(base: self, projection: { $0 })
}
}
Sequence 프로토콜에 uniqued() 함수를 정의합니다.
uniqued() 함수는 원본 시퀀스에서 고유한(unique) 요소들로만 이루어진 시퀀스를 반환합니다.
고유한 요소들이 여러 개 있을 경우, 원본 시퀀스에 처음 등장하는 순서대로 나타납니다.
그럼 이제, Sequence 프로토콜을 채택한 객체가 uniqued()를 실행하면 어떻게 될까요?
let animals = ["dog", "pig", "cat", "ox", "dog", "cat"]
let uniqued = animals.uniqued()
아무일도 일어나지 않습니다.
정확히는, 우리가 결과로 기대하던 고유값의 배열이 만들어지지 않습니다.
uniqued() 함수는 UniquedSequence 인스턴스를 만들어내는 함수입니다.
따라서 현재 위 코드의 uniqued 상수는
uniqued() 의 실행 결과로 만들어진 UniquedSequence<[String]>, [String] 타입의 인스턴스입니다.
우리가 결과로 기대하던 배열은 만들기 위해서는 따로 배열로 선언하여 생성해주어야 합니다.
print(Array(uniqued)) // ["dog", "pig", "cat", "ox"] 출력
Array의 이니셜라이저는 Sequence의 Iterator를 생성하여 next() 함수를 호출하는 형태로 이루어져있다고 합니다.
그래서 따로 UniquedSequence의 Iterator를 생성하여 next()를 호출해주지 않아도
다음 요소를 순회하며 배열을 생성할 수 있습니다.
(챗GPT가 알려준 거라 이 부분은 부정확할 수 있습니다. 추후 Collection을 살펴봐야겠습니다.)
uniqued() 함수의 시간 복잡도는 O(1)로 매우 빠릅니다.
5. uniqued(on: ) 함수
extension Sequence {
@inlinable
public func uniqued<Subject: Hashable>(
on projection: (Element) throws -> Subject
) rethrows -> [Element] {
var seen: Set<Subject> = []
var result: [Element] = []
for element in self {
if seen.insert(try projection(element)).inserted {
result.append(element)
}
}
return result
}
}
Sequence 프로토콜에 uniqued(on: ) 함수를 정의합니다.
uniqued(on: ) 함수는 원본 시퀀스에서 projection 클로저의 결과로 반환된 고유한 요소들로 이루어진 배열을 반환합니다.
uniqued() 함수와 마찬가지로, 고유한 요소들이 여러 개일 경우, 원본 시퀀스에서 처음 등장하는 순서대로 나타납니다.
let animals = ["dog", "pig", "cat", "ox", "cow", "owl"]
let uniqued = animals.uniqued(on: { $0.first })
print(uniqued) // ["dog", "pig", "cat", "ox"] 출력
uniqued(on: ) 함수의 파라미터인 projection은 원본 시퀀스의 요소를 고유값으로 변환시키는 클로저입니다.
위 예제에서는 $0.first 즉, 요소의 첫 번째 글자를 고유값으로 사용합니다.
"dog", "pig", "cat", "ox", "cow", "owl"의 첫 번째 글자는 각각
"d", "p", "c", "o", "c", "o" 입니다.
여기서 "c"와 "o"는 2번씩 등장하므로, 가장 먼저 등장했던 "cat"과 "ox"가 결과 배열의 값으로 선택되었습니다.
uniqued(on: ) 함수는 uniqued() 함수와 아주 큰 차이점이 하나 있습니다.
그것은 바로, 반환값입니다.
앞서 uniqued() 함수는 함수를 실행한 뒤 배열을 생성해줘야 우리가 원하던 결과 배열을 얻을 수 있었습니다.
하지만 uniqued(on: ) 함수는 결과값으로 고유값 배열을 바로 반환해줍니다.
uniqued(on: ) 의 시간 복잡도는 O(n)으로, n은 시퀀스의 길이입니다.
6. lazy.uniqued()
extension LazySequenceProtocol {
@inlinable
public func uniqued<Subject: Hashable> (
on projection: @escaping (Element) -> Subject
) -> UniquedSequence<Self, Subject> {
UniquedSequence(base: self, projection: projection)
}
}
LazySequenceProtocol에 uniqued() 함수를 정의합니다.
uniqued() 는 원본 시퀀스에서 projection 클로저의 결과로 반환된 고유한 요소들로 이루어진 lazy 시퀀스를 반환합니다.
마찬가지로, 고유한 요소가 여러 개 있을 경우 원본 시퀀스에서 처음 등장하는 순서대로 나타납니다.
let animals = ["dog", "pig", "cat", "ox", "dog", "cat"]
let a = animals.lazy.uniqued() // UniquedSequence<LazySequence<[String]>, LazySequence<[String]>.Element> 타입
let b = Array(a) // [LazySequence<[String]>.Element] 타입
print(type(of: b)) // [String] 출력
LazySequenceProtocol의 uniqued() 함수도 4.에서 살펴본 uniqued() 함수와 동일하게 시퀀스를 반환합니다.
따라서 단순히 uniqued() 함수를 실행한 상수 a는 UniquedSequence 타입입니다.
상수 b는 a를 배열로 생성합니다.
다만, 현재 우리가 보고 있는 객체는 lazy 시퀀스입니다.
실제 사용 시점에 실제 객체가 만들어지므로, 상수 b의 타입은 [LazySequnce<String>.Element] 입니다.
print 함수로 b의 타입을 출력했습니다.
print 함수에서 상수 b가 사용되므로, 해당 시점의 b는 [String] 타입입니다.
lazy 시퀀스의 uniqued() 또한 시간 복잡도는 O(1)로 매우 빠릅니다.