我对多维数组的性能特征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]
。我应该优先选择一个而不是另一个吗?另外,是否有更可读的方式来编写呼叫?
仅涉及展平2D数组(不应用任何转换或分隔符,请参阅@dfri的答案以获取有关该方面的更多信息),array.flatMap{$0}
并且Array(array.joined())
在概念上都是相同的,并且具有相似的性能。
flatMap(_:)
和之间的主要区别joined()
(请注意,这不是一个新方法,它刚刚从改名了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
从2D数组中找到元素。尽管,如@dfri在下面正确指出的那样,您也可以flatMap(_:)
通过使用LazySequence
/来懒惰地应用LazyCollection
该lazy
属性,该属性可以创建/ 。这对于延迟应用变换和展平给定的2D序列非常理想。
在joined()
完全迭代的情况下,从概念上讲,它与使用并无区别flatMap{$0}
。因此,这些都是将2D数组展平的有效(且在概念上相同)的方法:
array2D.joined().map{$0}
Array(array2D.joined())
array2D.flatMap{$0}
就性能而言,flatMap(_:)
记录为具有以下时间复杂性:
O(m + n),其中m是此序列的长度,n是结果的长度
这是因为其实现很简单:
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()
,没有记录的时间复杂性,因为它是懒惰的。但是,要考虑的源代码的主要部分是的实现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)
}
(请注意,执行测试的顺序可能会影响结果-以上两个结果都是按不同顺序执行测试的平均值)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句