认识 Swift 算法和字体集软件包

♪ （Swift Algorithms 和Collections包简介）

嗨 我是凯尔 Swift标准库团队维护着越来 越多的开源包 包括 Swift ArgumentParser Swift Numerics和 Swift System 今天 我们很高兴为 这个家族引入两大新成员： Swift Algorithms和 SwiftCollections！ Swift Algorithms 是一个开源的序列和集合算法包 扩展了Swift标准库 Swift最强大的功能之一 是内置了丰富的 算法分类 学习词汇需要付出一点努力 但是一旦学会了 您会惊奇地发现 很多算法其实显而易见 采用它们能大大提高 代码质量 为了便于理解 让我们来看看我一直 在研究的消息传递 App的一些代码 看一看这个循环 它在表视图中 选定行的索引路径中迭代 收集所有相应的消息 进行转发或删除 这就是map 使用map可以让读者 更清楚地理解这段代码 因为它提供了额外的上下文 即闭包的主体 不管它的长度或复杂性如何 只是在转换输入 使用map还可以使代码运行更快 因为它通过保留容量避免了 由于数组大小调整而 导致的中间分配—— 这是我们的raw循环 解决的问题 或者看一下这个循环 如果用户点击一个图像 迭代记录中的消息 收集所有附件以便 使用Quick Look显示 这就是map和filter！ 事实上 这种过滤掉零 并映射到unwrap选项的模式 非常常见 因此我们给它 定义了一个特殊的名称 和算法：compactMap 接下来 看一下这段代码 我有一个消息数组 我想把它转换成 一个下标项数组 棘手的是 任何给定的消息 都可能对应于聊天记录的多项 此时使用map生成一系列数组 但那不是我想要的； 我只想要一个扁平数组 这是否意味着我必须 回到使用raw for循环？ 当然不是；我们有另一种算法 叫做“joined” 它所做的是将所有内部数组连接到 单个扁平的元素集合中 这种映射和连接模式非常常见 因此我们为它定义了另一种 特殊的映射： flatMap 当然 map和filter 只是冰山一角 从我的App中的聊天详情 屏幕看一下这个raw循环 我想在聊天中显示最后六张照片 从最新的到最旧的 所以我反过来迭代记录—— 从最新到最旧—— 如果这项是一张照片 我就把它添加到数组中 一旦我有了六个 我就停下来 我们可以通过 将标准库中的算法—— 反向 compactMap 和前缀—— 链接在一起来更简洁地 表达这一点 只需要前六个 将算法链接在一起也带来了 更大的灵活性 可以更清楚地表达这段代码 例如 我发现用记录的后缀 而不是反向记录的前缀 来思考这个操作更加自然 所以算法链比raw循环更清晰 更简洁 但性能对比如何？ 如果算法链中的每一步都 分配一个中间数组 难道不会比raw循环更慢吗？ 如果标准库没有 在这里发挥巧妙的作用 答案将是肯定的 让我们回到前面 看到的joined算法 仔细看看发生了什么 事实证明 joined实际上并 没有在这里分配和返回一个新数组 相反 它返回一个 FlattenSequence FlattenSequence 也就是“lazy adapter” 对于大多数目的来说 它像一个数组一样工作 但它只是一个简单的包装器 所以它实际上可以自由创建 而且它很“lazy” 所以 只是按需处理它的元素 而不是预先做好所有的工作 像FlattenSequence 这样的lazy adapter 使算法链具有与raw for循环 相媲美的性能 让我们回到详情屏幕 仔细看看我们计算聊天 中最后六张照片的算法 我们看到后缀实际上只是 返回了一个数组切片—— 这很巧妙—— 而且reversed还被实现为 lazy adapter 一个在末尾开始并在开始时 结束的adapter compactMap呢？ 它仍然返回一个数组 那能是“lazy”吗？ 可以的 您只需要在链的开始处 添加一个. lazy 它会让任何接受闭包的算法 比如map和filter 都变成“lazy”！ lazy算法链非常适合 像这样的用例 在这种情况下 你只处理潜在的非常大的 集合中的少量元素 当然 有时候你确实需要 或者想要获得一个数组 在这种情况下 你总是可以 将你的算法链包装 在数组初始值设定项中 这是为什么在标准库团队中 我们非常热衷于 lazy算法的又一个原因 利用lazy算法获得 想要的结果真的很容易 但反过来却不可能 所以我在消息传递App上 取得了很大的进展 我的设计师向我提出了 一个功能请求 如果任何两条连续的信息 间隔超过一个小时 则他们希望在记录中 包含时间戳 看上去似乎很合理 我一定还可以用另一种算法 对吧？ 有 但是要使用它 我需要导入 Swift Algorithms包 每隔一段时间 你会遇到像这样的用例 而这些用例是Swift 标准库还没有覆盖的 Algorithms包的目的 是为我们提供 一个低摩擦的场所—— 在你的帮助下—— 孵化新的缺失算法家族 以便最终包含在标准库中 我们已经向Swift Algorithms添加了40多种算法 比如生成元素集合的所有组合 或排列；或者将一个序列的元素 迭代两次或三次 或者按谓词确定的组迭代； 或者在一个集合中选择 五个最小的元素 五个最大的元素 或者随机选择任意五个 让我们仔细看看 Swift Algorithms 附带的一些强大的迭代工具 windows(ofCount:) 提供了一个滑动窗口 这里的大小为3 可以进入一个集合的元素 对于循环的每一圈 window只是基本集合的 一个子序列—— 这里是ArraySlice—— 这避免了任何中间分配 windows(ofCount: 2) 特别常见 因此我们给它创建了一个快捷方式 它被称为 “adjacentPairs” adjacentPairs 发出元组而不是子序列 从而更便于元素访问 另一个强大的迭代工具是 chunks(ofCount:) 与窗口不同 块不会重叠 如果集合不能被块数整除 则序列中的最后一个 块将包含余数 就像窗口一样 块是基本集合的子序列 所以创建起来很容易 有时 你希望将一个集合分成 多个相似的元素 我们是在isPrime 上进行分块 这意味着我们 将分块迭代为isPrime 返回相同值的连续元素块 为了方便起见 chunked(on:) 发出块和分块值的元组 你有没有发现自己 写了一个像这样的raw循环 如果先前和当前的元素不同 它只能完成一些工作？ 这只是分块的！ 现在让我们回到我的 设计师要求的那个特性 即每当消息间隔超过一个小时 就在记录中包括时间戳 如果你还记得 我们通过在消息上 进行平面映射来创建记录 以创建记录项 每个记录项都可以访问其日期 如果记录项之间的 间隔不到一个小时 那我们可以把日期进行分块 以把记录项组合在一起 我们已经看到了如何将一个集合 分成类似元素的序列 Swift Algorithms 附带了另一个允许 提供自定义谓词的分块变体 它可以传递相邻的元素对 如果它们属于同一个组 则返回true 在这里 如果记录项 之间的时间间隔小于一小时 则我们返回true 接下来 我们需要创建时间戳 并将所有内容连接到 单个扁平集合中 之前 我们使用joined 来展平嵌套集合 标准库附带了另一个可以插入 分隔符的joined变体 使用这种算法将字符串 连接在一起是很常见的 比如说 用一个新的行或逗号分隔符 然而 在这种情况下 常量分隔符是不够的 为了构造时间戳 我们需要访问 下一个块中的第一个日期 好吧 Algorithms包 包括另一个joined变体 它允许你计算前一个和 下一个块的分隔符 我们可以在这里用它 把块下标项重新连接起来 现在用时间戳分开 很满意 是吧？ 当然 我们不需要为任何 这些中间分配大费周章 所有这些都可以通过添加 一个.lazy实现按需计算 大功告成！ 不过 我想提醒大家 lazy不是万灵药 当你只迭代一次序列时 按需计算可以节省工作并避免分配 但是 当你一次又一次地 重复一个序列时—— 就像我在消息传递 App中处理聊天记录一样—— 按需计算会重复同样的工作 每次用户进入编辑模式 点击图像或访问详情屏幕时 都会进行过度映射、分块和连接 在这种情况下 你仍然应该使用lazy算法链 只是作为最后一步 如果您把所有东西收集到 一个数组中来保存工作 效率会更高 我们已经查看了 来自Swift标准库 和 Algorithms包的 十几种不同的算法 所有这些不仅适用于数组 还适用于字符串 以及符合序列和集合 协议的所有其他Swift类型 包括新Swift Collections包中的 每个数据结构 将算法链接在一起可以 让你的代码更清晰 更快速 更正确 掌握起来并不复杂； 只要积累词汇量就好了 所以下次你发现自己 在读或写一个raw循环时 停下来想想这是 map filter 还是您刚刚看到的其他算法 如果想不起来 请搜索关于 序列和集合协议的文档或阅读 Swift Algorithms GitHub存储库中的指南 或访问Swift论坛 在那里我们可以一起找到答案 谁知道呢 它可能会 成为Algorithms包 新功能的灵感！ 接下来 卡罗伊 将介绍新的Swift Collections包 附带的多功能数据结构 卡罗伊？ 谢谢你 凯尔! 让我们谈谈数据结构 目前 Swift标准库 只实现了三种主要的通用数据结构： 数组 无序集 和无序字典 事实证明 作为通用集合类型 它们是很好的选择 尤其适合跨模块边界传输数据 它们都实现了写时复制的值语义 提供了高效的就地突变操作 同时还确保了集合值 可以安全地传递 而这些突变不会 导致任何创建的副本发生意外变化 然而 还有更多的数据结构 有更多的选择是有用的 今年早些时候 我们发布了 带有新数据结构实现的 Swift Collections包 这个包让Swift开发人员 在我们最终提议 将它们纳入Swift标准库之前 获得新集合类型的实际开发经验 通过导入Swift Collections包 我们可以访问其他类型 该包的初始版本实现了 三种最常请求的数据结构 这些恰好是三种 标准集合类型的新变体 我们有一个双端队列 一个OrderedSet 和一个Ordered Dictionary 这些类似于数组 集和字典； 它们是同一个主题的变体 为现有的构造增加了新的特性 也就是说 这些新类型 不是现有类型的替代品； 它们是相辅相成的 对于一些用例 新的类型会更适合 然而 对于许多其他用例 现有类型仍然是正确的选择 为了知道要使用哪种数据结构 我们需要了解这些数据结构 与现有类型有何不同 因此 让我们从双端队列开始 或者更确切地说 从一般队列开始 简单地看一下其中的每一个 从超市排队等候的顾客到 App中的异步任务 需要逐一处理任意数量的 项目的地方都会 弹出队列 在最抽象的形式中 队列提供了两种主要的操作： 我们可以将项目推到队列的后面 我们可以将元素从前面弹出

双端队列使这些队列操作对称 它支持将新项目高效地 推到队列的前面... ...以及从后面弹出元素

“双端队列”这个名字对于这样 一个有用的类型来说是相当拗口的 所以我们喜欢把它 简称为“deque” 多去掉了一个音节 这在传统上与 “deck”的发音相同 如a deck of cards 在Collections包中 deque拥有与熟悉的数组 类型大致相同的API 并且它实现了许多相同的协议 例如 我们可以使用数组 文字来创建一个deque Deque符合RandomAc cessCollection协议 像数组一样 deque使用整数索引 这些索引是从集合的开头 测量的偏移量 这让基于位置访问 任何元素变得容易 例如 这个deque中索引1处 的元素是字母E 现在 我确信我不是唯一一个 被这个集合末尾的小写f困扰的人 幸运的是 deque符合 MutableCollection 协议 因此 我们可以通过索引2赋值 用大写的F替换小写的f 来解决这个问题 啊 看起来好多了！ Deque还实现了 RangeReplaceableCollection 协议 因此它提供了所有常见的插入 移除或替换元素子范围的操作 例如 我们可以通过调用索引为零的 insert(contentsOf:) 方法 在我们的deque 前面插入一个序列 它的执行方式就是deque 开始与数组不同的地方 如果我们使用一个数组 来存储我们的项目 那么在前面插入新的元素 需要从移动现有的元素开始 为新的元素腾出空间 为了使访问尽可能简单 数组将它们的元素保存 在单个连续的缓冲区中 从它们的存储开始 如果数组很大 这使得预先添加 新元素相对麻烦一点； 因此 在前面插入一个 新元素需要的时间 与数组中已经存在的元素数量 大致成正比 deque的工作方式不同 它将存储缓冲区包装在其边界周围 这样它就可以在不移动任何 现有元素的情况下 预先添加新元素 索引仍然是从集合 逻辑开头的偏移量 所以在插入之后 索引1处的元素现在是B 这意味着deque需要做一些工作 来在它们的逻辑索引和 它们的实际存储位置之间进行转换 但是访问元素仍然是非常有效的 因为预先添加到 一个deque并不涉及 滑动任何现有成员 所以它们能够比数组 更快地执行这个操作 无论集合中已经有多少元素 在前面插入一个新元素 都需要一段固定的时间 这就是数据结构的力量 一旦我们的工具箱中有了它们 我们就可以用它们来解决 以前无法解决的问题 切换到正确的数据结构 会有很大的不同 它可以让一个非常慢的App 变地反应灵敏 使用起来很顺畅 当然 deque也可以 在存储过程中 执行操作 例如 当移除一系列元素时 deque可以选择通过 移动前面的元素而不是 后面的元素来关闭产生的间隙 这可以减少 需要移动的元素数量 这并不像预先添加一个元素那样 是大幅度的改进 但是当我们随机移除元素时 它确实让运行速度平均快了一倍 这就是deque 现在 让我们看看有序集 标准的 预先存在的 集类型是一个集合 保证它的所有元素都是唯一的 然而 它并没有保留最初的顺序 集中元素的顺序 实际上是随机的 这意味着同一个集的两个实例经常 以两种完全不同的排列列出它们 尽管如此 包含相同元素的两个集 被认为是相等的；顺序并不重要 当我们只想保证唯一性时 这很好 但有时我们也想 控制元素的顺序 例如 如果我们正在编写 一个待办事项列表App 我们可能希望确保它 只列出每个项目一次 但我们也需要按照用户设置的 特定顺序保存它们 这就是有序集的作用 根据我们的视口 它要么像保持其元素 唯一的数组一样工作 要么我们可以将其视为一个集 保持我们对其成员建立的顺序 像数组和集一样 有序集也可以用数组文字表示 然而 与集不同 元素的顺序一定会被保留 顺序也很重要；如果两个有序集不仅 包含相同的成员 而且它们的顺序也必须相同 则它们比较相等 如果我们只需要知道两个有序集 是否包含相同的元素 以任何顺序 那么我们可以通过特殊的 无序视图来比较它们 这个轻量级视图忽略了元素排序 因此它提供了一个更传统的 类似集的接口 然而 默认情况下 有序集类似于数组的工作方式 有序集是具有整数偏移索引的 随机访问集合 这一事实加强了这一点 我们可以使用整数下标来访问项目 就像在数组或deque中一样 正如从集中预期的那样 我们也可以添加和移除元素 尽管这些操作确实需要 考虑位置 例如 我们有一个追加操作 如果一个新元素还不是成员 就在集的末尾添加一个新元素 它的返回值指示 是否需要添加元素 并且它还报告该项的索引 我们还有一个插入操作 将新元素放在指定的位置 在这种情况下 字母B已经存在 因此该操作只返回现有 成员的索引 移除一个元素会在 有序集中留下一个洞 需要移动其余的成员来填充它 就像在数组中一样 有序集需要保持其元素的唯一性 因此它们不能支持任意的项目替换 这意味着与数组不同 它们不能符合 MutableCollection或 RangeReplaceableCollection 协议 然而 它们确实支持 标准的重新排序操作 如排序或洗牌 有序集还以保序的方式实现了 SetAlgebra协议中的 所有高级集操作 例如 形成一个并集会按照元素 在第二个集中出现的顺序 追加任何缺失的元素 减去一个集会保持剩余元素 的原始顺序 即使有序集实现了大多数的 SetAlgebra操作 它们也不能正式地符合那个协议 因为它要求元素的顺序 不重要 然而 它们无序的观点 有一个对顺序不敏感的平等概念 所以它可以并且 确实符合SetAlgebra 我们可以使用它将 OrderedSet值 传递给任何需要 SetAlgebra值的函数 从幕后看 标准的 无序集类型使用随机植入的 通用散列函数将其元素 直接存储在扁平哈希表中 这为元素提供了很好的查找性能 但是它丢弃了它们原来的顺序 为了支持用户指定的 任意元素排序 有序集将其元素存储在 常规数组实例中 有序集仍然使用相同的 快速且安全的哈希表实现 但是在这种情况下 该表只需要将整数索引 存储到存储数组中 这些整数的范围受 哈希表的大小限制 因此我们可以通过将整数值 打包成尽可能少的位来压缩该表 与常规集相比 这有时可以 节省大量内存 同时仍然保持大多数操作的 竞争性能 查找性能与标准集相当 无论集合的大小如何 查找随机成员 都需要大致恒定的时间 数组需要费力地查看每个元素 随着集合的增长 这需要更长的时间 向有序集追加一个新元素的操作 大致相当于向标准集中 插入一个元素 这仍然需要对新项进行散列 并且还包括检查该元素 是否已经存在 因此这是一个比直接将元素 附加到简单数组复杂得多的操作 但是这些仍然需要固定的时间 不管集合有多大 然而 虽然OrderedSet 能够快速查找 现有元素并追加新元素 但它不能有效地实现在集的 前面或中间移除或插入项目 与数组一样 这些操作需要 在存储数组中滑动元素 但也需要对哈希表中的后续索引 重新编号 这意味着移除和插入 变成了具有线性复杂度的操作 使得这些操作比常规集慢 总有取舍的！ 但是 一旦我们熟悉了这些 数据结构是如何工作的 我们将能够根据我们需要满足的需求 和需要优化的重要操作 自信地选择合适的数据结构 来解决任何问题 选择正确的数据结构可以带来 算法上的改进 从而使代码速度提高 数百甚至数千倍 选错了反而会适得其反 因此 我认为了解这些是有用的 因为最终 它会让App更优秀 让用户更满意 这种新的OrderedSet类型 是基础中现有NSOrdered Set类型的纯Swift变体 然而 因为OrderedSet 是在一个包中实现的 所以它不能与 NSOrderedSet桥接 这意味着现有的 Objective-C API 不会被自动导入以使用新的类型 它们是彼此分离的

Collections包提供的 第三种数据结构 是标准字典类型的有序模拟 像标准字典一样 这是一个键值对序列 允许我们使用一个键作为下标 来快速查找它的对应值 与常规字典不同 键值对的顺序是明确定义的 默认情况下 它遵循键 最初插入的顺序 要追加一个新元素 我们可以给一个新键赋值 我们可以通过给现有的键赋零 来移除元素 在这些操作中 有序字典 以明确定义的顺序维护其内容

有序字典使用类似数组的整数索引 但这带来了一个有趣的问题 在我们的示例字典中 索引下标操作与 键下标发生了冲突 当我们用零下标时 我们是指访问键零的值 还是指在偏移量零处检索键值对？

我们认为基于键的下标 是字典类型的主要操作 所以为了防止这种歧义 给有序字典下标总是意味着 键控下标 OrderedDictionary 根本不提供 索引下标操作 这意味着 OrderedDictionary 不能是集合 因为集合协议需要这样的下标 因此 OrderedDictionary 只符合序列协议 但是 对于需要 集合一致性的情况 OrderedDictionary 提供了特殊的元素视图 元素是一个随机访问集合 它提供了一个返回 键值对的索引下标 从底层实现来看 常规字典类型使用两个单独的 哈希表分别存储键和值 而有序字典使用单个压缩哈希表 和两个并行数组 这可以比有序集节省更多的空间 这是Collections包中可用的 三种新数据结构 通过使用这些结构 我们可以提高App的性能 或者减少内存使用 或者同样重要的是 我们可以表达 我们无法轻松满足标准类型的约束 例如保留集中的元素顺序 因为这些新类型 都符合一些序列和集合协议 它们还与标准库提供的算法 以及凯尔之前向我们 展示的新Algorithms包 进行互操作 Swift Collections和 Swift Algorithms只是我们不断 扩展的开源软件包 列表中的两个新成员 随着我们向新平台和新领域扩展 Swift库生态系统的未来 正在逐渐成形 随着我们越来越多地利用开源包 这一点已经很明显了 我们有意提前发布这些包 而它们仍然是可改进的 我们正在GitHub上 将其开发为社区成果 所以试试吧 提出问题 打开拉取请求 这是一个从未有过的好时机 参与进来并产生影响也轻而易举 我希望你和我们一样 对这些新的Swift软件包 感到兴奋 我们迫不及待地想知道 你用这些能构建什么！ 感谢观看 继续观看会议的其余部分吧！ ♪