joined() 或 flatMap(_:) 在 Swift 3 中表现更好吗？

Question

我很好奇 joined() 和 .flatMap(_:) 在展平多维数组时的性能特征：

let array = [[1,2,3],[4,5,6],[7,8,9]]
let j = Array(array.joined())
let f = array.flatMap{[=11=]}

它们都将嵌套的 array 扁平化为 [1, 2, 3, 4, 5, 6, 7, 8, 9]。为了性能我应该更喜欢一个吗？另外，有没有更可读的方式来编写调用？

Answer 1

从Swiftdoc.org documentation of Array (Swift 3.0/dev)我们读到[强调我的]：

func flatMap<SegmentOfResult : Sequence>(_: @noescape (Element) throws -> SegmentOfResult)
Returns an array containing the concatenated results of calling the given transformation with each element of this sequence.

...

In fact, s.flatMap(transform) is equivalent to Array(s.map(transform).flatten()).

我们还可以看看 Swift 源代码中两者的实际实现（从中生成 Swiftdoc ...）

最值得注意的是后一个源文件，其中 flatMap 实现中使用的闭包 (transform) 不产生和可选值（就像这里的情况）都被描述为

/// Returns the concatenated results of mapping `transform` over
/// `self`.  Equivalent to 
///
///     self.map(transform).joined()

从上面（假设编译器可以很聪明 w.r.t。一个简单的 over self { [=19=] } transform），似乎在性能方面，这两个选择应该是等效的，但是 joined 确实，imo，更好地显示操作的意图。

除了语义上的意图之外，还有一个明显的用例，其中 joined 比 flatMap 更可取（并且不完全可比）：使用 joined 和 init(separator:) 使用分隔符连接序列的初始值设定项：

let array = [[1,2,3],[4,5,6],[7,8,9]]
let j = Array(array.joined(separator: [42]))

print(j) // [1, 2, 3, 42, 4, 5, 6, 42, 7, 8, 9]

使用 flatMap 的相应结果并不是那么整洁，因为我们明确需要在操作 flatMap 之后删除最后的附加分隔符 （两个不同的用例，有或没有尾随分隔符）

let f = Array(array.flatMap{ [=13=] + [42] }.dropLast()) print(f) // [1, 2, 3, 42, 4, 5, 6, 42, 7, 8, 9]

另请参阅 Erica Sadun 讨论 flatMap 与 flatten() 的有点过时的 post（注意：joined() 在 [=72] 中被命名为 flatten() =] < 3).

Erica Sadun- Beta 6: flatten #swiftlang

Answer 2

TL;博士

当仅涉及展平二维数组时（没有应用任何转换或分隔符，请参阅了解有关该方面的更多信息），array.flatMap{[=18=]} 和 Array(array.joined()) 在概念上都是相同且具有相似的性能。

flatMap(_:)和joined()的主要区别（注意这不是新方法，它有just been renamed from flatten()) is that joined() is always lazily applied (for arrays, it returns a special FlattenBidirectionalCollection<Base>）。

因此，就性能而言，在您只想迭代展平序列的一部分（不应用任何转换）的情况下，使用 joined() 而不是 flatMap(_:) 是有意义的。例如：

let array2D = [[2, 3], [8, 10], [9, 5], [4, 8]]

if array2D.joined().contains(8) {
    print("contains 8")
} else {
    print("doesn't contain 8")
}

因为 joined() 被延迟应用 & contains(_:) 将在找到匹配项时停止迭代，只有前两个内部数组必须是 'flattened' 才能找到元素 8 来自二维数组。虽然，如, you are also able to lazily apply flatMap(_:) through the use of a LazySequence/LazyCollection – which can be created through the lazy属性。这对于懒惰地应用转换和展平给定的 2D 序列来说是理想的。

在完全迭代 joined() 的情况下，它在概念上与使用 flatMap{[=35=]} 没有区别。因此，这些都是展平二维数组的有效（并且概念上相同）方法：

array2D.joined().map{[=11=]}

Array(array2D.joined())

array2D.flatMap{[=13=]}

就性能而言，flatMap(_:) is documented 的时间复杂度为：

O(m + n), where m is the length of this sequence and n is the length of the result

这是因为 its implementation 就是：

  public func flatMap<SegmentOfResult : Sequence>(
    _ transform: (${GElement}) throws -> SegmentOfResult
  ) rethrows -> [SegmentOfResult.${GElement}] {
    var result: [SegmentOfResult.${GElement}] = []
    for element in self {
      result.append(contentsOf: try transform(element))
    }
    return result
  }
}

由于 append(contentsOf:) 的时间复杂度为 O(n)，其中 n 是要追加的序列的长度，我们得到的总体时间复杂度为 O(m + n)，其中 m 将是附加的所有序列的总长度，n 是二维序列的长度。

当谈到 joined() 时，没有记录时间复杂性，因为它是延迟应用的。但是，要考虑的主要源代码是 the implementation of FlattenIterator, which is used to iterate over the flattened contents of a 2D sequence (which will occur upon using map(_:) or the Array(_:) 初始化程序 joined()).

  public mutating func next() -> Base.Element.Iterator.Element? {
    repeat {
      if _fastPath(_inner != nil) {
        let ret = _inner!.next()
        if _fastPath(ret != nil) {
          return ret
        }
      }
      let s = _base.next()
      if _slowPath(s == nil) {
        return nil
      }
      _inner = s!.makeIterator()
    }
    while true
  }

这里 _base 是基本的 2D 序列，_inner 是来自内部序列之一的当前迭代器，_fastPath & _slowPath 是对编译器的提示帮助进行分支预测。

假设我正确地解释了这段代码并且遍历了整个序列，这也具有 O(m + n) 的时间复杂度，其中 m 是序列的长度，n 是结果。这是因为它通过每个外部迭代器和每个内部迭代器来获取扁平元素。

因此，性能方面，Array(array.joined()) 和 array.flatMap{[=18=]} 具有相同的时间复杂度。

如果我们运行在调试版本 (Swift 3.1) 中进行快速基准测试：

import QuartzCore

func benchmark(repeatCount:Int = 1, name:String? = nil, closure:() -> ()) {
    let d = CACurrentMediaTime()
    for _ in 0..<repeatCount {
        closure()
    }
    let d1 = CACurrentMediaTime()-d
    print("Benchmark of \(name ?? "closure") took \(d1) seconds")
}

let arr = [[Int]](repeating: [Int](repeating: 0, count: 1000), count: 1000)

benchmark {
    _ = arr.flatMap{[=16=]} // 0.00744s
}

benchmark {
    _ = Array(arr.joined()) // 0.525s
}

benchmark {
    _ = arr.joined().map{[=16=]} // 1.421s
}

flatMap(_:) 似乎是最快的。我怀疑 joined() 变慢可能是由于 FlattenIterator 中发生的分支（尽管编译器的提示最小化了这个成本）——尽管 map(_:) 这么慢的原因，我不太确定。肯定有兴趣知道是否还有其他人对此有更多了解。

然而，在优化构建中，编译器能够优化掉这个巨大的性能差异；给所有三个选项相当的速度，尽管 flatMap(_:) 仍然是最快的几分之一秒：

let arr = [[Int]](repeating: [Int](repeating: 0, count: 10000), count: 1000)

benchmark {
    let result = arr.flatMap{[=17=]} // 0.0910s
    print(result.count)
}

benchmark {
    let result = Array(arr.joined()) // 0.118s
    print(result.count)
}

benchmark {
    let result = arr.joined().map{[=17=]} // 0.149s
    print(result.count)
}

（请注意，执行测试的顺序会影响结果——以上两个结果都是以各种不同顺序执行测试的平均值）

joined() 或 flatMap(_:) 在 Swift 3 中表现更好吗？

Does joined() or flatMap(_:) perform better in Swift 3?

arrays

functional-programming

swift

swift3

TL;博士