第九章：泛型 Generics
9.2 对集合采用泛型操作 Operating Generically on Collections
本小节主要是通过泛型二分法，序列随机排列，判断子序列的位置的算法的几个Demo，来讲了一些应该注意的知识点。
本小节代码量有些多，不要求全部掌握。通读一遍即可，以后在实际开发中有遇到算法相关的泛型封装可以回来看看~
二分法查找 A Binary Search
书中先对RandomAccessCollection协议随机存取协议(笔记第三章第五节有讲，忘了的同学可以回头看看) 封装一个二分法的extension方法，
extension RandomAccessCollection where Index == Int, IndexDistance == Int{只满足Int的二分查找
public func binarySearch(for value: Iterator.Element,
areInIncreasingOrder: (Iterator.Element, Iterator.Element) -> Bool)
-> Index? {
var left = 0
var right = count - 1
while left <= right {
let mid = (left + right) / 2
let candidate = self[mid]
if areInIncreasingOrder(candidate, value) {
left = mid + 1
}else if areInIncreasingOrder(value, candidate) {
right = mid - 1
}else {只有左右两个相等才会返回中间值
return mid
}
}
return nil
}
}
let binaryInt = [1,3,2,6,4]
let bin = binaryInt[1..<3]
bin.binarySearch(for: 2, areInIncreasingOrder: <)
print(binaryInt ?? 000)
但会引入一个严重的bug，并不是所有的集合都以整数为索引的，Dictionary、Set、String都有自己的索引类型。
还有一个是以整数为索引的并不一定都以0开始 例如 Array[3..<5] 的startIndex就是3 ，如果使用就会在运行时崩溃。 为此我们进行二次修改
泛型二分查找 Generic Binary Search
我们二次修改上面的方法，来满足泛型的要求
泛型二分查找
extension RandomAccessCollection {
public func binarySearch(for value: Iterator.Element,
areInIncreasingOrder: (Iterator.Element, Iterator.Element) -> Bool)
-> Index? {
guard !isEmpty else {
return nil
}
/ left和right不再是整数类型了，而是对于的索引值
var left = startIndex
var right = index(before: endIndex)
while left <= right {
let dist = distance(from: left, to: right) 计算left到right的距离
let mid = index(left, offsetBy: dist/2)
let candidate = self[mid]
if areInIncreasingOrder(candidate, value) {
left = index(after: mid)
}else if areInIncreasingOrder(value, candidate) {
right = index(before: mid)
}else {
return mid
}
}
return nil
}
}
extension RandomAccessCollection where Iterator.Element: Comparable {
func binarySearch(for value: Iterator.Element) -> Index? {
return binarySearch(for: value, areInIncreasingOrder: <)
}
}
let a = ["a", "c", "d", "g"]
let r = a.reversed()
r.binarySearch(for: "d", areInIncreasingOrder: >) == r.startIndex
let s = a[1..<3]
s.startIndex
s.binarySearch(for: "d")
这样对二分法的泛型改造就结束啦~
集合随机排列 Shuffing Collections
我们先用代码实现一下 Fisher-Yates洗牌算法。
/集合随机排列
extension Array {
mutating func shuffle(){
for i in 0..<(count - 1) {
let j = Int(arc4random_uniform(UInt32(count - i))) + i
guard i != j else {保证不会将一个元素与自己交换
continue
}
self.swapAt(i, j)将两个元素交换
}
}
func shuffled() -> [Element] {不可变版本
var clone = self
clone.shuffle()
return clone
}
}
和前面的二分法算法一样，这里还是依赖整数索引才能使用。 我们用泛型进行二次改造
extension MutableCollection where Self: RandomAccessCollection {
mutating func shuffle() {
var i = startIndex
let beforeEndIndex = index(before: endIndex)
while i < beforeEndIndex {
let dist = distance(from: i, to: endIndex)
let randomDistance = IndexDistance.distance(dist)
let j = index(i, offsetBy: randomDistance)
guard i != else {
continue
}
swap(&self[i], &self[j]
formIndex(after: &i))
}
}
}
///二次封装
extension Sequence {
func shuffled() -> [Iterator.Element] {
var clone = Array(self)
clone.shuffle()
return clone
}
}
Subsequence和泛型算法 SubSequence and Generic Algorithms
这一小结最后一个Demo。。求子集合的位置。
extension Collection where Iterator.Element: Equatable {
func search<Other: Sequence>(for pattern: Other) -> Index?
where Other.Iterator.Element == Iterator.Element {
return indices.first(where: { (idx) -> Bool in
suffix(from: idx).starts(with: pattern)
})
}
}
let text = "it was the best of times"
text.search(for: ["w","a","s"])
注：如果知道被搜索的序列和待搜索的序列都满足随机存取(RandomAccessCollection)的索引,我们可以二次优化。
extension RandomAccessCollection
where Iterator.Element: Equatable,
Indices.Iterator.Element == Index,
SubSequence.Iterator.Element == Iterator.Element,
SubSequence.Indices.Iterator.Element == Index {
func search<Other: RandomAccessCollection>(for pattern: Other) -> Index?
where Other.IndexDistance == IndexDistance,
Other.Iterator.Element == Iterator.Element{
///如果匹配集合比原集合长 直接退出
guard !isEmpty && pattern.count <= count else {
return nil
}
///否则可以取到容纳匹配模式的最后一个索引。
let stopSearchIndex = index(endIndex, offsetBy: -pattern.count)
///检查从当前位置切片是否可以以匹配模式开头。
return prefix(upTo: stopSearchIndex).indices.first(where: { (idx) -> Bool in
suffix(from: idx).starts(with: pattern)
})
}
}
let numbers = 1..<100
numbers.search(for: 80..<90)
overover~
网友评论