Swift中使用 map 和 filter 高阶函数的惰性序列及其原理

使用 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
let lazyMap = Array(1...1000).lazy.filter { $0 % 2 == 0 }.map { $0 * 2 }
print(lazyMap) // LazyMapCollection
// 在这种情况下，第一个泛型参数是惰性操作内部的 Collection，而第二个参数是 map 操作的转换函数。
复制代码

看看 Swift 的源代码，我们可以通过这样一个事实，看到其非急迫性，即这些方法除了返回一个新类型之外，实际上并没有做任何事情：

（我将使用 LazySequence 而不是 LazyCollections 的代码作为例子，因为他们在特性上十分相似。如果你不理解 Sequences 如何工作，那么看一下 Apple 的这篇文章吧。）

extension LazySequenceProtocol {
    /// 返回一个 `LazyMapSequence` 类型来替代 `Sequence`。
    /// 结果每次被 `transform` 方法读取一个基础元素，
    /// 它们都将会被惰性计算。
    @inlinable
    public func map(_ transform: @escaping (Elements.Element) -> U) -> LazyMapSequence {
        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.. Slice {

    _failEarlyRangeCheck(bounds, bounds: startIndex..