Meet the Swift Algorithms and Collections packages
Swift & UI 入门 20m

认识 Swift Algorithms 和 Collections 包

Meet the Swift Algorithms and Collections packages

2021年6月10日

在 Apple 官方观看视频

一句话判断

Swift Algorithms 补上了标准库缺失的几十个集合操作（chunked、 uniqued、partitioned），Swift Collections 提供了 Deque 和 OrderedDictionary——两个包加起来让你的集合操作代码少写一半。

这场 Session 讲了什么

Session 介绍了 Apple 开源的两个 Swift 包：Swift Algorithms 和 Swift Collections。

Swift Algorithms 提供了一组集合操作的算法，填补了标准库的空白。包括：chunked(into:)（按大小分块）、chunked(by:)（按条件分块）、uniqued()（去重）、partitioned(by:)（分区）、minAndMax()（同时找最小和最大值）、adjacentPairs()（相邻元素配对）等。每个算法都有 O(n) 或更优的时间复杂度保证。

Swift Collections 提供了标准库中没有的数据结构。第一个版本包含 Deque（双端队列，头尾插入删除都是 O(1)）和 OrderedDictionary（有序字典，保持插入顺序的同时支持 O(1) 查找）。

两个包都是开源的，通过 Swift Package Manager 引入。

值得深挖的点

chunked 的两种模式

chunked(into: 3) 把数组按固定大小分块——[1,2,3,4,5,6,7] 变成 [[1,2,3],[4,5,6],[7]]。chunked(by: { $0.type != $1.type }) 按条件分块——当相邻元素满足条件时切分。后者在处理分类数据时特别有用——比如把一个混合的日志列表按日期分块，同一天的日志在同一个 chunk 中。

Deque 为什么比 Array 快

Array 在头部插入需要 O(n)（所有元素后移）。Deque 使用环形缓冲区（ring buffer），头尾插入都只需要 O(1)。当你的代码中有频繁的 insert(at: 0) 或 removeFirst() 操作时，用 Deque 替代 Array 会有显著性能提升。Swift Collections 的 Deque 实现还保证了内存连续性（和 Array 一样有 withUnsafeContiguousStorage），不会比 Array 慢太多。

代码片段

Swift Algorithms 常用操作

import Algorithms

let numbers = [1, 2, 2, 3, 4, 4, 5]

// 去重（保持顺序）
let unique = numbers.uniqued()  // [1, 2, 3, 4, 5]

// 按大小分块
let chunks = numbers.chunked(into: 3)  // [[1,2,2], [3,4,4], [5]]

// 按条件分块
let items = [(type: "A", val: 1), (type: "A", val: 2), (type: "B", val: 3)]
let grouped = items.chunked { $0.type == $1.type }
// [[(A,1), (A,2)], [(B,3)]]

// 同时找最小和最大值（一次遍历）
if let (min, max) = numbers.minAndMax() {
    print("范围: \(min) - \(max)")  // 范围: 1 - 5
}

// 相邻元素配对
for (first, second) in numbers.adjacentPairs() {
    print("\(first), \(second)")  // 1,2  2,2  2,3  ...
}

Deque 的使用

import Collections

// 双端队列：头尾都是 O(1) 操作
var deque: Deque<Int> = [1, 2, 3]

deque.prepend(0)   // 头部插入 O(1)  [0, 1, 2, 3]
deque.append(4)    // 尾部插入 O(1)  [0, 1, 2, 3, 4]

deque.popFirst()   // 头部删除 O(1)  -> 0
deque.popLast()    // 尾部删除 O(1)  -> 4

// deque 现在是 [1, 2, 3]

// 当 BFS 队列用
func bfs(graph: [Int: [Int]], start: Int) -> [Int] {
    var visited: Set<Int> = []
    var queue: Deque<Int> = [start]
    var order: [Int] = []
    
    while let node = queue.popFirst() {
        guard !visited.contains(node) else { continue }
        visited.insert(node)
        order.append(node)
        queue.append(contentsOf: graph[node] ?? [])
    }
    return order
}

OrderedDictionary 的使用

import Collections

// 有序字典：保持插入顺序，同时 O(1) 查找
var orderedDict: OrderedDictionary<String, Int> = [:]

orderedDict["苹果"] = 3
orderedDict["香蕉"] = 5
orderedDict["橙子"] = 2

// 遍历时保持插入顺序
for (key, value) in orderedDict {
    print("\(key): \(value)")  // 苹果: 3, 香蕉: 5, 橙子: 2
}

// 通过索引访问
orderedDict[0]  // (key: "苹果", value: 3)
orderedDict["香蕉"]  // 5（和普通 Dictionary 一样 O(1)）

// 排序后仍然是有序字典
let sorted = orderedDict.sorted { $0.value > $1.value }
// [(key: "香蕉", value: 5), (key: "苹果", value: 3), (key: "橙子", value: 2)]

最佳实践

引入策略： 两个包都是轻量级的（Algorithms 只有算法扩展，Collections 只有数据结构），不会增加 App 体积太多。新项目建议直接引入，在 Package.swift 中添加依赖。已有项目可以在需要时逐步引入，不需要全量迁移。

替代标准库的模式： 看到代码中有 filter + map 链式操作时，检查 Algorithms 是否有一步到位的方法。看到代码中有 insert(at: 0) 时，考虑用 Deque。需要保持插入顺序的字典场景，用 OrderedDictionary。

还有什么值得关注

  • Swift Algorithms 的 product 函数可以计算笛卡尔积。
  • indexed() 方法返回 (index, element) 对的序列，比手动 enumerated() 更安全。
  • Swift Collections 计划在未来添加更多数据结构（如 Heap、Bit Set）。
WWDC 2021