[swift 进阶]读书笔记-第九章:泛型 C9P2 对集合采

2019-04-11  本文已影响0人  liaoworkinn

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

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

上一篇 下一篇

猜你喜欢

热点阅读