如何在Swift中高效地向大数组追加项？

Question

我正在进行一个涉及非常大的动态数组的Swift项目。 我遇到的问题是，每个操作所需的时间比前一个更长。 我相信这个问题是由于向数组附加元素引起的，因为我在一个简单的测试中只向一个大型数组附加元素也遇到了同样的问题。

我的测试代码：

import Foundation

func measureExecution(elements: Int, appendedValue: Int) -> Void {
    var array = Array(0...elements)
    //array.reserveCapacity(elements)
    
    let start = DispatchTime.now()
    array.append(appendedValue)
    let end = DispatchTime.now()
    print(Double(end.uptimeNanoseconds - start.uptimeNanoseconds) / 1_000_000_000)
}

for i in 0...100 {
    measureExecution(elements: i*10000, appendedValue: 1)
}

这个程序尝试在10000到1000000之间测试100个不同的数组大小，计时向数组末尾添加一个项目所需的时间。据我了解，Swift数组是动态数组，将以几何方式重新分配内存（每次需要重新分配时都会分配更多的内存），苹果的文档说平均而言将单个元素附加到数组是O(1)操作，即调用append(_ :)方法（source）。因此，我认为内存分配并不是引起问题的原因。

然而，数组长度与附加元素所需时间之间存在线性关系。我绘制了一堆数组长度的时间图表，除了一些离群值外，它很清楚地是O(n)。我还使用保留容量运行了相同的测试（在代码块中已注释），以确认内存分配不是问题，结果几乎相同： 如何高效地将元素添加到大型数组的末尾（最好不使用reserveCapacity）？

- 42nd

---

看一下 Swift Collections Package 中的 Deque，它可能适合你的情况。 - Alladinian

我无法重现你的结果。你在什么硬件上运行这个程序？我正在MBP上测试，并且只是将其作为命令行应用在Xcode中运行，未经过优化。我发现追加时间保持平稳，范围从7x10^-7到8x10^-6。 - Rob Napier

我会研究Deque；那看起来很有前途。至于平台，我已经在Xcode playground、Mac和iPad上尝试了Swift Playgrounds，并且为了保持清醒，我还在Replit.com上进行了检查，它们给出了相同的结果。随着数组大小的增加，值在平台之间有所不同，但通常从千分之一秒逐渐增加到十分之一秒。如果您的计算机速度较快，您可能需要增加循环迭代次数或将i乘以的常数，因为效果显示得相对较慢。 - 42nd

X轴是什么？数组的基本大小（乘以10,000）？ - Alexander

是的。x轴上的每个单位都是通过for i in 0...100循环的一次迭代，因此它将比上一个数组长10,000个索引。 - 42nd

@Alladinian 我已经尝试过双端队列，但它似乎并没有明显提高性能。重新阅读了swift.org上的新闻稿，我认为Deque使得将值添加到数组开头与追加到末尾一样高效，但不会加快追加到末尾的速度（我是一个新手，所以我可能使用Deque不正确，但我相信这是事实）。 - 42nd

Answer 1

据我所知，Swift 数组会预先分配存储空间。每次填充数组的已分配存储空间时，它会将分配的空间加倍。这样你就不需要经常进行新的内存分配，也不会分配大量你不需要的空间。

数组类确实有一个 reserveCapacity(_:) 方法。如果你知道要存储多少元素，可以尝试使用该方法。

- Duncan C

---

我认为OP了解reserveCapacity，他们在他们的代码和图表中使用了它。 - Alexander