arrays - 是否join()或flatMap(_ :) perform better in Swift 3?

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

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

它们都将嵌套的array展平为[1, 2, 3, 4, 5, 6, 7, 8, 9]。我是否应该选择一个而不是另一个来提高性能？另外，是否有更可读的方式来编写调用？

最佳答案

TL;博士

仅涉及展平2D数组(不应用任何转换或分隔符，请参阅@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(_:)在找到匹配项后将停止迭代，因此只有“前两个内部数组”必须被“展平”才能从2D数组中找到元素8。虽然，作为@dfri correctly notes below，您也可以通过使用flatMap(_:)/LazySequence懒惰地应用LazyCollection，这可以通过 lazy 属性创建。这对于延迟应用变换和展平给定的2D序列非常理想。

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

array2D.joined().map{$0}

Array(array2D.joined())

array2D.flatMap{$0}

就性能而言， flatMap(_:) is documented具有以下时间复杂度:

这是因为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是2D序列的长度。

对于joined()，没有记录的时间复杂性，因为它是惰性应用的。但是，要考虑的源代码的主要部分是the implementation of FlattenIterator ，它用于对2D序列的平坦内容进行迭代(这将在将 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是基本的2D序列，_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)
}

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

JOINED

arrays - 是否join()或flatMap(_ :) perform better in Swift 3?