Swift如何在内部管理阵列？

Question

我想知道Swift内部如何管理数组？Apple的语言指南仅处理使用情况,但没有详细说明内部结构.

作为一名Java开发人员,我习惯将"裸"数组视为非常静态和固定的数据结构.我知道在Swift中这不是真的.在Swift中,除了在Java中,您可以改变数组的长度并执行插入和删除操作.在Java中,我习惯于根据我想用该结构执行的操作来决定我想要使用的数据结构(简单数组,ArrayList,LinkedList等),从而优化我的代码以获得更好的性能.

总之,我想知道如何在Swift中实现数组.它们内部管理为(双)链表吗？是否有可与Java的Collection Framework相媲美的东西,以便调整以获得更好的性能？

Answer 1

您可以Array在Swift标准库的上面的注释中找到大量信息.要看到这一点,你可以Array在游乐场中进行cmd-opt-click ,或者你可以在非官方的SwiftDoc页面中查看它.

从那里解释一些信息来回答你的问题:

在Swift中创建的数组将其值保存在连续的内存区域中.因此,您可以有效地将Swift数组传递到需要这种结构的C API.

正如您所提到的,当您向其附加值时,数组可以增长,并且在某些点处,这意味着分配了一个新的,更大的内存区域,并将先前的值复制到其中.正是出于这个原因,它声明像append这样的操作可能是O(n)- 也就是说,执行追加操作的最坏情况时间与数组的当前大小成比例增长(因为复制值所花费的时间) .

但是,当阵列必须增加其存储空间时,每次分配的新存储量会呈指数级增长,这意味着重新分配在您追加时变得越来越罕见,这意味着在所有调用上追加的"分摊"时间接近恒定时间.

数组也有一个方法,reserveCapacity允许你通过请求数组预先为自己分配一些最小量的空间来预先避免重新分配调用append.如果您提前知道计划在阵列中保留多少个值,则可以使用此方法.

将新值插入到数组的中间也是O(n)因为数组保存在连续的内存中,因此插入新值会将后续值混合到最后.不同于附加,这不会改善多个呼叫.这与链接列表非常不同,您可以在其中插入O(1)即恒定时间.但请记住,最大的权衡是,与链接列表不同,数组也可以在恒定时间内随机访问.

对数组中的单个值进行就地更改(即通过下标进行分配)应该是O(1)(subscript实际上没有记录注释,但这是一个非常安全的选择).这意味着如果您创建一个数组,填充它,然后不附加或插入它,它在性能方面应该与Java数组类似.

所有这一点都有一个警告 - 数组具有"价值"语义.这意味着如果你有一个数组变量a,并将它分配给另一个数组变量b,这实质上是复制数组.对值的后续更改a不会影响b,并且更改b不会影响a.这与"参考"语义其中两个a,并b指向同一个阵列,并通过它所做的任何修改a都将反映到有人通过看它b.

但是,Swift数组实际上是"Copy-on-Write".也就是说,当您指定时a,b实际上不会进行复制.只有当两个变量中的一个发生变化("变异")时才会发生.这带来了很大的性能优势,但它确实意味着如果两个数组引用相同的存储,因为自复制以来都没有执行写操作,像下标分配这样的更改确实会在此处重复整个数组的一次性成本点.

在大多数情况下,除了在极少数情况下(特别是在处理小到中等大小的数组时),您不必担心这些问题,但如果性能对您至关重要,那么绝对值得您熟悉所有该链接中的文档.