我想知道Swift内部是如何管理数组的? Apple's language guide只处理用法,不详细说明内部结构。
作为一名 Java 开发人员,我习惯于将“裸”数组视为非常静态且固定的数据结构。我知道在 Swift 中这不是真的。在 Swift 中,与 Java 不同,您可以改变数组的长度,还可以执行插入和删除操作。在 Java 中,我习惯于根据我想要使用该结构执行哪些操作来决定要使用哪种数据结构(简单数组、ArrayList、LinkedList 等),从而优化我的代码以获得更好的性能。
总之,我想知道数组在 Swift 中是如何实现的。它们在内部作为(双)链表进行管理吗?有没有什么可以与 Java 的 Collection Framework 相媲美的,以便调整以获得更好的性能?
最佳答案
您可以在 Swift 标准库中的上面的注释中找到有关 Array
的大量信息。要查看这一点,您可以在 Playground 中 cmd-opt-click Array
,或者您可以在非官方 SwiftDoc 中查看它。页。
转述其中的一些信息来回答您的问题:
在 Swift 中创建的数组将它们的值保存在连续的内存区域中。因此,您可以有效地将 Swift 数组传递到需要这种结构的 C API 中。
正如您所提到的,数组可以随着您向其附加值而增长,并且在某些时候,这意味着分配新的、更大的内存区域,并将以前的值复制到其中。正是由于这个原因,它指出像追加这样的操作可能是O(n)
——也就是说,执行追加操作的最坏情况时间与数组的当前大小(因为复制值所花费的时间)。
但是,当数组必须增加其存储空间时,每次分配的新存储量都会呈指数增长,这意味着当您追加时,重新分配会变得越来越少,这意味着在所有调用上追加的“摊销”时间接近常数时间。
数组还有一个方法,reserveCapacity
,它允许您通过请求数组预先为自己分配一些最小空间量来预先避免调用追加时的重新分配。如果您提前知道计划在数组中保存多少个值,则可以使用此选项。
将新值插入到数组中间也是O(n)
,因为数组保存在连续的内存中,因此插入新值需要将后续值打乱到末尾。但与附加不同的是,这不会因多次调用而得到改善。这与可以在 O(1)
即常数时间内插入的链表非常不同。但请记住,最大的权衡是数组也可以在恒定时间内随机访问,这与链表不同。
对数组中单个值的就地更改(即通过下标分配)应该是O(1)
(下标
实际上没有文档注释但这是一个非常安全的选择)。这意味着,如果您创建一个数组,填充它,然后不向其中追加或插入,那么它在性能方面的行为应该与 Java 数组类似。
所有这一切有一个警告——数组具有“值”语义。这意味着如果您有一个数组变量 a
,并将其分配给另一个数组变量 b
,这本质上是复制数组。后续对 a
中的值进行更改不会影响 b
,更改 b
也不会影响 a
。这与“引用”语义不同,其中 a
和 b
都指向同一个数组,并且通过 a
对它所做的任何更改都会反射(reflect)到有人通过 b
查看它。
然而,Swift 数组实际上是“写时复制”。也就是说,当您将 a
分配给 b
时,实际上不会发生复制。仅当两个变量之一发生更改(“突变”)时才会发生。这带来了很大的性能优势,但它确实意味着,如果两个数组引用相同的存储,因为自复制以来两个数组都没有执行写入操作,那么像下标分配这样的更改确实会产生复制整个数组的一次性成本点。
在大多数情况下,除非在极少数情况下(特别是在处理小型到中等大小的数组时),否则您不需要担心任何这些问题,但如果性能对您来说至关重要,那么绝对值得您熟悉一下以及该链接中的所有文档。
关于arrays - Swift 内部如何管理数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30691214/