Swift 中的 Array 性能比较: append vs reserveCapacity(译)

如果你往数组中添加很多元素，你可能会发现：使用 reserveCapacity() 函数提前告诉 Swift 你需要多大的长度，代码性能会更好。然而，对它的使用你需要格外小心，因为它也可能使你的代码变得非常非常慢。

首先，让我们看一下数组的存储策略。如果你创建一个包含四个元素的数组，Swift 将会分配足够的内存去存储这仅有的4个元素。所以，数组的 count 和 capacity 都是4。

现在，你想去添加第五个元素。但数组并没有足够的长度去添加它，所以数组需要寻找一块足够存放五个元素的内存，然后将数组的4个元素拷贝过去，最后再拼接第五个元素。它的时间复杂度是O(n)。

为了避免不断重新分配内存，Swift 对数组的容量采用了一种几何增加模式(a geometric allocation pattern)。这是一种非常好的方式，它成倍的增加数组的容量避免多次重新分配内存的问题。当你在容量为4的数组中添加第五个元素的时候，Swift 将会将数组的长度增加为 8 。每当你超出数组的长度范围，它将会以32、64等成倍的依次增加。

如果你知道你将要存储512个元素，你可以使用 reserveCapacity() 函数来通知 Swift。然后 Swift 会立刻分配一块可以存储512个元素的内存给数组，而不是创建一个小数组，再多次重新分配内存。

示例：

var randomNumbers = [Int]()
randomNumbers.reserveCapacity(512)

for _ in 1...512 {
    randomNumbers.append(Int.random(in: 1...10))
}
复制代码

由于 reserveCapacity() 的时间复杂度也是 O(n) ，所以你应该在数组为空的时候调用它。

但是这有一个非常重要的点：你需要确定你的数组增长策略比 Swift 的好。记住， Swift 使用几何增长策略，所以调整数组尺寸的次数会随着数组容量的增加而减少，这就意味着它会将时间复杂度平摊为O(1)。

Tip：平摊(amortization): 是 程序员 选择用来描述算法随时间变化的行为的术语。虽然 append() 在不得不扩充数组的容量的时候时间复杂度是O(n) ；当你有足够的容量存储的时候，它的时间复杂度是O(1)。随着数组容量的增大，O(1) 操作将大大超过O(n)操作。因此我们可以认为 append() 的时间复杂度是O(1)。

当 append() 平摊为一个常量运行时间的时候， reserveCapacity() 也是如此。之前的用法将会使你的代码变得更慢而不是更快。

例如，假设我们想要追踪抽奖的幸运数字。我们可以从一个空数组开始：

var allLuckyNumbers = [Int]()
复制代码

下一步，我们可以编写一个能够选择10个数字的函数，以便我们可以在本周的彩票中进行游戏。这个函数知道我们将要生成10个数字，我们可以使用 reserveCapacity() 来确定我们的数组可以存放10个数字。

func pickLuckyNumbers() {
    let newSize = allLuckyNumbers.count + 10
    allLuckyNumbers.reserveCapacity(newSize)

    for _ in 1...10 {
        allLuckyNumbers.append(Int.random(in: 0...50))
    }
}
复制代码

目前为止还不错： reserveCapacity() 的时间复杂度为O(n)，并且他分配了足够的内存来存储。

但是人算不如天算，你可能提前想去生成全年的幸运数字。

for _ in 1...52 {
    pickLuckyNumbers()
}
复制代码

这个循环也是O(n)，现在你摊上事了：循环里面嵌套循环，时间复杂度为O(n²)。

即使使用 reserveCapacity() 可以让你的代码变快，但是在这种情况下它将使你的代码变慢：Swift 将会重复调整数组的容量去添加十多个元素。另一方面，如果你移除了 reserveCapacity() , Swift将恢复其几何增长策略，并最终分配比所需更多的容量。这将会比重复调整数组的容量快很多。

判断该使用的哪一个的方法很简单：如果你调用 reserveCapacity() 一次，那么你就应该使用它，但是如果你可能会调用它多次，那么你应该实现自己的增长策略或者使用 Swift 的几何增长策略。

原文链接