作者：Ole Begemann溃论，原文鏈接屎蜓，原文日期：2017-02-08
譯者：四娘；校對(duì)：Cwift蔬芥；定稿：CMB

在上周的 Swift Talk 里梆靖，F(xiàn)lorian 和 Chris 編寫(xiě)了一個(gè)有序數(shù)組類(lèi)型 SortedArray：一個(gè)總是按照指定規(guī)則排序的數(shù)組。這很贊笔诵，因?yàn)樗鼘⒍鄠€(gè)[不變性](https://en.wikipedia.org/wiki/Invariant_(computer_science)編碼到了類(lèi)型系統(tǒng)里返吻。用戶可以使用這個(gè)類(lèi)型去取代普通的 數(shù)組 ，而且不用擔(dān)心忘記手動(dòng)排序數(shù)組乎婿。

為了保持視頻簡(jiǎn)短测僵，F(xiàn)lorian 和 Chris 省略掉了一些很實(shí)用的功能。我想給你展示一下這部分實(shí)用功能的實(shí)現(xiàn)谢翎。這些實(shí)現(xiàn)都不難編寫(xiě)捍靠，我的主要目的是讓你明白借助標(biāo)準(zhǔn)庫(kù)去實(shí)現(xiàn)一個(gè)緊貼需求的自定義集合類(lèi)型是多么簡(jiǎn)單。

你可以去 GitHub 上查看全部代碼 森逮，但下面會(huì)有更多講解榨婆。

指定集合的協(xié)議

如視頻所示，SortedArray 遵守了 RandomAccessCollection 褒侧，它可以讓隨機(jī)訪問(wèn)數(shù)組元素的操作變得更快良风，稍后實(shí)現(xiàn)一個(gè)高效的 Binary Search 的時(shí)候會(huì)用到它谊迄。

實(shí)現(xiàn)部分很直觀，因?yàn)榘阉袞|西都橋接到用來(lái)實(shí)際存儲(chǔ)的數(shù)組那里烟央。由于 Index 是 Int 類(lèi)型统诺，你甚至不用自己實(shí)現(xiàn) index(_:offsetBy:) 和 distance(from:to:) 函數(shù)，標(biāo)準(zhǔn)庫(kù)已經(jīng)提供了默認(rèn)的實(shí)現(xiàn)疑俭。

SortedArray 不能遵守 MutableCollection 或者 RangeReplaceableCollection 粮呢，因?yàn)樗麄兊?語(yǔ)義 -- 插入/替換特定位置的元素，跟我們保持元素有序的原則沖突钞艇。

字面量表達(dá)

SortedArray 也不遵守 ExpressibleByArrayLiteral 啄寡，即你不能像下面這么做：

let sorted: SortedArray = [3,1,2]

這個(gè)功能很好，但是你沒(méi)辦法給一個(gè)字面數(shù)組傳遞排序算法香璃，并且 SortedArray 的元素必須遵守 Comparable 这难。因?yàn)?Swift 3 還不支持 conditional protocol conformance ，所以需要寫(xiě)成下面這樣：

extension SortedArray: ExpressibleByArrayLiteral where Element: Comparable {
    ...
}

也許 Swift 4 中可以實(shí)現(xiàn) conditional protocol conformance葡秒。

Binary search

使用有序數(shù)組的好處之一就是可以通過(guò) Binary Search 快速找到某一個(gè)數(shù)組元素姻乓。在這里 Binary Search 的時(shí)間復(fù)雜度 是 log n 而不是線性的 。

為了實(shí)現(xiàn)該算法眯牧，我首先寫(xiě)了一個(gè)輔助函數(shù) search(for:)蹋岩。你可以去 GitHub 上查看完整代碼 ；這里我想討論一下返回的類(lèi)型：

fileprivate enum Match<Index: Comparable> {
    case found(at: Index)
    case notFound(insertAt: Index)
}

extension SortedArray {
     
    /// 使用 Binary Search 找到 `newElement`
    ///
    /// - Returns: 如果 `newElement` 在數(shù)組里学少，就返回 `.found(at: index)`剪个，
    ///   這里的 `index` 是數(shù)組里元素的位置
    ///   如果 `newElement` 不在這個(gè)數(shù)組里，就會(huì)返回 `.notfound(insertAt: index)`
    ///   這里的 `index` 是根據(jù)排序算法得出元素應(yīng)該插入的位置
    ///   如果數(shù)組包含了多個(gè)元素版确，且都等于 `newElement`扣囊，那就無(wú)法保證哪一個(gè)會(huì)被找到
    ///   
    /// - Complexity: O(_log(n)_)，這里的 _n_ 是數(shù)組的大小.
    fileprivate func search(for newElement: Element) -> Match<Index> {
        ...
    }
}

標(biāo)準(zhǔn)庫(kù)里的 index(of:) 返回的是一個(gè) Optional<Index>绒疗，沒(méi)有找到的情況就會(huì)返回 nil侵歇。而 search(for:) 方法也類(lèi)似，但它的返回值是一個(gè)自定義的枚舉吓蘑，無(wú)論是 .found 或者 .notFound 都會(huì)帶上一個(gè)序號(hào)作為附加信息惕虑。這可以讓我們?cè)谒阉骱筒迦霑r(shí)使用一致的算法：返回的序號(hào)就是我們需要維持有序數(shù)組時(shí)插入元素的位置。

算法準(zhǔn)備就緒之后磨镶，就可以開(kāi)始實(shí)現(xiàn) index(of:) 和 contains(_:) 了：

extension SortedArray {

    /// 返回特定值在集合里第一次出現(xiàn)的位置
    ///
    /// - Complexity: O(_log(n)_)溃蔫，這里的 _n_ 是數(shù)組的大小
    public func index(of element: Element) -> Index? {
        switch search(for: element) {
        case let .found(at: index): return index
        case .notFound(insertAt: _): return nil
        }
    }

    /// 返回一個(gè)布爾值，表示這個(gè)序列是否包含給定的元素
    ///
    /// - Complexity: O(_log(n)_)琳猫，_n_ 是數(shù)組的大小
    public func contains(_ element: Element) -> Bool {
        return index(of: element) != nil
    }
}

需要注意的是伟叛，這里的實(shí)現(xiàn)不止比標(biāo)準(zhǔn)庫(kù)里的實(shí)現(xiàn)更高效，而且通用性更強(qiáng). 標(biāo)準(zhǔn)庫(kù)里這個(gè)方法還要求 where Iterator.Element: Comparable 的約束脐嫂，而 SortedArray 總是擁有一個(gè)排序算法,所以不需要這樣的約束痪伦。

插入元素

下一個(gè)任務(wù)是利用 binary search 的優(yōu)勢(shì)去提高插入元素的效率侄榴。我決定提供兩個(gè)插入函數(shù): 第一個(gè)會(huì)在正確的位置去插入單個(gè)元素，保持?jǐn)?shù)組有序网沾。它利用 binary search 去找到正確的插入位置，復(fù)雜度為 O(log n)蕊爵。插入新元素到非空數(shù)組里辉哥，最糟糕的時(shí)間復(fù)雜度是 O(n)，因?yàn)槿恳延性夭坏貌灰苿?dòng)位置去提供空間攒射。

第二個(gè)函數(shù)可以插入一組序列醋旦。這里我選擇先把所有元素都插入到數(shù)組最后，然后進(jìn)行一次重新排序. 這比重復(fù)尋找正確的插入位置更快(如果插入的數(shù)組元素個(gè)數(shù)大于 log n)会放。

extension SortedArray {
    
    /// 插入一個(gè)新元素到數(shù)組里饲齐，并保持?jǐn)?shù)組有序
    ///
    /// - Returns: 新元素插入的位置
    /// - Complexity: O(_n_)     這里的 _n_ 是數(shù)組大小
    ///    如果新元素插入到數(shù)組最后，時(shí)間復(fù)雜度下降到 O(_log n_)
    @discardableResult
    public mutating func insert(_ newElement: Element) -> Index {
        let index = insertionIndex(for: newElement)
        // 如果元素可以被插入到數(shù)組最后咧最，則復(fù)雜度為 O(1)
        // 最糟糕的情況是 O(_n) (插入到最前面時(shí))
        _elements.insert(newElement, at: index)
        return index
    }

    /// 插入 `elements` 里的所有元素到 `self` 里捂人，保持?jǐn)?shù)組有序
    /// 這會(huì)比每個(gè)元素都單獨(dú)插入一遍更快
    /// 因?yàn)槲覀冎恍枰匦屡判蛞淮?    ///
    /// - Complexity: O(_n * log(n)_)，_n_ 是插入后數(shù)組的大小
    public mutating func insert<S: Sequence>(contentsOf newElements: S) where S.Iterator.Element == Element {
        _elements.append(contentsOf: newElements)
        _elements.sort(by: areInIncreasingOrder)
    }
}

其它優(yōu)勢(shì)

Chris 和 Florian 已經(jīng)在這一集里做過(guò)展示矢沿，我們可以得到一個(gè)更高效的 min() 和 max() 滥搭。因?yàn)樽钚≈底畲笾捣謩e是有序集合的第一個(gè)和最后一個(gè)元素：

extension SortedArray {
     /// 返回集合里的最小值
    ///
    /// - Complexity: O(1).
    @warn_unqualified_access
    public func min() -> Element? {
        return first
    }

    /// 返回集合里的最大值
    ///
    /// - Complexity: O(1).

    @warn_unqualified_access
    public func max() -> Element? {
        return last
    }
}

當(dāng)你在類(lèi)型的內(nèi)部實(shí)現(xiàn)中調(diào)用這些函數(shù)，卻沒(méi)有顯式地寫(xiě)明 self. 的前綴時(shí)捣鲸，@warn_unqualified_access 會(huì)告訴編譯器拋出一個(gè)警告 瑟匆。這樣可以幫助你避免混淆了這些函數(shù)與全局函數(shù) min(::) 和 max(::) 。

如同 index(of:) 和 contains(_:) 一樣栽惶，我們的 min() 和 max() 更加通用愁溜，因?yàn)樗鼈儾恍枰厥?Comparable 的. 我們獲得了更高的效率，更少的約束外厂。

只有協(xié)議要求的才可以自定義

這四個(gè)方法都不是 Sequence 和 Collection 協(xié)議里要求必須實(shí)現(xiàn)的冕象，他們不在協(xié)議的定義里。他們只是拓展里的默認(rèn)實(shí)現(xiàn)酣衷。結(jié)果就是交惯，調(diào)用這些方法的時(shí)候都會(huì)是靜態(tài)派發(fā)，因?yàn)樗麄儾皇?可自定義的 穿仪。

SortedArray 里的實(shí)現(xiàn)并不會(huì)重寫(xiě)默認(rèn)實(shí)現(xiàn)(因?yàn)橹灰獏f(xié)議里定義的方法才可以被重寫(xiě))席爽，他們只是附屬品。當(dāng)你直接使用 SortedArray 的時(shí)候啊片，更加高效的實(shí)現(xiàn)會(huì)讓你收益只锻。但當(dāng)它們作為泛型時(shí)將永遠(yuǎn)不會(huì)被調(diào)用。例如：

let numbers = SortedArray(unsorted: [3,2,1])
    // 這會(huì)直接調(diào)用 SortedArray.max()
    let a = numbers.max()

func myMax<S: Sequence>(_ sequence: S ) -> S.Iterator.Element?
    where S.Iterator.Element: Comparable {
    return sequence.max()
}

// 這種寫(xiě)法調(diào)用的是 Sequence.max() 了(更低效的版本)
let b = myMax(numbers)

我們沒(méi)辦法改變這個(gè) "bug"紫谷，swift-evolution 有討論過(guò)讓這些方法變成協(xié)議的一部分(我不確定這是不是一個(gè)好的做法)齐饮。

2017.02.09 更新: 我忘了 index(of:) 和 contains(_:) 這些方法捐寥，現(xiàn)在還不是 Sequence 和 Collection 的一部分艺挪，因?yàn)樗麄冃枰?Iterator.Element 是 Equatable 的赴邻。而現(xiàn)在還沒(méi)有方法去定義一個(gè)泛型協(xié)議。Brent Royal-Gordon 在 swift-evolution 里進(jìn)行了相關(guān)的討論并且提問(wèn)泛型協(xié)議是否應(yīng)該加入 Swift 里完丽。

切片

我嘗試著把 SortedArray 保存在一個(gè) ArraySlice 而不是 Array 里捺僻，這么做的優(yōu)勢(shì)就是可以非常簡(jiǎn)單地把 SortedArray.SubSequence 定義為 ArraySlice乡洼。這會(huì)讓切片操作變得非常簡(jiǎn)單，因?yàn)?sortedArray.prefix(5) 會(huì)直接返回另一個(gè) SortedArray匕坯，而不是默認(rèn)的 RandomAccessSlice 束昵。

最后我還是決定放棄這種做法，因?yàn)殚L(zhǎng)時(shí)間持有一個(gè) ArraySlice 的實(shí)例不是一件好事. 就算只持有一個(gè)非常大的數(shù)組的切片葛峻，也會(huì)一直間接持有那個(gè)大的數(shù)組锹雏，這會(huì)導(dǎo)致非常高的內(nèi)存占用，這是使用者不想看到的术奖，就算基底 Array 的內(nèi)存不會(huì)泄露礁遵，但切片還是會(huì)讓它無(wú)法及時(shí)釋放。

外部 Modules 引入的泛型類(lèi)型的性能表現(xiàn)

如果你想在你的代碼里使用 SortedArray (或者別的性能要求比較高的泛型)腰耙，我建議你不要直接把它作為第三方 module 引入榛丢，而是 直接把源代碼文件加入到你的 module 里 。

就 Swift 3 而言挺庞，Swift 無(wú)法在跨 Module 的情況下表現(xiàn)出泛型類(lèi)型的優(yōu)勢(shì)晰赞。換而言之，如果你在代碼里使用了 SortedArray<Int>选侨，并且 SortedArray 是定義在另一個(gè) Module 的時(shí)候掖鱼，編譯器無(wú)法為元素為 Int 的 Array 優(yōu)化生成代碼，只能按照常規(guī)的方式援制，將每一個(gè)泛型值打包到一個(gè)容器里戏挡，然后通過(guò) witness table 進(jìn)行方法派發(fā)。這很容易造成你的代碼在執(zhí)行時(shí)被拖慢 一到兩個(gè)數(shù)量級(jí) 晨仑。

當(dāng)前版本的 Swift 編譯器無(wú)法約束從外部 Module 引入的泛型(標(biāo)準(zhǔn)庫(kù)除外)褐墅。…這個(gè)限制會(huì)讓外部 Module 引入的集合類(lèi)型性能大幅下降洪己。特別當(dāng)集合中的元素是簡(jiǎn)單的妥凳，被極度優(yōu)化的值類(lèi)型，例如 Int答捕，甚至是 String逝钥。 依賴引入的 Module，你的集合裝填基礎(chǔ)數(shù)據(jù)類(lèi)型時(shí)性能會(huì)有 10-200 倍的下降拱镐。

標(biāo)準(zhǔn)庫(kù)是唯一一個(gè)例外艘款，標(biāo)準(zhǔn)庫(kù)里的類(lèi)型對(duì)于任何 Module 都是可見(jiàn)的持际。

我希望 Swift 編譯器團(tuán)隊(duì)可以找到一個(gè)方法解決這個(gè)問(wèn)題。雖然我不知道該怎么做哗咆。編譯器現(xiàn)在加入了一個(gè)
非正式的修飾符 @_specialize (可能在 之后會(huì)加入一個(gè)新的語(yǔ)法 )蜘欲。給一個(gè)方法添加這個(gè)修飾符時(shí)，相關(guān)的類(lèi)型就告訴編譯器為自己生成特殊的代碼岳枷。目前正在開(kāi)發(fā)的版本里芒填，這個(gè)修飾符好像支持使用 _Trivial64 去把所有不那么重要的值類(lèi)型都封裝成相同的大小。

總結(jié)

完整的實(shí)現(xiàn) 總共兩百多行空繁，包括注釋。

就像你看到的朱庆，自定義集合類(lèi)型有很多需要考量的東西盛泡。而且我們都只考慮了接口的設(shè)計(jì)，我們甚至還沒(méi)接觸底層的實(shí)現(xiàn)娱颊。但我覺(jué)得這些付出都是有回報(bào)的傲诵。我們獲得了一個(gè)行為和內(nèi)建集合類(lèi)型完全一致的類(lèi)型，兼容序列和集合操作的同時(shí)還會(huì)根據(jù)算法自我變化箱硕。

雖然跨 Module 使用泛型類(lèi)型確實(shí)對(duì)于性能有很大的影響拴竹。

本文由 SwiftGG 翻譯組翻譯，已經(jīng)獲得作者翻譯授權(quán)剧罩，最新文章請(qǐng)?jiān)L問(wèn) http://swift.gg栓拜。