第九章：泛型 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~

文章源文件地址,大家如果有更好的想法和观点欢迎交流