在Swift 3中，joined（）或flatMap（_ :)会更好吗？ [英] Does joined() or 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}
它们将嵌套的数组变成 [1,2,3,4,5， 6，7，8，9] 。我应该比其他人更喜欢表演吗？另外，是否有更可读的方式来编写调用？ 解决方案
DR
当只是平面化2D数组（没有应用任何转换或分隔符时，请参阅 @ dfri的答案以获得更多关于该方面的信息）， array.flatMap {$ 0} 和 Array（array.joined（ ）在概念上都是相同的，并且具有相似的性能。
code> flatMap（_：）和 joined（）（注意这不是一个新的方法，它有刚从 FlattenBidirectionalCollection< Base> ） p>
因此就performa而言nce，在你只想迭代的情况下，使用 joined（） over flatMap（_：）在平坦序列的一部分上（不应用任何转换）。例如：
let array2D = [[2,3]，[8,10]，[9,5]，[ （8）{
print（contains 8）
} else {
print（不包含8）
}
因为加入）懒惰地应用& contains（_：）将在找到匹配时停止迭代，只有前两个内部数组必须被拼合才能找到元素 8 来自二维数组。虽然，正如 @dfri正确注意下面的，你也可以通过使用 LazySequence 来延迟应用 flatMap（_：） > / LazyCollection - 可以通过 lazy 属性。这对于懒惰地应用转换&展开一个给定的2D序列。
在 joined（）完全遍历的情况下，概念上没有区别从使用 flatMap {$ 0} 。因此，这些都是有效的（并且在概念上相同）平展2D数组的方式：
array2D.joined（）。map {
$ / code>
Array（array2D.joined（））
<
$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ pre>
在性能方面， flatMap（_：）是记录为具有以下时间复杂性：
O（m + n），其中m是这个序列的长度，n是结果的长度。
这是因为它的实现是s暗示：
$ b $ pre $ public func flatMap< SegmentOfResult：Sequence>（
_ transform：（$ {GElement}）throws - > SegmentOfResult
）rethrows - > [SegmentOfResult。$ {GElement}] {
var result：[SegmentOfResult。$ {GElement}] = []
for self {
result.append（contentsOf：try transform（element ））
}
返回结果
}
}
As append（contentsOf：） 具有O（n）的时间复杂度，其中n是要追加的序列的长度，我们得到总体时间复杂度为O（m + n），其中m是所有序列的总长度，n是2D序列的长度。
当它来到 joined（），没有记录的时间复杂度，因为它被延迟应用。不过，要考虑的主要源代码是 FlattenIterator 的实现，它用于迭代2D序列的展平内容（这将在使用 map（_：） 或 Array（_：） c）>
public mutating func next（） - > Base.Element.Iterator.Element？ {
if _fastPath（_inner！= nil）{
let ret = _inner！.next（）
if _fastPath（ret！= nil）{
返回ret
让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（\（name ??closure）的基准值为\（d1 ）秒）
}
let arr = [[Int]]（重复：[Int]（重复：0，count：1000），count：1000）
基准{
_ = arr.flatMap {$ 0} // 0.00744s
}
基准{
_ = Array（arr.joined（）） // 0.525s
}
基准{
_ = arr.joined（）。map {$ 0} // 1.421 s
flatMap（_：）似乎是最快的。我怀疑 joined（）变慢的原因可能是由于 FlattenIterator 内发生了分支（尽管提示编译器最小化这个成本） - 虽然为什么 map（_：）太慢了，我不太确定。然而，在一个优化的版本中，编译器能够优化掉这种巨大的性能差异;但是，虽然 flatMap（_：）仍然是最快的，但速度还是可比的：
<$
$ b基准{$ b} let arr = [[Int]]（重复：[Int]（重复：0，count：10000），count：1000） $ b let result = arr.flatMap {$ 0} // 0.0910s
print（result.count）
}
基准{
let result = Array（arr .joined（））// 0.118s
print（result.count）
}
基准{
let result = arr.joined（）。map {$ 0 } // 0.149s
print（result.count）
}
（请注意，执行测试的顺序可能会影响结果 - 上述两个结果均是以各种不同的顺序执行测试的平均值）。
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}
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; 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.
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>).
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")
}
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.
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}
In terms of performance, flatMap(_:) is documented as having a time-complexity of:
O(m + n), where m is the length of this sequence and n is the length of the result
This is because its implementation is simply:
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
}
}
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.
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
}
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.
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.
So, performance wise, Array(array.joined()) and array.flatMap{$0} both have the same time complexity.
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(_:) 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.
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)
这篇关于在Swift 3中，joined（）或flatMap（_ :)会更好吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
