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

栏目: Swift · 发布时间: 5年前

内容简介:如果你往数组中添加很多元素,你可能会发现:使用首先,让我们看一下数组的存储策略。如果你创建一个包含四个元素的数组,Swift 将会分配足够的内存去存储这仅有的4个元素。所以,数组的现在,你想去添加第五个元素。但数组并没有足够的长度去添加它,所以数组需要寻找一块足够存放五个元素的内存,然后将数组的4个元素拷贝过去,最后再拼接第五个元素。它的时间复杂度是O(n)。

如果你往数组中添加很多元素,你可能会发现:使用 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 的几何增长策略。

原文链接


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

人月神话

人月神话

[美] 弗雷德里克·布鲁克斯 / 汪颖 / 清华大学出版社 / 2002-11 / 29.80元

作者为人们管理复杂项目提供了颇具洞察力的见解,既有很多发人深省的观点,也有大量的软件工程实践。书中的内容来自布鲁克斯在IBM公司System 360家族和OS 360中的项目管理经验。初版的20年后,布鲁克斯重新审视了他原先的观点,增加了一些新的想法和建议。新增加的章节包括:原著中一些核心观点的精华;在经过了一个时代以后,Brooks博士对原先观点新的认识;1986年的经典文章《没有银弹》;对19......一起来看看 《人月神话》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具