Categories
Swift

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

问题

我们先说上文中的第一个代码块,他直接用了 Set ,众所周知,这东西和字典( Dictionary )一个样,实际上是没有顺序的,所以你把 Array  转换为 Set  再转换回 Array  确实达到了去重的目的,但极有可能让原本的顺序错乱。

在 Swift 中, Set  在一定程度上是能够保持顺序的,比如上文来源网页中的例子实际上就是保持了原本的顺序的,这只能是一个巧合,因为它并不保证任何内容都是原来的顺序的。

第二个代码块的实现实际上已经非常不错了,事实上它是我在写这篇文章的时候意外发现的一种实现方式,利用的就是 Array  的 filter 方法并使用一个 Dictionary  进行过滤,它占用了一点点额外的空间,但无可厚非。

第三个代码块问题在于直接用 Array  的 contains 方法来判断存在,这是一种非常不好的方式,实际上我在在字符串中 快速查找一文中曾讨论过,Swift 中几乎所有 contains 都没有同等类型的 index  或者 range  来的快,何况 Array  的查找速度是 O(n)。

更高端的解决方案

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

最终实现

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

我的实现中,使用了 Set  作为过滤器,因为它主要就是干这个的 :)

也有人说 Set 实际上就是红黑树实现,这里我是要打个问号的,Swift 中的 Set 具体是用什么算法实现的我并没有查到,但似乎并不是红黑树。

这里重要的地方有两点,首先是 .reserveCapacity ,实际上对于 Swift 来说, Array 、 Dictionary 、 Set 这类集合类型的空间是动态分配的,绝大部分时间你不需要手动去为它设定容量大小,但这里我们追求速度,所以我手动为它设定了 Array  的长度,因为这里目的是去重,所以最大长度绝对不会超出原本数据的大小,这样就避免了 Set  在去重过程中添加元素导致扩容,这个扩容的过程,实际上也是有很大的时间成本的。

另外一点是 Set  的 .insert ,通常我们会忽略掉 .insert 的返回值,毕竟它的声明就是包含了 @discardableResult 的,但如果你仔细观察,会发现这个方法返回一个元组,类型是 (inserted: Bool, memberAfterInsert: Set<Element>.Element) ,它告诉了你,这个元素是否成功插入,以及这个元素本身——也就是说,如果已经存在,那么插入失败。

这样,我们就得到了一个快速、精简的 Swift unique  方法。

讨论

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

这个算是上边实现的繁琐版本,但它很直观,这里我使用了 firstIndex(of: 来判断存在,要比 contains 快那么一点点,具体效果如何呢?我们来用这样的的代码测试一下:

我们对一个随手写的数组进行去重 9999 次,计算时间,得到的结果单位是毫秒(ms): 167.54305362701416

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

同样去重 9999 次,得到时间: 142.61806011199951 看起来不错呢,快了 25 毫秒!

最后,是我的实现:

结果: 103.64902019500732 ms

 

当然,本文的讨论是有前提限制的,比如数据量不会很大。还有就是主要针对 Swift 这个编程语言,换到其他语言,兴许就还会有更方便更高效的算法也说不定(主要是 Swift 里坑太多……),另,之前对于毫秒单位搞错,现已更正,超尴尬的。

本文由 落格博客 原创撰写:落格博客 » Swift 里的数组去重方案

转载请保留出处和原文链接:https://www.logcg.com/archives/3177.html

By 落格博客

如非声明,本人所著文章均为原创手打,转载请注明本页面链接和我的名字。

发表评论

电子邮件地址不会被公开。 必填项已用*标注