Swift 里的数组去重方案

最近更新：5th 三月, 2019

在使用 Swift 进行开发落格输入法时，我遇到了一个很有意思的问题—— 去重 。

众所周知，输入法的候选在计算出来后总会有可能是重复的选项（比如码表和词库中都有某个词，也许他们编码不同，但字是一样的之类），这时候就需要去重，但又要保持候选的先后顺序不变。

别人的解决方案

如果你去网上找，那么你可能找到的是这样的：

extension Array where Element : Hashable {
    var unique: [Element] {
        return Array(Set(self))
    }
}

来源： https://stackoverflow.com/questions/27624331/unique-values-of-array-in-swift

这样的：

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

或者是这样的：

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 的查找……

更高端的解决方案

实际上，你还有更高级的解决方案，比如传说中的“ 有序字典 ”，不过很遗憾的是 Swift 基础框架中并没有给出这样高端的算法，比如一个 红黑树 实现。不过，在我找到几个 红黑树 进行比较之后，实际上这种高级算法更慢（也许是因为我的具体场景无法体现高级算法的优势，比如需要去重的数量不够多？）

最终实现

总之，我最后还是根据我的经验实现了我自己的版本，实际上上文中的第二个代码块（用字典实现的那个）已经很不错了，不过，这里还是贴出我的代码，并对其讨论：

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 方法。

讨论

实际上，乍一看我的这个实现似乎也没什么了不起的地方，毕竟，也就是个集合罢了，那么，如果是直接一点的实现，那么大多数人可能会想到类似的，比如这样：

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 快那么一点点，具体效果如何呢？我们来用这样的的代码测试一下：

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)*100)

我们对一个随手写的数组进行去重 9999 次，计算时间，得到的结果单位是毫秒（ms）： 16 . 754305362701416

看起来挺快的，对吗？那么我们来用同样的测试代码，试试上文中提到的用字典实现去重，我把代码再贴过来：

var unique:[Element] {
        var addedDict = [Element: Bool]()
        return filter {
            addedDict.updateValue(true, forKey: $0) == nil
        }
    }

同样去重 9999 次，得到时间： 14 . 261806011199951 看起来不错呢，快了 2 毫秒！

最后，是我的实现：

var unique:[Element] {
        var uniq = Set<Element>()
        uniq.reserveCapacity(self.count)
        return self.filter {
            return uniq.insert($0).inserted
        }
    }

结果： 10 . 364902019500732 ms