ios - Swift 函数执行时间测量问题

Question

我有两个函数:

extension Array where Element: Hashable {
    func uniqueOrderly() -> [Element] {
        let startTime = CFAbsoluteTimeGetCurrent()
        var set = Set<Element>()
        var array = [Element]()
        for element in self {
            if set.contains(element) {
                continue
            }
            set.insert(element)
            array.append(element)
        }
        let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time for uniqueOrderly: \(timeElapsed)")
        return array
    }
}

第二个:

public extension Sequence where Element: Equatable {
    func unique() -> [Element] {
        let startTime = CFAbsoluteTimeGetCurrent()
        var unique: [Element] {
            return reduce(into: []) {
                unique, x in
                if !unique.contains(x) {
                    unique.append(x)
                }
            }
        }
        let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time for unique: \(timeElapsed)")
        return unique
    }
}

我正在对数组进行函数执行时间测量。

即:

let arrayToFilter = [1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1,1,2,4,6,1,2,5,7,9,3,3,1]

实际的函数调用和结果是这样的:

arrayToFilter.unique() //Time for unique: 0.00012195110321044922
arrayToFilter.uniqueOrderly() Time for uniqueOrderly: 0.02329099178314209

但是当我改变调用函数的顺序时，我的 unique() 函数显示出可怕的时间测量结果。

arrayToFilter.uniqueOrderly() //Time for uniqueOrderly: 0.0013059377670288086
arrayToFilter.unique() //Time for unique: 8.940696716308594e-06

所以我的问题是为什么我会遇到这种情况，不同的函数调用顺序？此外，当我在 for 循环中运行这些测试时，测量结果大不相同。 (大约 +- 1 秒)

所有测量都是在 playground 和真实的 iOS 应用程序中使用发布build设置(在模拟器上)完成的。

测试规范:

Xcode 版本 10.1

swift 4.2

Answer 1

你的 unique()实现在计算 unique 之前计算耗时. unique是一个计算变量，在访问时进行计算。

你的 uniqueOrderly()实现仍将比 unique() 慢对于像这样的相当短的列表，因为与几乎总是命中前几个元素的线性搜索相比，插入到集合中是昂贵的。

至于排序问题，这几乎可以肯定是您测试它的方式造成的。微观分析非常具有挑战性。我通过将每个放入自己的 .swift 来测试这些文件并以 swift -O <file> 运行.但是，如果我按照您的方式将它们放在同一个文件中，并修复 unique()实际计时它的事件，然后运行时时间非常一致 swift -O <file> :

Time for uniqueOrderly: 1.800060272216797e-05
[1, 2, 4, 6, 5, 7, 9, 3]
Time for unique: 2.0265579223632812e-06
[1, 2, 4, 6, 5, 7, 9, 3]

Time for unique: 2.002716064453125e-05
[1, 2, 4, 6, 5, 7, 9, 3]
Time for uniqueOrderly: 2.9802322387695312e-06
[1, 2, 4, 6, 5, 7, 9, 3]

经过更多测试后，我怀疑这些差异部分是内存分配(内存是从操作系统中分块获取的，因此第一个分配器比第二个分配器付出更大的代价)和 L1 缓存。如果您对两个不同的数组(指向内存缓存)进行排序，几乎所有差异都会消失。但是这个算法对数组的构成也非常敏感，因为它有很多重复项。

无论如何，这种微优化是没有意义的。你整天都在追鬼。很难在微小的数据 block 上对微小的代码片段进行性能测试，并以适用于实际使用的方式对其进行优化。至少，您需要更多、更大的数组并在许多不同类型的分布上进行测试(大量重复与极少重复)。您必须在 Playgrounds 之外进行测试，并且必须使用优化器。