Swift，计算排序算法的执行时间

Question

我需要计算2个不同算法的执行时间，然后根据执行时间确定推荐哪一个。目前我对算法和数据结构还不太熟悉，更不用说在Swift语言中了。

所以我进行了一些搜索，但是没有找到很多有用的信息。我确实找到了这个：

func printTimeElapsedWhenRunningCode(title:String, operation:()->()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print("Time elapsed for \(title): \(timeElapsed) s.")
}

这就是我实际想要测试的内容：

printTimeElapsedWhenRunningCode(title: "Merge Sort") {
    let newSort = mergeSort(sortArray)
}

我不确定这是否真正计算了我所需的内容。每次运行此代码时，都会得到不同的时间。我是否走在正确的道路上？

- Micheal

---

你是在哪里运行这段代码？不要使用游乐场。请使用完全优化的发布版本测试代码。 - rmaddy

我一直在Playground中进行所有操作。我将在帖子中添加更多信息。 - Micheal

不要在游乐场进行任何性能测试。 - rmaddy

这是一项作业，不是真实世界中的情况。我们被要求找到排序算法并测试执行效果。基本上，这个任务涉及到不同的排序算法。我只需要一些方法来展示算法的执行时间。 - Micheal

我已经开始了一个Swift控制台应用程序。我不需要使用playgrounds，这是一个好消息。 - Micheal

Answer 1

注意：在现实生活中最好找到一些已经建立的性能测试框架。正确地进行测试是很难的。

以下是一份不完整的清单，如果您自己进行测试，最好遵循这些步骤：

1. 对多次迭代求平均值，而不仅仅是一次。结果存在一些噪音的原因有很多。如果总运行时间少于0.1秒，则很可能完全不可靠。最好是至少1秒。此外，跟踪平均值以外的其他指标（如95％百分位数）也是有意义的。

2. 不要忽略循环内测试计算的结果。聪明的编译器可以优化掉未使用的结果并将其替换为类似无操作的东西。理想情况下，结果应对编译器不可预测。例如，在第i个迭代中，将排序列表的第i个（或（i％array.length）-th）元素添加到总和中，并在最后返回总和或打印它（显然在测量时间之外）。

3. 除非您试图测量该IO操作的性能，否则不要在测试算法内部进行任何打印/日志记录/IO操作。 IO非常慢。

4. 在主要“测试”迭代之前进行几次热身迭代。这是为了确保各种CPU缓存中可能存在的所有数据都在那里。没有预热，第一次运行和后续运行可能会有很大的差异。此外，如果您正在运行托管代码（例如JavaScript或Java或.Net），许多运行可能会强制VM重新编译带有一些更好优化的代码。在这种情况下，您可能需要先运行几千个“预热”迭代来强制它。一些更好的测试框架运行批处理，直到不同批次之间的时间变得稳定。

5. 将代码与将在生产中使用的相同级别的优化进行比较。今天的编译器可以非常聪明地进行优化，如果允许它们，“调试”版本可以轻松比“发布”版本慢10倍。

对于排序算法，有一些特定的事情需要记住，其中主要是：在不同的测试数组上进行几次测量

1. 尝试不同大小的数组，从几个元素到数百万个元素。今天的内存访问是非常复杂的。不同的算法具有不同的内存使用模式，这可能会在不同的大小上极大地影响性能。

2. 检查不同的数据。某些排序算法具有病态的坏情况，而某些则没有。有些可能在半排序数据上特别快，而有些则无法利用它。至少使用一些随机数据。最好不仅使用随机数据。

- SergGr

Answer 2

如果你想衡量性能，请使用单元测试的measure { ... }代码块作为起点，因为它会运行多次并计算经过的时间、标准偏差等等。

我还建议：

- 使用一种相对高效的类型来测试 (例如 [Int] 而不是 [String] ), 这样可以更专注于排序速度而非比较速度； - 进行可观察的排序测试（例如一个大数组）并重复多次进行排序； - 最后对结果进行简单处理，如此将即使您测试了优化构建，也不会有风险将一些生成但未被使用的代码优化掉。

但是，对于快速的性能测试，Xcode 单元测试非常简便。例如：

class MyAppTests: XCTestCase {

    let iterationCount = 1_000

    // build large array

    var array = (0 ..< 1_000).map { _ in Int.random(in: 0 ..< 1_000_000) }

    // test performance

    func testSortPerformance() {
        measure {
            for _ in 0 ..< iterationCount {
                let results = array.sorted()
                XCTAssert(!results.isEmpty)
            }
        }
    }

    func testBubbleSortPerformance() {
        measure {
            for _ in 0 ..< iterationCount {
                let results = array.bubbleSorted()
                XCTAssert(!results.isEmpty)
            }
        }
    }
}

这将在报告导航器中产生以下结果：

或者在控制台中，您将看到详细信息：

/.../MyAppTests.swift:33: Test Case '-[MyAppTests.MyAppTests testBubbleSortPerformance]' measured [Time, seconds] average: 0.603, relative standard deviation: 3.284%, values: [0.613748, 0.580443, 0.590879, 0.586842, 0.626791, 0.610288, 0.595295, 0.588713, 0.594823, 0.647156], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
/.../MyAppTests.swift:23: Test Case '-[MyAppTests.MyAppTests testSortPerformance]' measured [Time, seconds] average: 0.025, relative standard deviation: 13.393%, values: [0.033849, 0.026869, 0.022752, 0.023048, 0.023024, 0.022847, 0.023286, 0.023987, 0.023803, 0.022640], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100

顺便说一下，我可能也会测试排序算法本身，例如确保结果是递增的值，并且所有项目的总和仍然加起来：

func testBubbleSort() {
    let results = array.bubbleSorted()

    var previous = results[0]
    for index in 1 ..< results.count {
        let current = results[index]
        XCTAssertLessThanOrEqual(previous, current)
        previous = current
    }

    XCTAssertEqual(results.sum(), array.sum())
}

- Rob

---

我觉得这是目前为止最好的帮助，但我感觉对于我需要的东西来说，可能会变得非常复杂。我可能错了。这是我还没有涉及但计划要做的事情。我有一个包含9个整数的数组。我只需要使用任意两种排序方法将它们排序。然后我需要计算每个排序的执行时间。然后根据时间比较它们，哪个时间最短就推荐哪个。我只需要知道我提交的代码是否在简单层面上或正确方向上实现了我所需的功能。 - Micheal

你的方法是正确的，但是对一个包含9个整数的数组进行一次迭代测试不太可能产生具有统计学意义的结果，因此我建议使用更大的数组和更多的迭代。我还会让应用程序在基准测试之前达到静止状态。如果您像现在这样手动测试两个排序算法，请确保丢弃第一次迭代并尝试更改两个排序算法的顺序。但是使用一个包含9个项目的数组进行一次迭代的数据量不足以得出任何结论。 - Rob

这是一项课堂作业。我们被给定了一个包含9个整数的数组。然后选择两种排序算法，找到每个算法的代码。运行算法并计算执行时间。我是说自从问了这个问题以来，我已经学到了很多，并且想继续深入了解性能测试。 - Micheal