一尘不染

Swift如何在内部管理数组?

swift

我想知道Swift如何在内部管理数组?Apple的语言指南仅处理用法,而未详细说明内部结构。

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

总之,我想知道如何在Swift中实现数组。它们是否在内部作为(双)链接列表进行管理?是否有任何其他东西可以与Java的Collection
Framework媲美,以进行调整以获得更好的性能?


阅读 171

收藏
2020-07-07

共1个答案

一尘不染

您可以Array在Swift标准库中的注释上方找到很多信息。要查看此内容,您可以Array在操场上进行cmd-opt-click
,也可以在非官方的SwiftDoc页面中查看它。

为了从中解释一些信息来回答您的问题:

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

正如您所提到的,在向数组添加值时,数组可能会增长,并且在某些时候,这意味着将分配一个更大的新内存区域,并将先前的值复制到其中。出于这个原因,它声明像追加这样的操作
可能O(n)–即,执行追加操作的最坏情况下的时间与数组的当前大小成比例地增长(因为要复制值所花费的时间) 。

但是,当阵列必须增加其存储量时,每次分配的新存储量都呈指数增长,这意味着重新分配的数量在您追加时变得越来越少,这意味着在所有调用中追加的“摊销”时间接近恒定时间。

数组还有一种方法,,reserveCapacity您可以通过请求数组预先为其分配一些最小的空间来抢先避免在调用append时发生重新分配。如果您提前知道计划在数组中保留多少个值,则可以使用此方法。

将新值插入数组的中间也是O(n),因为数组保存在连续的内存中,所以插入新值涉及将后续值拖到末尾。但是与追加不同,这不能改善多个调用。例如,这与可以在O(1)固定时间内插入的链表非常不同。但是请记住,最大的折衷是,与链接列表不同,数组还可以在恒定时间内随机访问。

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

所有这些都有一个警告-
数组具有“值”语义。这意味着,如果您有一个数组变量a,并且将其分配给另一个数组变量b,这实际上是在复制该数组。中的值的后续更改a不会影响b,并且更改b也不会影响a。这与“引用”语义不同,在“引用”语义中,a和都b指向同一个数组,并且对via
a进行的任何更改都将反映给通过via查看它的人b

但是,Swift数组实际上是“写时复制”。也就是说,当您指定ab不进行复制时,实际上不会发生。仅当两个变量之一发生更改(“突变”)时才会发生。这带来了很大的性能优势,但是这确实意味着,如果两个数组都引用了相同的存储,因为自复制以来两个都没有执行写操作,则像下标assign这样的更改确实会一次性复制整个数组。点。

在大多数情况下,除了在极少数情况下(尤其是在处理中小尺寸的阵列时),您无需担心任何其他问题,但是如果性能对您至关重要,那么一定要熟悉所有这些该链接中的文档。

2020-07-07