可搜索,可注册,可登录,致敬逗比大佬!尽在救援版逗比根据地 dbgjd.com
投稿文章 | 广告合作 | Telegram 群组 / 公告频道 / 使用教程

Swift 里的数组去重方案

News 转载自https://www.logcg.com 76℃ 0评论
最近更新:5th 三月, 2019

在使用 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 里的数组去重方案

喜欢 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址