Swift 裡的數組去重方案

在使用 Swift 進行開發落格輸入法時,我遇到了一個很有意思的問題——去重

眾所周知,輸入法的候選在計算出來後總會有可能是重複的選項(比如碼表和詞庫中都有某個詞,也許他們編碼不同,但字是一樣的之類),這時候就需要去重,但又要保持候選的先後順序不變。

別人的解決方案

如果你去網上找,那麼你可能找到的是這樣的:

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

這樣的:

來源:https://www.hackingwithswift.com/example-code/language/how-to-remove-duplicate-items-from-an-array

或者是這樣的:

來源:https://medium.com/if-let-swift-programming/swift-array-removing-duplicate-elements-128a9d0ab8be

問題

我們先說上文中的第一個代碼塊,他直接用了 ,眾所周知,這東西和字典( Dictionary )一個樣,實際上是沒有順序的,所以你把 排列 轉換為 再轉換回 排列 確實達到了去重的目的,但極有可能讓原本的順序錯亂。

在 Swift 中, 一定程度上是能夠保持順序的,比如上文來源網頁中的例子實際上就是保持了原本的順序的,這只能是一個巧合,因為它並不保證任何內容都是原來的順序的。

第二個代碼塊的實現實際上已經非常不錯了,事實上它是我在寫這篇文章的時候意外發現的一種實現方式,利用的就是 排列過濾 方法並使用一個 Dictionary 進行過濾,它佔用了一點點額外的空間,但無可厚非。

第三個代碼塊問題在於直接用 排列包含 方法來判斷存在,這是一種非常不好的方式,實際上我在在字符串中 快速查找一文中曾討論過,Swift 中幾乎所有 包含 都沒有同等類型的 指數 或者 範圍 來的快,何況 排列 的查找速度是 O(ñ)。

更高端的解決方案

實際上,你還有更高級的解決方案,比如傳說中的“有序字典“,不過很遺憾的是 Swift 基礎框架中並沒有給出這樣高端的算法,比如一個紅黑樹實現。不過,在我找到幾個紅黑樹進行比較之後,實際上這種高級算法更慢(也許是因為我的具體場景無法體現高級算法的優勢,比如需要去重的數量不夠多? )

最終實現

總之,我最後還是根據我的經驗實現了我自己的版本,實際上上文中的第二個代碼塊(用字典實現的那個)已經很不錯了,不過,這裡還是貼出我的代碼,並對其討論:

我的實現中,使用了 作為過濾器,因為它主要就是乾這個的 :)

也有人說 Set 實際上就是紅黑樹實現,這裡我是要打個問號的,Swift 中的 Set 具體是用什麼算法實現的我並沒有查到,但似乎並不是紅黑樹。

這裡重要的地方有兩點,首先是 .reserveCapacity ,實際上對於 Swift 來說, 排列Dictionary 這類集合類型的空間是動態分配的,絕大部分時間你不需要手動去為它設定容量大小,但這裡我們追求速度,所以我手動為它設定了 排列 的長度,因為這裡目的是去重,所以最大長度絕對不會超出原本數據的大小,這樣就避免了 在去重過程中添加元素導致擴容,這個擴容的過程,實際上也是有很大的時間成本的。

另外一點是 .插入 ,通常我們會忽略掉 .插入 的返回值,畢竟它的聲明就是包含了 @discardableResult 的,但如果你仔細觀察,會發現這個方法返回一個元組,類型是 (插入: 布爾, memberAfterInsert: <元件>.元件) ,它告訴了你,這個元素是否成功插入,以及這個元素本身——也就是說,如果已經存在,那麼插入失敗。

這樣,我們就得到了一個快速、精簡的 Swift 獨特 方法。

討論

實際上,乍一看我的這個實現似乎也沒什麼了不起的地方,畢竟,也就是個集合罷了,那麼,如果是直接一點的實現,那麼大多數人可能會想到類似的,比如這樣:

這個算是上邊實現的繁瑣版本,但它很直觀,這裡我使用了 firstIndex(: 來判斷存在,要比 包含 快那麼一點點,具體效果如何呢?我們來用這樣的的代碼測試一下:

我們對一個隨手寫的數組進行去重 9999 次,計算時間,得到的結果單位是毫秒(ms): 167.54305362701416

看起來挺快的,對嗎?那麼我們來用同樣的測試代碼,試試上文中提到的用字典實現去重,我把代碼再貼過來:

同樣去重 9999 次,得到時間: 142.61806011199951 看起來不錯呢,快了 25 毫秒!

最後,是我的實現:

結果: 103.64902019500732 女士

 

當然,本文的討論是有前提限制的,比如數據量不會很大。還有就是主要針對 Swift 這個編程語言,換到其他語言,興許就還會有更方便更高效的算法也說不定(主要是 Swift 裡坑太多……),另,之前對於毫秒單位搞錯,現已更正,超尷尬的。

本文由 落格博客 原創撰寫:落格博客 » Swift 裡的數組去重方案

轉載請保留出處和原文鏈接:https://www.logcg.com/archives/3177.html

由...出版 落格博客

如非聲明,本人所著文章均為原創手打,轉載請註明本頁面鏈接和我的名字。

發表評論

您的電子郵件地址不會被公開. 必填字段標 *