在使用 Swift 进行开发落格输入法时，我遇到了一个很有意思的问题——去重。
众所周知，输入法的候选在计算出来后总会有可能是重复的选项（比如码表和词库中都有某个词，也许他们编码不同，但字是一样的之类），这时候就需要去重，但又要保持候选的先后顺序不变。
别人的解决方案
如果你去网上找，那么你可能找到的是这样的：
|
1 2 3 4 5 |
extension Array where Element : Hashable { var unique: [Element] { return Array(Set(self)) } } |
来源：https://stackoverflow.com/questions/27624331/unique-values-of-array-in-swift
这样的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
extension Array where Element: Hashable { func removingDuplicates() -> [Element] { var addedDict = [Element: Bool]() return filter { addedDict.updateValue(true, forKey: $0) == nil } } mutating func removeDuplicates() { self = self.removingDuplicates() } } |
来源：https://www.hackingwithswift.com/example-code/language/how-to-remove-duplicate-items-from-an-array
或者是这样的：
|
1 2 3 4 5 6 7 8 9 10 11 |
extension Array where Element: Equatable { mutating func removeDuplicates() { var result = [Element]() for value in self { if !result.contains(value) { result.append(value) } } self = result } } |
来源：https://medium.com/if-let-swift-programming/swift-array-removing-duplicate-elements-128a9d0ab8be
问题
我们先说上文中的第一个代码块，他直接用了 Set ，众所周知，这东西和字典（ Dictionary ）一个样，实际上是没有顺序的，所以你把 Array 转换为 Set 再转换回 Array 确实达到了去重的目的，但极有可能让原本的顺序错乱。
在 Swift 中， Set 在一定程度上是能够保持顺序的，比如上文来源网页中的例子实际上就是保持了原本的顺序的，这只能是一个巧合，因为它并不保证任何内容都是原来的顺序的。
第二个代码块的实现实际上已经非常不错了，事实上它是我在写这篇文章的时候意外发现的一种实现方式，利用的就是 Array 的 filter 方法并使用一个 Dictionary 进行过滤，它占用了一点点额外的空间，但无可厚非。
第三个代码块问题在于直接用 Array 的 contains 方法来判断存在，这是一种非常不好的方式，实际上我在在字符串中 快速查找一文中曾讨论过，Swift 中几乎所有 contains 都没有同等类型的 index 或者 range 来的快，何况 Array 的查找速度是 O(n)。
更高端的解决方案
实际上，你还有更高级的解决方案，比如传说中的“有序字典”，不过很遗憾的是 Swift 基础框架中并没有给出这样高端的算法，比如一个红黑树实现。不过，在我找到几个红黑树进行比较之后，实际上这种高级算法更慢（也许是因为我的具体场景无法体现高级算法的优势，比如需要去重的数量不够多？）
最终实现
总之，我最后还是根据我的经验实现了我自己的版本，实际上上文中的第二个代码块（用字典实现的那个）已经很不错了，不过，这里还是贴出我的代码，并对其讨论：
|
1 2 3 4 5 6 7 8 9 |
extension Array where Element:Hashable { var unique:[Element] { var uniq = Set<Element>() uniq.reserveCapacity(self.count) return self.filter { return uniq.insert($0).inserted } } } |
我的实现中，使用了 Set 作为过滤器，因为它主要就是干这个的 ：）
也有人说 Set 实际上就是红黑树实现，这里我是要打个问号的，Swift 中的 Set 具体是用什么算法实现的我并没有查到，但似乎并不是红黑树。
这里重要的地方有两点，首先是 .reserveCapacity ，实际上对于 Swift 来说， Array 、 Dictionary 、 Set 这类集合类型的空间是动态分配的，绝大部分时间你不需要手动去为它设定容量大小，但这里我们追求速度，所以我手动为它设定了 Array 的长度，因为这里目的是去重，所以最大长度绝对不会超出原本数据的大小，这样就避免了 Set 在去重过程中添加元素导致扩容，这个扩容的过程，实际上也是有很大的时间成本的。
另外一点是 Set 的 .insert ，通常我们会忽略掉 .insert 的返回值，毕竟它的声明就是包含了 @discardableResult 的，但如果你仔细观察，会发现这个方法返回一个元组，类型是 (inserted: Bool, memberAfterInsert: Set<Element>.Element) ，它告诉了你，这个元素是否成功插入，以及这个元素本身——也就是说，如果已经存在，那么插入失败。
这样，我们就得到了一个快速、精简的 Swift unique 方法。
讨论
实际上，乍一看我的这个实现似乎也没什么了不起的地方，毕竟，也就是个集合罢了，那么，如果是直接一点的实现，那么大多数人可能会想到类似的，比如这样：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
var unique:[Element] { var uniq = Set<Element>() var result:[Element] = [] for v in self { guard uniq.firstIndex(of: v) == nil else {continue} uniq.insert(v) result.append(v) } return result } |
这个算是上边实现的繁琐版本，但它很直观，这里我使用了 firstIndex(of: 来判断存在，要比 contains 快那么一点点，具体效果如何呢？我们来用这样的的代码测试一下：
|
1 2 3 4 5 6 7 |
let data = [1,2,3,4,5,6,7,8,9,0,9,8,7,6,5,4,3,2,1,4,2,3,5,6,7,45,3,43,99,687,8,5,3] var date = Date() for _ in 0..<9999 { let a = data.unique } print(Date().timeIntervalSince(date)*1000) |
我们对一个随手写的数组进行去重 9999 次，计算时间，得到的结果单位是毫秒（ms）： 167.54305362701416
看起来挺快的，对吗？那么我们来用同样的测试代码，试试上文中提到的用字典实现去重，我把代码再贴过来：
|
1 2 3 4 5 6 |
var unique:[Element] { var addedDict = [Element: Bool]() return filter { addedDict.updateValue(true, forKey: $0) == nil } } |
同样去重 9999 次，得到时间： 142.61806011199951 看起来不错呢，快了 25 毫秒！
最后，是我的实现：
|
1 2 3 4 5 6 7 |
var unique:[Element] { var uniq = Set<Element>() uniq.reserveCapacity(self.count) return self.filter { return uniq.insert($0).inserted } } |
结果： 103.64902019500732 ms
当然，本文的讨论是有前提限制的，比如数据量不会很大。还有就是主要针对 Swift 这个编程语言，换到其他语言，兴许就还会有更方便更高效的算法也说不定（主要是 Swift 里坑太多……），另，之前对于毫秒单位搞错，现已更正，超尴尬的。
本文由 落格博客 原创撰写：落格博客 » Swift 里的数组去重方案
转载请保留出处和原文链接：https://www.logcg.com/archives/3177.html
