join() 或 flatMap(_:) 在 Swift 3 中表现更好吗? [英] Does joined() or flatMap(_:) perform better in Swift 3?

问题描述

我很好奇 joined() 和 .flatMap(_:) 在扁平化多维数组方面的性能特征:

I'm curious about the performance characteristics of joined() and .flatMap(_:) in flattening a multidimensional array:

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].为了性能，我应该更喜欢一种吗?另外，有没有更易读的方法来编写调用?

They both flatten the nested array into [1, 2, 3, 4, 5, 6, 7, 8, 9]. Should I prefer one over the other for performance? Also, is there a more readable way to write the calls?

推荐答案

TL;博士

当涉及扁平化二维数组时(没有应用任何转换或分隔符，请参阅 @dfri 的回答了解更多信息关于这方面)，array.flatMap{$0} 和 Array(array.joined()) 在概念上是相同的，并且具有相似的性能.

TL; DR

When it comes just to flattening 2D arrays (without any transformations or separators applied, see @dfri's answer for more info about that aspect), array.flatMap{$0} and Array(array.joined()) are both conceptually the same and have similar performance.

flatMap(_:) 和 joined() 的主要区别(注意这不是一个新方法，它有 刚刚从 flatten()) 是 joined() 总是懒惰地应用(对于数组，它返回一个特殊的 FlattenBidirectionalCollection).

The main difference between flatMap(_:) and joined() (note that this isn't a new method, it has just been renamed from flatten()) is that joined() is always lazily applied (for arrays, it returns a special FlattenBidirectionalCollection<Base>).

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

Therefore in terms of performance, it makes sense to use joined() over flatMap(_:) in situations where you only want to iterate over part of a flattened sequence (without applying any transformations). For example:

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 正确注意下面，您还可以通过使用 LazySequence/LazyCollection 延迟应用 flatMap(_:) - 其中可以通过 lazy 属性.这对于懒惰地应用转换和转换是理想的.展平给定的二维序列.

Because joined() is lazily applied & contains(_:) will stop iterating upon finding a match, only the first two inner arrays will have to be 'flattened' to find the element 8 from the 2D array. Although, as @dfri correctly notes below, you are also able to lazily apply flatMap(_:) through the use of a LazySequence/LazyCollection – which can be created through the lazy property. This would be ideal for lazily applying both a transformation & flattening a given 2D sequence.

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

In cases where joined() is iterated fully through, it is conceptually no different from using flatMap{$0}. Therefore, these are all valid (and conceptually identical) ways of flattening a 2D array:

array2D.joined().map{$0}

Array(array2D.joined())

array2D.flatMap{$0}

<小时>

在性能方面，flatMap(_:) 被记录为具有以下时间复杂度:

---

In terms of performance, flatMap(_:) is documented as having a time-complexity of:

O(m + n)，其中m是这个序列的长度，n是结果的长度

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

这是因为它的实现 就是:

  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 是二维序列的长度.

As append(contentsOf:) has a time-complexity of O(n), where n is the length of sequence to append, we get an overall time-complexity of O(m + n), where m will be total length of all sequences appended, and n is the length of the 2D sequence.

当谈到 joined() 时，没有记录的时间复杂性，因为它被懒惰地应用.但是，要考虑的主要源代码是 FlattenIterator 的实现，用于迭代 2D 序列的扁平化内容(这将在使用 map(_:) 或 Array(_:) 初始化器和 joined()).

When it comes to joined(), there is no documented time-complexity, as it is lazily applied. However, the main bit of source code to consider is 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(_:) initialiser with 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 是对编译器的提示，以帮助进行分支预测.

Here _base is the base 2D sequence, _inner is the current iterator from one of the inner sequences, and _fastPath & _slowPath are hints to the compiler to aid with branch prediction.

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

Assuming I'm interpreting this code correctly & the full sequence is iterated through, this also has a time complexity of O(m + n), where m is the length of the sequence, and n is the length of the result. This is because it goes through each outer iterator and each inner iterator to get the flattened elements.

因此，在性能方面，Array(array.joined()) 和 array.flatMap{$0} 都具有相同的时间复杂度.

So, performance wise, Array(array.joined()) and array.flatMap{$0} both have the same time complexity.

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

If we run a quick benchmark in a debug build (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(_:) appears to be the fastest. I suspect that joined() being slower could be due to the branching that occurs within the FlattenIterator (although the hints to the compiler minimise this cost) – although just why map(_:) is so slow, I'm not too sure. Would certainly be interested to know if anyone else knows more about this.

然而，在优化的构建中，编译器能够优化掉这个巨大的性能差异；尽管 flatMap(_:) 仍然最快几分之一秒:

However, in an optimised build, the compiler is able to optimise away this big performance difference; giving all three options comparable speed, although flatMap(_:) is still fastest by a fraction of a second:

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)
}

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

(Note that the order in which the tests are performed can affect the results – both of above results are an average from performing the tests in the various different orders)

这篇关于join() 或 flatMap(_:) 在 Swift 3 中表现更好吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！