本文向大家介绍稍许算法的实现:关于如何去除数组中的重复元素,并比较了三种算法之间的效率.全部代码在Xcode的Playground中实现,直观明了,适合Swift学习入门童鞋观赏.
有个前提
如题,很多童鞋立即给出解决方法,无外乎是利用Swift内置的集合(Set)或字典(Dict)的一个特性:过滤重复元素.
但由于集合和字典中元素的顺序是无法保证的,所以这建立在一个前提基础之上:结果数组元素顺序和原数组可以不同!
但本文的算法要求:在剔除重复元素之后,元素顺序和原数组必须相同,这正是数组核心特点:有序性的一种体现.
第一种实现
如果想要简单,就必须要多些限制.
如果数组元素能满足Hashable协议,我们利用内置集合也未尝不可:
extension Array where Element:Hashable{
/// 返回剔除重复元素后的数组,其元素顺序不变
public var noRepetitionUseSet:[Element]{
var set = Set<Element>(self)
var resultAry = [Element]()
for item in self{
if set.contains(item){
//只会保留第一个重复元素!!!
resultAry.append(item)
set.remove(item)
}
}
return resultAry
}
}
如上,我们首先用集合过滤所有重复的元素,然后遍历数组,只保留第一个重复的元素.这样原有数组的顺序即得以保持不变.
数组操作是麻烦之源
如果不能保证数组元素满足Hashable协议,至少它们要满足Equatable协议.
这里略微复杂的地方在于,动态删除数组的元素需要考虑到它们删除的顺序.
删除后的黑洞立即会被后续所填满,仿佛根本不存在一样. — 鲁迅
还有一个稍微棘手的问题在于:如何计算多个中间数组(它们只是原始数组的部分拷贝)元素在原始数组中对应的索引位置.
所以,这里不如让我们另辟蹊径,利用Swift的另一个特性: Optional!!!
有种类型叫:可有可无!
如果可以解决下面问题,就会使算法简单很多:
- 不用直接删除重复元素
- 简化定位元素的位置
这时Optional前来拯救我们了.
其核心思想是:不删除重复元素而是将其设置为nil!!!
extension Array where Element:Equatable{
public var noRepetition:[Element]{
var copy:[Element?] = self
//下面只有非nil值才有比较的必要.
for (i,x) in copy.enumerated(){
if x == nil {continue}
for (j,y) in copy[(i+1)...].enumerated(){
if y == nil {continue}
if x! == y! {
//将原数组中对应的重复元素设置为nil
copy[j+i+1] = nil
}
}
}
//剔除非空值,保持元素顺序
return copy.compactMap {$0}
}
}
如上,算法比较复杂,理解起来略微费劲!
永无止境
这个世界永远有更好的解决方法,就看你能不能发现了.
其实在不使用集合和字典的前提下,我们还可以这么写:
public var noRepetition2:[Element]{
var result = [Element]()
for item in self{
if !result.contains(item) {
result.append(item)
}
}
return result
}
我们只需要将每一个非重复的元素,放到一个新数组中,就完美的绕开了上面所有这些麻烦的东东…
问题来了:谁更快?快多少?
那么上面3种方法到底谁更快呢???
因为是在Playground中运行,所以很快能写一个性能计算器来得到答案:
struct Timing{
var start:Date!
mutating func timingStart(){
start = Date()
}
func timingStop()->Double{
return Date().timeIntervalSince(start)
}
mutating func timing(count:Int,working:()->Void){
var totalTiming:Double = 0.0
for _ in 0..<count{
timingStart()
working()
totalTiming += timingStop()
}
print("\(count)次平均执行时间 : \(totalTiming/Double(count))")
}
}
因为系统的复杂性,我们不可能只用一两次执行来统计准确的运行时间.
测试代码如下:
let a = [1,1,1,2,3,4,1,3,4,5,6,2,1,1,1,1,17,7,7,8,9,2,1,0,1]
var t = Timing()
t.timing(count: 1000){
_ = a.noRepetitionUseSet
}
print(a.noRepetitionUseSet)
t.timing(count: 1000){
_ = a.noRepetition
}
print(a.noRepetition)
t.timing(count: 1000){
_ = a.noRepetition2
}
print(a.noRepetition2)
结果如下:
1000次平均执行时间 : 0.002724636197090149
[1, 2, 3, 4, 5, 6, 8, 17, 7, 9, 0]
1000次平均执行时间 : 0.004712764143943787
[1, 2, 3, 4, 5, 6, 8, 17, 7, 9, 0]
1000次平均执行时间 : 0.002008106589317322
[1, 2, 3, 4, 5, 6, 8, 17, 7, 9, 0]
首先可以看到三者返回剔除重复元素后的结果是完全一样的(这是必须的),另外它们的速度是第二种比第一种慢大约2ms左右,而最后一种比第一种还快一点点.我想日常的使用还是可以接受的.
(更正:只是对于[1,1,1,2,3,4,1,3,4,5,6,2,1,1,1,1,17,7,7,8,9,2,1,0,1]这个数组来说,第二种比第一种慢2ms,但随着数组元素个数的增加,后者会比前者慢更多!)
结尾
最后总结一下:
- 第一种算法利用内置集合类,对数组元素类型有限制,但速度快,逻辑简单.
- 第二种算法依赖更少,但速度稍慢,逻辑略复杂.
- 第三种算法速度最快,依赖少,逻辑最简单,可以作为首选.
虽然第一种方法利用了内部Swift库的优化,但创建集合的时间抵消了优化的时间,所以最后一种方法胜出!!!
上面我们实现了3种剔除重复元素的算法,并且比较了它们的优劣.
大家可以自由选择,如果你有更好的算法,欢迎讨论
这就是所有的内容了.
(PS:最后还有一种很简单的实现:
public var noRepetition3:[Element]{
var curIdx = -1
return self.filter {
curIdx += 1
return self.index(of: $0) == curIdx
}
}
至于原理和速度大家可以遐想一下)
早睡早起,感谢观赏