[譯] Swift 中的惰性序列及其原理

Swift · 發表 2018-10-13 08:41:37

摘要：使用map 和filter 這樣的高階函式在 Swift 專案中非常常見，因為它們是簡單的演算法，能讓你將複雜的想法轉化為簡單的單行函式。不幸的是，它們沒能解決所有的問題 — 至少在它們的預設實現中沒能解決。高階函式是非常急迫的：它們使用閉包立即返回一個新的陣列，不...

使用map 和filter 這樣的高階函式在 Swift 專案中非常常見，因為它們是簡單的演算法，能讓你將複雜的想法轉化為簡單的單行函式。不幸的是，它們沒能解決所有的問題 — 至少在它們的預設實現中沒能解決。高階函式是非常急迫的：它們使用閉包立即返回一個新的陣列，不論你是否需要提前返回或者只是使用其中特定的元素。當效能很重要時，你可能被逼著寫一些具體的輔助方法來避免高階函式急迫的這個性質。

let addresses = getFirstThreeAddresses(withIdentifier: "HOME")
func getFirstThreeAddresses(withIdentifier identifier: String) -> [Address] {
// 不使用 .filter{}.prefix(3)，因為我們需要提前返回
var addresses = [Address]()
for address in allAddresses where address.identifier == identifier {
addresses.append(address)
if addresses.count == 3 {
break
}
}
return addresses
}
複製程式碼

幸運的是，Swift 有辦法在使用高階函式的同時保持其高效能和輔助函式 — Swift 標準庫Sequences 和Collections 的惰性執行版本可以通過lazy 關鍵詞獲取到。

這些變化後的惰性版本使用起來就和普通情況一樣，僅有一處改變：它們擁有像map 和filter 一樣自定義實現的方法來保證它們的惰性 — 這意味著實際上只有在你需要它們的時候 才會進行運算。

let allNumbers = Array(1...1000)
let normalMap = allNumbers.map { $0 * 2 } // 不論你是需要做什麼，這段對映都會被執行完
let lazyMap = allNumbers.lazy.map { $0 * 2 } // 在這裡什麼都不會發生
print(lazyMap[0]) // 列印 2，但其他不涉及的部分都不會發生
複製程式碼

雖然一開始看著有點嚇人，但它們允許你減少大多數的for 迴圈，取代以能夠提前返回的單行函式。例如，當用於查詢滿足斷言的第一個元素時，這是它與其他方法的比較：

// 在 [Address] 陣列中有 10000 個 Address 元素，和一個位於最開頭的 "HOME" address 元素
let address = allAddresses.filter { $0.identifier == "HOME" }.first // ~0.15 秒

// 對比

func firstAddress(withIdentifier identifier: String) -> Address? {
// 現在你可以使用標準庫的 first(where:) 方法，
// 但讓我們現在假裝它不存在。
for address in allAddresses where address.identifier == identifier {
return address
}
return nil
}

let address = firstAddress(withIdentifier: "HOME") // 立刻

// 對比

let address = allAddresses.lazy.filter { $0.identifier == "HOME" }.first // 同樣立刻返回，並且程式碼更少！
複製程式碼

除了寫的程式碼更少之外，它們也對總體上惰性操作非常有幫助，能讓你的程式碼更易閱讀。假設你有一個購物應用，如果使用者花費太長時間完成購買，則會顯示來自本地資料庫的優惠：

let offerViews = offersJson.compactMap { database.load(offer: $0) }.map(OfferView.init) // O(n)
var currentOffer = -1

func displayNextOffer() {
guard currentOffer + 1 < offerViews.count else {
return
}
currentOffer += 1
offerViews[currentOffer].display(atViewController: self)
}
複製程式碼

當這個解決辦法生效時，它有一個主要的問題：我急迫地將全部要展示的 json 內容都對映到了OfferViews ，即便使用者並不一定會看完這所有的選項。這並不是一個問題如果內容offerJson 只是一個小型的陣列，但如果資料量巨大時，一次性將所有內容從資料庫取出立刻就成為一個問題了。

你可以通過將解析邏輯移動到displayNextOffer() ，實現僅僅對映需要的OfferViews ，但你的程式碼質量可能因為保留了原始資料而變得難以理解：

let offersJson: [[String: Any]] = //
var currentOffer = -1

func displayNextOffer() {
guard currentOffer + 1 < offerViews.count else {
return
}
currentOffer += 1
guard let offer = database.load(offer: offersJson[currentOffer]) else {
return
}
let offerView = OfferView(offer: offer)
offerView.display(atViewController: self)
}
複製程式碼

通過使用lazy ，當前的offerView 將只會在被displayNextOffer() 使用到時對映陣列相對應的位置，這樣既保證了程式碼可讀性又保證了程式碼效能！

let offerViews = offersJson.lazy.compactMap { database.load(offer: $0) }.map(OfferView.init) // 這裡什麼都沒發生！
var currentOffer = -1

func displayNextOffer() {
guard currentOffer + 1 < offerViews.count else {
return
}
currentOffer += 1
offerViews[currentOffer].display(atViewController: self) // 只在這裡發生了對映，且只有需要的元素
}
複製程式碼

不過注意，惰性序列將不會有快取。這意味著如果使用了offerViews[0] 兩次，全部對映過程也都將被執行兩次 。如果你要多次獲取某些元素，那麼就把他們放到普通的陣列之中吧。

這為什麼能生效？

雖然它們在使用時看起來很神奇，但延遲序列的內部實現並不像它看起來那麼複雜。

如果我們列印第二個例子的型別，我們可以看到，即使我們惰性對映的Collection 就像普通的Collection 一樣，我們也處理的是不同的型別：

let lazyMap = Array(1...1000).lazy.map { $0 * 2 }
print(lazyMap) // LazyMapCollection<Array<Int>, Int>
let lazyMap = Array(1...1000).lazy.filter { $0 % 2 == 0 }.map { $0 * 2 }
print(lazyMap) // LazyMapCollection<LazyFilterCollection<Array<Int>>, Int>
// 在這種情況下，第一個泛型引數是惰性操作內部的 Collection，而第二個引數是 map 操作的轉換函式。
複製程式碼

看看 Swift 的原始碼，我們可以通過這樣一個事實，看到其非急迫性，即這些方法除了返回一個新型別之外，實際上並沒有做任何事情：

（我將使用LazySequence 而不是LazyCollections 的程式碼作為例子，因為他們在特性上十分相似。如果你不理解Sequences 如何工作，ofollow,noindex">那麼看一下 Apple 的這篇文章吧。）

extension LazySequenceProtocol {
/// 返回一個 `LazyMapSequence` 型別來替代 `Sequence`。
/// 結果每次被 `transform` 方法讀取一個基礎元素，
/// 它們都將會被惰性計算。
@inlinable
public func map<U>(_ transform: @escaping (Elements.Element) -> U) -> LazyMapSequence<Self.Elements, U> {
return LazyMapSequence(_base: self.elements, transform: transform)
}
}
複製程式碼

這樣的神奇來自這些獨特型別的內部實現。例如，如果我們看一下LazyMapSequence 和LazyFilterSequence ，我們可以看到它們只不過是常規的Sequences ，它儲存一個操作並僅在迭代時應用它們的對應的立刻生效的方法：

// _base 是原始的 Sequence
extension LazyMapSequence.Iterator: IteratorProtocol, Sequence {
@inlinable
public mutating func next() -> Element? {
return _base.next().map(_transform)
}
}
複製程式碼

extension LazyFilterSequence.Iterator: IteratorProtocol, Sequence {
@inlinable
public mutating func next() -> Element? {
while let n = _base.next() {
if _predicate(n) {
return n
}
}
return nil
}
}
複製程式碼

`LazyCollection` 的效能困境

如果文章在這裡結束的話會很好，但重要的是要知道惰性序列其實是有缺陷 — 特別是當底層型別是Collection 時。

在最開始的例子中，我們的方法獲得了滿足某個條件的前三個地址。通過將惰性操作連結在一起，這也可以簡化為單行函式：

let homeAddresses = allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)
複製程式碼

但是，看看這個特定的例子與直接執行相比表現如何：

allAddresses.filter { $0.identifier == "HOME" }.prefix(3) // ~0.11 secs
Array(allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)) // ~0.22 secs
複製程式碼

即使找到三個地址後lazy 版本就會立刻停止，但它的執行速度卻反而是急迫版本的兩倍！

不幸的原因來自於Sequences 和Collections 之間的細微差別。擷取Sequence 的頭部元素就像將所需元素移動到單獨的Array 一樣簡單，但對Collections 的切片操作卻需要知道所需切片的結束位 的索引：

public func prefix(_ maxLength: Int) -> SubSequence {
_precondition(maxLength >= 0, "Can't take a prefix of negative length from a collection")
let end = index(startIndex, offsetBy: maxLength, limitedBy: endIndex) ?? endIndex
return self[startIndex..<end]
}

@inlinable
public subscript(bounds: Range<Index>) -> Slice<Self> {
_failEarlyRangeCheck(bounds, bounds: startIndex..<endIndex)
return Slice(base: self, bounds: bounds)
}
複製程式碼

問題是在Collection 相關術語中，endIndex 不是最後一個元素的索引，而是最後一個元素（index(startIndex, offsetBy:maxLength) ）之後的索引。對於我們的惰性filter 函式來說，這意味著為了切割獲得前三個家庭地址，我們必須找到四個家庭地址 — 它們甚至可能不存在。

這篇文件certain lazy types 說明了這個問題：

/// - 注意：獲取 `endIndex`、獲取 `last` 以及
///任何依賴 `endIndex` 的方法或者是
///依賴於 collection 頭部符合條件的元素個數進行移動的方法，
///都可能無法匹配 `Collection` 協議保證的效能。
///因此要知道，對於 `${Self}` 例項的普通操作
///可能並不只有文件上描述的複雜度。
public struct LazyPrefixWhileCollection<Base: Collection> {
複製程式碼

更糟糕的是，因為一個Slice 只是原始Collection 的一個視窗，所以將它轉換為Array 需要呼叫使用了惰性 filter 方法的Collection 的count 屬性的函式 — 但是因為lazy.filter(_:) 操作不符合RandomAccessCollection 協議，count 只能通過遍歷整個Collection 來找到。

由於 Lazy Sequence 缺少快取，這導致整個過濾/切片過程再次發生。因此，如果第四個元素不存在或者與第三個元素相距太遠，那麼lazy 版本的執行速度將比原始版本差兩倍。

好訊息是這種情況可以被避免 — 如果你不確定你的惰性操作是否會在合理的時間內執行，你可以通過將結果視為Sequence 來保證效率。雖然這樣失去BidirectionalCollection 所具有的反向遍歷功能，但保證了前向操作將再次快速。

let sequence: AnySequence = allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)
let result = Array(sequence) // ~0.004 秒！
複製程式碼

Conclusion

使用lazy 物件可以讓你快速編寫高效能、複雜的東西 — 代價是需要了解 Swift 內部機制以防止出現重大問題。像所有功能一樣，它們有巨大的優點也有等同的缺點，在這種情況下，需要了解Sequences 和Collections 之間的主要區別，汲取它們中的最佳功能來使用。一旦掌握，對映得到特定元素，將變得非常簡單和直觀。

在 Twitter 上關注我 —@rockthebruno，如果你想分享任何的更正或者建議，請告知我。

[譯] Swift 中的惰性序列及其原理

這為什麼能生效？

LazyCollection 的效能困境

Conclusion

您可能也會喜歡…

`LazyCollection` 的效能困境