arrays - joined() 还是 flatMap(_ :) perform better in 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{$0}

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

Answer 1

TL;博士

如果只是展平二维数组(没有应用任何转换或分隔符，请参阅 @dfri's answer 了解有关该方面的更多信息)，array.flatMap{$0}和 Array(array.joined())两者在概念上是相同的，并且具有相似的性能。

---

flatMap(_:) 之间的主要区别和 joined() (请注意，这不是一种新方法，它有 just been renamed from flatten() )是 joined()总是延迟应用(对于数组，它返回一个特殊的 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(_:)将在找到匹配项后停止迭代，只有前两个内部数组必须“展平”才能找到元素 8来自二维数组。虽然，作为@dfri correctly notes below , 你也可以懒惰地申请 flatMap(_:)通过使用 LazySequence/LazyCollection – 可以通过 lazy 创建属性(property)。这对于延迟应用转换和展平给定的 2D 序列来说是理想的。

在 joined() 的情况下完全迭代，它在概念上与使用 flatMap{$0} 没有什么不同.因此，这些都是展平二维数组的有效(并且概念上相同)方法:

array2D.joined().map{$0}

Array(array2D.joined())

array2D.flatMap{$0}

---

在性能方面， 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 , 它用于迭代二维序列的展平内容(这将在使用 map(_:) 或 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是基本二维序列，_inner是内部序列之一的当前迭代器，_fastPath & _slowPath是对编译器的提示，以帮助进行分支预测。

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

所以，性能方面，Array(array.joined())和 array.flatMap{$0}两者具有相同的时间复杂度。

如果我们在调试版本 (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{$0} // 0.00744s
}

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

benchmark {
    _ = arr.joined().map{$0} // 1.421s
}

flatMap(_:)似乎是最快的。我怀疑 joined()变慢可能是由于 FlattenIterator 中发生的分支所致(尽管对编译器的提示将此成本降至最低)——尽管这就是为什么 map(_:)太慢了，我不太确定。肯定有兴趣知道是否还有其他人对此有更多了解。

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

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

benchmark {
    let result = arr.flatMap{$0} // 0.0910s
    print(result.count)
}

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

benchmark {
    let result = arr.joined().map{$0} // 0.149s
    print(result.count)
}

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