Using Collections Effectively

2019-04-16

Swift 提供了Array, Set, Dictionary 三种基本的集合类型用来存储数据。Array是有序数据的集合,Set是无序无重复数据的集合,Dictionary是无序的键值对的集合。

集合非常普遍并且共享非常多的常见特性和算法,因为在Swift中它们都遵守一个通用协议Collection。在Swift中,集合就是序列,其中的元素可以以非破坏性的方式多次遍历,并且其元素可以通过下标访问。

collection_subscript_index

这可能是一个在连续内存中定义的数组,哈希表,红黑树,链表或者你可以想象的任何其他东西。作为集合它们都支持起始索引(startIndex)和结束索引(endIndex),可以用来访问集合的初始元素和用来标识集合的结束。集合支持从其startIndexendIndex直接遍历元素,同时也支持使用下标(subscript[index])来获取集合中的元素。

Collection 集合

集合的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
protocol Collection : Sequence { 

// 集合中元素的类型
associatedtype Element

// 索引类型, 需要遵守Comparable协议
associatedtype Index : Comparable

// 遍历时所用到的方法了, 即通过索引查询到对应的元素
subscript(position: Index) -> Element { get }

// 开始索引
var startIndex: Index { get }

// 结束索引
var endIndex: Index { get }

// 通过一个索引, 获取它后面的索引
func index(after i: Index) -> Index
}

这里用到了associatedtype关键字, 在Swift协议定义的时候, 会看到使用这个关键字, 你可以认为这是一个占位符, 具体的类型直到被用到的时候才会确定. 但是有时候我们需要规定这个占位符要有一些能力, 比如这里的Index, 他就需要遵守Comparable协议.

集合协议的扩展

collection_protocol_extensions

通过遵守Collection协议,你可以访问集合中各种丰富的功能, 有一些我们常用的first, lastisEmpty,count等属性,以及dropFirstdropLast,reversedsplit等函数以及一些mapfilter之类的高阶函数。

我们也可以通过自定义一些协议扩展来实现更加强大的功能。

如隔元素遍历的功能:

collection_extension_every_other_element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
extension Collection { // 扩展集合协议  
func everyOther(_ body: (Element) -> Void) {
// 获取首元素索引
let start = self.startIndex
// 获取末尾元素索引
let end = self.endIndex
var iter = start
// 未走到末尾
while iter != end {
// 执行外部的闭包
body(self[iter])
// 获取当前元素的下一个索引
let next = index(after: iter)
// 检查索引是否走到末尾
if next == end { break }
// 将当前索引指向next的下一个
iter = index(after: next)
}
}
}

(1...10).everyOther { print($0) }

集合的继承结构

collection_protocol_hierarchy

除了强大的Collection本身,Swift中还有其他很多继承自Collection的协议。

  • BidirectionalCollection 双向集合,可以向前访问元素
  • RandomAccessCollection 随机访问集合,提供了复杂度O(1)的访问方法,因为继承自BidirectionalCollection,也可以向前向后访问元素
  • MutableCollection 可变集合,提供了修改集合元素的能力
  • RangeReplaceableCollection 范围替换集合,可以通过指定范围替换元素

Indces 索引

集合可以通过索引的方式来访问其中的元素,其中

  • 每个集合都有自己的索引
  • 索引必须满足Comparable
  • 将索引作为不透明的类型(索引可能是正数,也可能是其他类型)

如何访问第一个元素

通过下标进行直接访问

使用array[0]访问第一个元素, 当然没有问题, 可是如果我们扩展开来, 如果给的集合不是数组, 而是一个set, 那么, 这样的方式就行不通了.

通过索引进行访问

使用set[set.startIndex]进行访问, 这样就可以了。 这个方法普遍适用于其他集合类型,如array[array.startIndex]

但是, 你同样需要注意一些潜在的问题, 如需要判空, 需要判断越界, 诸如此类

first

我们可以使用set.first进行获取. 而且不用担心那些潜在的问题

如何访问集合的第二个元素

我们可以通过向集合来添加一个新属性来实现

collection_access_second_1

collection_access_second_startindex

显然我们不能通过这两种方式来进行获取,因为我们之前说过,Collection的索引类型并不一定是Int,而是一个遵守Comparable协议的类型。

collection_access_second_element

Slice 切片

切片是仅描述集合一部分元素的类型,每个切片都有自己的起始和结束索引,并且切片与其原始集合分开存在。切片不占用额外的存储空间,只是引用原始集合,因此非常高效。当使用切片下标时,它将读出原始缓冲区中的数据,切片能这么做的原因是因为它与其原始集合共享同样的索引。

collection_forming_slice

通过切片,我们可以更优雅的实现访问第二个元素的功能。 我们去掉首元素,然后再获取新得到的集合的第一个元素就可以实现了。

collection_slice_find_the_second_element

切片与源集合共享索引
collection_slice_share_indices

每个类型都可以自由定义自己的切片类型

collection_slice_types

内存问题

值得注意的是, 持有切片, 将使得即便将原来的集合置空, 内存也不会释放。切片是一个 原有集合 + 映射关系 的产物. 所以, 除非将切片也置空, 否则, 原有集合并不会被释放.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
extension Array {
var firstHalf: ArraySlice<Element> {
return self.dropLast(self.count / 2)
}
}

var array = [1, 2, 3, 4, 5, 6, 7, 8]
var firstHalf = array.firstHalf // [1, 2, 3, 4]
// 将数组设置为空
array = []

print(firstHalf.first!) // 1

let copy = Array(firstHalf) // [1, 2, 3, 4]
// 将切片置为空
firstHalf = []
print(copy.first!) // 1

在这里,只有将源数组array设置为空且将切片firstHalf也设置为空之后,底层的存储才会真正消失。

过程如下

collection_slide_copy_a_slice

切片的工作方式有点像延迟拷贝,可以选择何时自己创建元素的副本,事实证明这种”懒”行为和延迟做某事的概念,在其他情况下也非常有用。

一种情况是函数调用。

Lazy Function

默认情况下,Swift中的函数是”Eager(急切)”的,也就是说它们接收了输入并按照要求返回输出。

collection_eager_function

经过这样的一套操作, 我们计算了4004个元素, 如果我们后面还有一些其他的操作, 更糟糕的是, 如果我们最终只是取取first, 这样, 前面生成的那些元素, 都成为了浪费.

collection_lazy_functions

我们可以通过lazy关键字来规避这样的浪费。可以看到, 使用lazy后, 刚才的遍历过程, 变成了组织一个新集合的过程,

collection_lazy_functions_filter

只有在first进行计算的时候,才进行计算。

使用lazy时如何避免重复计算的过程

collection_lazy_function_avoid_multi_computation

lazy的目的是只根据需要进行计算,但它避免的另一件事是创建中间存储。

何时使用 Lazy

  • 链式计算
  • 只需要结果中的一部分
  • 没有其他副作用 No side effects
  • 避免跨越API边界时

MutableCollection

当尝试修改集合时,使用了失效的索引:

collection_mutating_array

collection_avoid_index_invalidation

collection_reuse_invalid_dict_indices

collection_dict_up_to_date_indices

如何避免

  • 在持有索引和切片时, 处理要谨慎
  • 集合发生改变时, 要更新索引后再使用
  • 在需要索引和切片的情况下才对其进行计算

多线程访问

collection_thread_unsafe_pratices

collection_avoid_concurrent_mutation

如何避免

  • 隔离数据使其只能被单个线程访问
  • 实现适当形式的互斥,如串行调度队列或锁
  • 使用Thread Sanitizer来检查

建议

首选不可变集合来避免之前提到的问题

  • 如果可以避免,就不要使用可变集合
  • 可以使用切片和lazy操作符来模拟想要执行的改变
  • 当尝试修改不可变集合石,编译器会提示你

如果可以, 尽量使用带capacity的初始化函数去初始化你的集合, 因为这样节省一些不必要的内存开销, 虽然这并不能节省多少, 但是想象你的项目中有成千上万个集合对象, 他们可以省出一个相当可观的内存数量.

Foundation Collection

引用类型的集合:

collection_reference_type_collections

值类型和引用类型

collection_value_and_reference_type

collection_value_and_reference_type_2

对于值类型来说, 这样有什么好处呢? 因为在现代CPU在设计的时候, 采用了缓存机制, 可以快速的访问连续区域的地址. 而值类型的这种操作, 各个元素之间的内存是相连的, 而引用类型的则不是.

在Swift中使用Foundation集合时,通过桥接的方式将Objective-C中的API以Swift原生的值类型。桥接使我们可以在两种不同的运行时表示之间进行转换。尽管已经对Swift和Objective-C之间的桥接进行了优化,但是两种语言之间桥接时总会产生一些开销。

collection_how_bridging_works

当在语言之间桥接时,必须先建立新的对等的存储空间,然后需要逐个元素的在它们之间进行转换。当桥接发生在两种语言的边界时,称之为”Eager”桥接,当集合中元素也需要桥接时,集合本身将总是进行”Eager”桥接,这种情况最常出现在以字符串作为键的字典中。当集合桥接并不急切时,我们称之为’lazy’桥接。当集合元素的类型并不需要桥接时,就会发生这种情况,比如NSView,在这种情况下,桥接将会被推迟到首次使用该集合时。

collection_bridging_examples

发生桥接的地方和所需开销:

collection_bridging_time

collection_bridging_happens

这里的桥接发生在

  • NSMutableAttributedStringstring上, return bridge.
  • 需要传入一个NSString, 参数类型桥接 param bridge

collection_bridging_happens_2

其中 “Brown” 这里也会有一个小的桥接,这里的”Brown”是一个Swift值类型的字符串,每当我们调用NSString的range(of:)时,实际上会把这个字符串桥接回NSString。

collection_bridging_happens_final

建议

什么时候应该使用Foundation Collection?

collection_when_to_use_foundation_collection

现在我们对Swift中强大的集合世界的探索已经接近尾声,希望你能够使用这种新视角来检视你现在使用集合的方式,寻找可以通过更有效地使用索引和切片来改进代码的地方,寻找可以通过惰性或者调整桥接方式而受益的地方,用ThreadSanitizer辅助审查可变状态。并通过应用今天讨论的所有概念在自己的App或者Playground中进一步锻炼你对集合的掌握.