在Swift中选择正确的数据结构

你好 在离开周末之前，我们想与您分享专门为基础课程“ iOS Developer”准备的材料翻译。

---

确定用来表示给定值集的数据结构通常比看起来要困难得多。 由于每种类型的数据结构都针对一定数量的用例进行了优化，因此为每种数据集选择合适的位置通常会对我们代码的性能产生重大影响。

标准的Swift库带有三个主要的数据结构Array ， Dictionary和Set ，每个结构都有其自己的一组优化，优缺点。 让我们看一下它们的一些特征，以及可能需要超出标准库以找到适合我们目的的正确数据结构的情况。

阵列线性

Array可能是Swift中最常用的数据结构之一，这有充分的理由。 它按顺序存储其元素，可以轻松地以可预测的方式对它们进行排序，并且可以将任何值存储在其中：从结构到类的实例以及其他集合。

例如，在这里我们使用数组来存储放置在绘图应用程序中Canvas上的形状的集合。 然后，当我们需要将画布渲染为图像时，只需遍历数组以使用DrawingContext绘制每个元素-如下所示：

 struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } } 

当涉及到所有形状的顺序渲染时，就像我们在上面所做的那样，该数组非常适合。 数组不仅以非常有效的方式存储其元素，而且还具有保证的排序顺序，该顺序提供了可预测的渲染顺序，而无需执行任何额外的工作。

但是，像所有其他数据结构一样，数组也有其缺点。 在我们的案例中，当我们想从画布上删除形状时，我们将遇到其缺点之一。 由于数组的元素是按索引存储的，因此我们始终需要先找到图形与哪个索引关联，然后才能删除它：

 extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } } 

最初，上面的代码似乎没有那么大问题，但对于任何包含大量形状的画布，它可能成为性能瓶颈，因为firstIndex在时间复杂度方面是线性的（O（N））。

尽管我们可以在使用Canvas类型的地方解决这个限制。 例如，始终按索引而不是按值或ID引用图形-这将使我们的代码更加复杂和脆弱，因为我们始终必须确保在使用画布时索引不会过期会改变。

速度设定

相反，让我们看看是否可以通过更改其基础数据结构来优化Canvas本身。 考虑到上述问题，我们的初步想法之一可能是使用Set （集合）而不是Array 。 正如我们在Swift中的集合的强大功能中已经讨论的那样，集合相对于数组的显着优点之一是插入和删除操作始终可以在固定（O（1））的时间内完成，因为项目是按哈​​希值而不是按索引存储的。

通过将Canvas更新为使用集，我们得到以下信息：

 struct Canvas { var shapes: Set<Shape> func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func remove(_ shape: Shape) { shapes.remove(shape) } } 

同样，以上代码看起来不错，甚至可以编译而没有问题。 然而，尽管我们解决了删除问题，但我们也失去了稳定的渲染顺序-因为与数组不同，集合不能为我们提供有保证的排序顺序-在这种情况下，这是绊脚石，因为看起来我们将在其中绘制自定义形状随机地。

索引索引

让我们继续尝试。 现在，让我们看看是否可以通过引入Dictionary来优化Canvas ，它可以让我们根据ID来搜索任何形状的索引。 我们将从将shapes数组的访问级别更改为private以便我们可以使用新的add方法控制元素的插入。 每次添加新图形时，我们还将其索引添加到字典中：

 struct Canvas { private var shapes = [Shape]() private var indexes = [Shape.ID : Int]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { let index = shapes.count indexes[shape.id] = index shapes.append(shape) } } 

由于现在我们始终知道给定图形的存储索引，因此可以像使用集合时一样，在固定时间内快速执行删除操作：

 extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } } 

但是，我们新的Canvas实现中存在一个非常严重的错误。 每次删除形状时，实际上会使所有高于刚删除的索引的索引无效-因为这些元素中的每一个都会向数组的开头移动一步。 我们可以通过在每次删除后调整这些索引来解决此问题，但这又将我们带回到O（N）领域，这是我们从一开始就试图避免的领域。

我们的最新实现有其优点。 通常，在这种情况下使用两种数据结构的组合可能是一个好主意，因为我们经常可以利用一种数据结构的优势来弥补另一种数据结构的缺点，反之亦然。

因此，让我们尝试使用其他组合，但是这次让我们开始考虑我们的实际需求 ：

• 我们需要插入和删除都具有恒定的时间复杂度，并且应该有可能在不知道其基础索引的情况下删除该图形。
• 我们需要有保证的排序顺序，以便能够维持稳定的渲染顺序。

综观上述要求，事实证明，尽管我们需要稳定的排序顺序，但实际上并不需要索引。 这将使链表非常适合我们的用例。

链接列表由节点组成，其中每个节点都包含指向列表中下一个节点的链接（或链接），这意味着可以按可预测的方式对其进行排序-删除项目时无需任何索引更新。 但是，Swift标准库（到目前为止）不包含链表类型，因此，如果要使用它，则必须首先创建它。

创建一个链表

让我们首先声明一个List结构，该结构将跟踪List的第一个和最后一个节点。 我们将在类型之外将这两个属性设为只读，以确保数据一致性：

 struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? } 

接下来，让我们创建Node类型（节点），我们将创建一个类，因为我们希望能够通过引用而不是通过value引用节点。 我们的列表将被双重连接，这意味着每个节点都将包含指向其下一个邻居和上一个邻居的链接。 每个节点还将存储一个值-像这样：

 extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } } 

我们使先前的属性变弱的原因是为了避免在我们保持双向强链接的情况下出现的保留环。 要了解有关避免保留周期的更多信息，请参阅文章“内存管理” 。

实际上，这就是我们需要的所有代码，以便可以将值存储在链接列表中。 但这只是难题的第一步，与其他任何收藏一样，我们也希望能够对其进行迭代并更改其内容。 让我们从迭代开始，这要归功于面向协议的Swift设计，可以通过确保遵守Sequence协议并实现makeIterator方法来轻松实现：

 extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator { //   ,    ,    : let value = node?.value node = node?.next return value } } } 

由于上面的迭代非常简单，因此我们使用AnyIterator标准库来避免实现自定义迭代器类型。 对于更复杂的场景，可以通过向IteratorProtocol添加匹配项来实现。

接下来，让我们从插入开始添加一个API，以修改链表。 我们将使用append方法扩展List ，该方法将为插入的值添加一个新节点，然后返回此节点-如下所示：

 extension List { @discardableResult mutating func append(_ value: Value) -> Node { let node = Node(value: value) node.previous = lastNode lastNode?.next = node lastNode = node if firstNode == nil { firstNode = node } return node } } 

上面，我们使用@discardableResult属性，该属性告诉编译器如果不使用调用方法的结果，则不生成任何警告，因为我们并不总是对所创建的节点感兴趣。

由于链接列表不是基于索引，而是通过链接维护值链，因此实现删除只是更新远程节点的下一个和上一个邻居，以便它们彼此指向而已：

 extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous //  « »,        ,    : if firstNode === node { firstNode = node.next } if lastNode === node { lastNode = node.previous } } } 

基于上述内容，列表的初始版本已完成，我们准备对其进行验证。 让我们更新画布以使用我们的新列表，以及一个字典，该字典使我们能够快速找到与给定形状ID匹配的节点：

 struct Canvas { private var shapes = List<Shape>() private var nodes = [Shape.ID : List<Shape>.Node]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { nodes[shape.id] = shapes.append(shape) } mutating func remove(_ shape: Shape) { guard let node = nodes.removeValue(forKey: shape.id) else { return } shapes.remove(node) } } 

现在，我们既可以快速插入和删除，又可以预测排序顺序，而无需在调用过程中增加额外的复杂性-这非常酷！ 并且，由于我们的新List是完全通用的类型，因此现在我们可以在需要再次以线性方式存储没有索引的值时使用它。

结论

尽管数据结构是如此基础，以至于可以在各种编程语言中找到它们，但要决定在每种特定情况下使用哪种结构仍然需要大量的思考，测试和试验，尤其是如果我们想要这样我们的代码就可以随着数据集的增长而保持有效。

随着我们需求的变化，针对每种特定情况的适当数据结构也很可能会随时间而变化，有时使用几种数据结构（而不​​只是一种）的组合可以达到所需的性能特征。

在接下来的文章中，我们将继续探索数据结构的世界，重点关注那些尚未在标准库中实现的数据结构。 与许多其他事情一样，有时我们需要将思维方式扩展到Swift之外，以便为每种情况选择正确的数据结构。

如果您有任何问题，评论或反馈，可以在Twitter上找到我或给我发送电子邮件。

感谢您的关注！