在使用 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
問題
我們先說上文中的第一個代碼塊，他直接用了 組 ，眾所周知，這東西和字典（ Dictionary ）一個樣，實際上是沒有順序的，所以你把 排列 轉換為 組 再轉換回 排列 確實達到了去重的目的，但極有可能讓原本的順序錯亂。
在 Swift 中， 組 在一定程度上是能夠保持順序的，比如上文來源網頁中的例子實際上就是保持了原本的順序的，這只能是一個巧合，因為它並不保證任何內容都是原來的順序的。
第二個代碼塊的實現實際上已經非常不錯了，事實上它是我在寫這篇文章的時候意外發現的一種實現方式，利用的就是 排列 的 過濾 方法並使用一個 Dictionary 進行過濾，它佔用了一點點額外的空間，但無可厚非。
第三個代碼塊問題在於直接用 排列 的 包含 方法來判斷存在，這是一種非常不好的方式，實際上我在在字符串中 快速查找一文中曾討論過，Swift 中幾乎所有 包含 都沒有同等類型的 指數 或者 範圍 來的快，何況 排列 的查找速度是 O(ñ)。
更高端的解決方案
實際上，你還有更高級的解決方案，比如傳說中的“有序字典“，不過很遺憾的是 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 實際上就是紅黑樹實現，這裡我是要打個問號的，Swift 中的 Set 具體是用什麼算法實現的我並沒有查到，但似乎並不是紅黑樹。
這裡重要的地方有兩點，首先是 .reserveCapacity ，實際上對於 Swift 來說， 排列 、 Dictionary 、 組 這類集合類型的空間是動態分配的，絕大部分時間你不需要手動去為它設定容量大小，但這裡我們追求速度，所以我手動為它設定了 排列 的長度，因為這裡目的是去重，所以最大長度絕對不會超出原本數據的大小，這樣就避免了 組 在去重過程中添加元素導致擴容，這個擴容的過程，實際上也是有很大的時間成本的。
另外一點是 組 的 .插入 ，通常我們會忽略掉 .插入 的返回值，畢竟它的聲明就是包含了 @discardableResult 的，但如果你仔細觀察，會發現這個方法返回一個元組，類型是 (插入: 布爾, memberAfterInsert: 組<元件>.元件) ，它告訴了你，這個元素是否成功插入，以及這個元素本身——也就是說，如果已經存在，那麼插入失敗。
這樣，我們就得到了一個快速、精簡的 Swift 獨特 方法。
討論
實際上，乍一看我的這個實現似乎也沒什麼了不起的地方，畢竟，也就是個集合罷了，那麼，如果是直接一點的實現，那麼大多數人可能會想到類似的，比如這樣：
|
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(的: 來判斷存在，要比 包含 快那麼一點點，具體效果如何呢？我們來用這樣的的代碼測試一下：
|
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 女士
當然，本文的討論是有前提限制的，比如數據量不會很大。還有就是主要針對 Swift 這個編程語言，換到其他語言，興許就還會有更方便更高效的算法也說不定（主要是 Swift 裡坑太多……），另，之前對於毫秒單位搞錯，現已更正，超尷尬的。
本文由 落格博客 原創撰寫：落格博客 » Swift 裡的數組去重方案
轉載請保留出處和原文鏈接：https://www.logcg.com/archives/3177.html
