一文带你读懂 Swift 社区最新开源的算法库

关注
发布于: 2020 年 10 月 23 日
最近 Swift 社区动作频频，又是登陆 Windows，又是推出底层基础库。现在又推出了 Swift 算法库，现在让我们看看里面到底有什么内容，是否值得现在在生产中应用，面对内容丰富的 raywenderlich/swift-algorithm-club 是否有足够的竞争力呢。
﻿
介绍﻿
仓库地址：https://github.com/apple/swift-algorithms
﻿
目前项目还是 0.0.1 版，只提供 SwiftPM 包管理支持。一共包含 11 种算法，仅针对序列与集合类型，包含的算法如下：
﻿
排列与组合类算法：Combinations / Permutations
变换类算法：Rotate / Partition
集合合并类算法：Chain / Product / Cycle
子集合操作算法：Random Sampling / Unique
其他操作算法：Chunked / Indexed
﻿
使用方法﻿
在 Xcode 11 及以上已经集成了 Swift Package 的使用，在 project 的设置中添加一个 package 即可，地址：https://github.com/apple/swift-algorithms, 选择 0.0.1 版本。
﻿
如果使用 Package.swift 文件，添加如下内容：
let package = Package(
    // name, platforms, products, etc.
    dependencies: [
        .package(url: "https://github.com/apple/swift-algorithms", from: "0.0.1"),
        // other dependencies
    ],
    targets: [
        .target(name: "<target>", dependencies: [
            .product(name: "Algorithms", package: "swift-algorithms"),
        ]),
        // other targets
    ]
)
﻿
排列组合CombinationsCombinations 主要用来生成集合的所有可能组合结果，如果有两个元素值相同也算作不同的元素，用法如下：
let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2) {
    print(combo)
}
// [10, 20]
// [10, 30]
// [10, 40]
// [20, 30]
// [20, 40]
// [30, 40]
let numbers2 = [20, 10, 10]
for combo in numbers2.combinations(ofCount: 2) {
    print(combo)
}
// [20, 10]
// [20, 10]
// [10, 10]
﻿
Combinations 结构体实现了 Sequence 协议，通过迭代来读取每种组合，如果需要直接得到所有结果，转成数组即可：
let numbers = [10, 20, 30, 40]
let combinedArray = Array(numbers.combinations(ofCount: 3))
print(combinedArray)
// [[10, 20, 30], [10, 20, 40], [10, 30, 40], [20, 30, 40]]
﻿
PermutationsPermutations 用于生成集合的全排列，也是通过遵守 Sequence 协议的方式来实现，可以默认包含所有元素，也可以指定个数，同样相同的值作为不同的元素对待：
let numbers = [10, 20, 30]
for perm in numbers.permutations() {
    print(perm)
}
// [10, 20, 30]
// [10, 30, 20]
// [20, 10, 30]
// [20, 30, 10]
// [30, 10, 20]
// [30, 20, 10]
for perm in numbers.permutations(ofCount: 2) {
    print(perm)
}
// [10, 20]
// [10, 30]
// [20, 10]
// [20, 30]
// [30, 10]
// [30, 20]
﻿
集合变换RotateRotate 用于将集合中的一段数据移动到最前面，如下面代码将 index = 2 开始的后面所有元素都移动到最前面，并返回原来最前面元素移动后的新 index：
var numbers = [10, 20, 30, 40, 50, 60]
let p = numbers.rotate(at: 2)
// numbers == [30, 40, 50, 60, 10, 20]
// p == 4
﻿
还可以选择集合中的某一部分进行移动，下面将索引为 0..<3 范围内的元素，从 index = 1 处移动到该范围的最前面，范围外的其他元素保持不动：
var numbers = [10, 20, 30, 40, 50, 60]
numbers.rotate(subrange: 0..<3, at: 1)
// numbers = [20, 30, 10, 40, 50, 60]
﻿
Rotate 算法经常用于解决分治算法中的写时复制与切片修改问题。
PartitionPartition 用于根据指定条件将集合划分为两个部分，符合条件的移动到集合末尾。
提供了以下几个方法：
stablePartition(by:) 将符合闭包判断条件的元素移动至数组末尾，移动后的元素仍然保持原来的相对顺序，并返回移动后符合条件部分的第一个元素的索引（如果没有符合条件的元素，则返回数组末尾元素的下一个索引）：
numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers.stablePartition(by: { $0.isMultiple(of: 20) })
// numbers = [10, 30, 50, 70, 20, 40, 60, 80]
﻿
stablePartition(subrange:by:) 在指定范围内并将符合条件的元素移动至范围的末尾：
numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers.stablePartition(subrange: 1..<4, by: { $0.isMultiple(of: 20) })
// numbers = [10, 30, 20, 40, 50, 60, 70, 80]
﻿
有一个问题需要注意一下：在 0.0.1 版本中 stablePartition(subrange:by:) 方法是有缺陷的，如果设定的 subrange 未覆盖全部集合元素将会报错，笔者已经对这个问题提交了一个 pr 并合并到了主干，pr 链接。
﻿
另外需要注意，swift 内置的集合方法中已经提供了一个 partition(by:) 方法，但这个方法只是将符合条件的元素移动至末尾，并不保证元素移动后的相对位置，partition 的时间复杂度是 O(n), stablePartition 的时间复杂度是 O(n log n)：
var numbers = [10, 100, 30, 40, 50, 60, 70, 80]
let p2 = numbers.partition(by: { $0.isMultiple(of: 20) })
// numbers = [10, 70, 30, 50, 40, 60, 100, 80]
﻿
还提供了一个方法，获取已经进行了 partition 操作的集合的第一个符合条件元素索引：
let numbers = [10, 30, 50, 70, 20, 40, 60]
let p = numbers.partitioningIndex(where: { $0.isMultiple(of: 20) })
// p = 4
// numbers[..<p] == [10, 30, 50, 70]
// numbers[p...] = [20, 40, 60]
﻿
集合合并ChainChain 用于将两个集合合并为一个集合：
let numbers = [10, 20, 30].chained(with: 1...5)
// Array(numbers) == [10, 20, 30, 1, 2, 3, 4, 5]
// 
let letters = "abcde".chained(with: "FGHIJ")
// String(letters) == "abcdeFGHIJ"
Chain 类型实现了 Sequence 与 Collection 协议，可以当成普通的集合类型来使用。
ProductProduct 用于提供两个集合所有元素的俩俩配对组合的遍历支持：
let seasons = ["winter", "spring", "summer", "fall"]
for (year, season) in product(1900...2020, seasons) {
    print(year, season)
}
// 1900 winter
// 1900 spring
// 1900 summer
// 1900 fall
// 1902 winter
// ..
// 2020 fall
product 方法要求传入的第一个参数遵守 Sequence 协议，而第二个参数遵守 Collection 协议，因为第一个参数只需要遍历一次，而第二参数需要多次遍历，Sequence 协议不保证重复遍历输出一样的值。
CycleCycle 提供无限遍历一个集合的能力：
for (odd, n) in zip([true, false].cycled(), 1...) {
  print(odd, n)
}
// true 1
// false 2
// true 3
// false 4
// true 5
// false 6
// ...
﻿
或者指定重复遍历的次数：
for x in (1...3).cycled(times: 3) {
    print(x)
}
// 1 2 3 1 2 3 1 2 3
﻿
cycled(times:) 方法组合了标准库中的 repeatElement 和 joined 方法，提供了更方便的有限次重复集合的方法。
子集合操作Random SamplingRandom Sampling 提供了从集合中随机挑选元素形成新的集合的能力 ，每次执行的结果都可能不同：
var source = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
source.randomSample(count: 4)
// e.g. [30, 10, 70, 50]
﻿
还提供了一个 randomStableSample(count:) 方法保证挑选之后的集合保持原有元素的相对顺序：
source.randomStableSample(count: 4)
// e.g. [20, 30, 80, 100]
﻿
还可以自定义随机数生成方法：
var rng = SplitMix64(seed: 0)
source.randomSample(count: 4, using: &rng)
UniqueUnique 可以去除集合中重复的元素，内部利用 Set 类型来实现：
let numbers = [1, 2, 3, 3, 2, 3, 3, 2, 2, 2, 1]
let unique = numbers.uniqued()
// unique == [1, 2, 3]
﻿
还可以提供一个闭包来确定是否唯一：
let source = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
let uniq = source.uniqued { $0 % 12 }
// [10, 20, 30, 40, 50, 60]
以上代码中，除以 12 余数相同的元素不再出现在结果中。
﻿
其他集合操作ChunkedChunked 可以将一个集合按照一定条件划分为包含多个子集的新集合：
let numbers = [10, 20, 30, 10, 40, 40, 10, 20]
let chunks = numbers.chunked(by: { $0 <= $1 })
// [[10, 20, 30], [10, 40, 40], [10, 20]]
﻿
以上代码根据 { $0 <= $1 } 这个闭包将原数组划分为多个升序子集合
﻿
还提供了一个 chunked(on:) 方法，根据其中闭包计算的结果比对是否相同，相同的元素在一个子集里：
let names = ["David", "Kyle", "Karoy", "Nate"]
let chunks = names.chunked(on: \.first!)
// [["David"], ["Kyle", "Karoy"], ["Nate"]]
以上代码将首字母相同的放在一个子集里。
﻿
IndexedIndexed 将集合转换为一个新的集合，每个元素为一个包含了原集合元素的索引与值的元组：
let numbers = [10, 20, 30, 40, 50]
var matchingIndices: Set<Int> = []
for (i, n) in numbers.indexed() {
    print(i, n)
}
// 0 10
// 1 20
// 2 30
// 3 40
// 4 50
﻿
总结从上面内容可以看到，Swift 算法库现在还比较简单，很多地方还待完善，等社区贡献了更多内容后未来还是值得期待的，以后不用再手写各种常用算法了。
﻿
发布于: 2020 年 10 月 23 日阅读数: 43
原文链接:【http://xie.infoq.cn/article/9a469eb206683e6c67ea1f92c】。文章转载请联系作者。
镜画者

关注
还未添加个人签名 2017.11.23 加入
https://github.com/pmtao
发布
暂无评论
创作场景

一文带你读懂 Swift 社区最新开源的算法库

介绍

使用方法

排列组合

Combinations

Permutations

集合变换

Rotate

Partition

集合合并

Chain

Product

Cycle

子集合操作

Random Sampling

Unique

其他集合操作

Chunked

Indexed

总结

镜画者

评论
