阅读 361

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

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

首先,让我们看一下数组的存储策略。如果你创建一个包含四个元素的数组,Swift 将会分配足够的内存去存储这仅有的4个元素。所以,数组的 countcapacity 都是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 的几何增长策略。

原文链接

关注下面的标签,发现更多相似文章
评论