Golang struct slice 去重

我需要对一个struct slice进行去重。怎么做呢?以下是一种时间复杂度为O(n^2)的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeDuplicate(personList []Person) []Person {
result := []Person{}
for i := range personList {
flag := true
for j := range result {
if personList[i].Name == result[j].Name {
flag = false
break
}
}
if flag {
result = append(result, personList[i])
}
}
return result
}

显然,两个结构体之间是没法直接做对比的。我可以选择结构体中的一个成员作为去重的依据,或者先将结构体Marshal,然后对比两个字符串。

但是,上面这种方法有两个for-range嵌套,时间复杂度是O(n^2),所以当slice的长度比较大时,代码执行时间还是比较耗时的。实测1w条数据大概耗时0.6s。

下面是一种使用map的方式去重的方式,也就是以空间换时间啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeDuplicate(personList []Person) []Person {
resultMap := map[string]bool{}
for _, v := range personList {
data, _ := json.Marshal(v)
resultMap[string(data)] = true
}
result := []Person{}
for k := range resultMap {
var t Person
json.Unmarshal([]byte(k), &t)
result = append(result, t)
}
return result
}

我们将personList转换为map。由于map天然具有key不能重复的属性,所以利用map去重是很合适的。在下面再将map转换为一个slice。

而且,这次我没有使用struct中的一个元素作为重复的标准,而是将整个struct先序列化再进行字符串的比较。

有人可能会问,能不能直接以struct作为map的key呢?比如这样:map[person]bool,答案是不行的。如果一定要以struct作为key,也许你可以将struct的指针作为key,但那样的话就没法用作去重了。

这时,1w个元素的slice进行去重,耗时将近0.1s。

其实这段代码还有一个性能优化的点,就是将encoding/json替换为第三方的json库。在Github上可以找到很多,我选择了https://github.com/json-iterator/go这个库,可以(几乎)无缝替换系统json库,性能比系统json库好不少,据说更快的原因是没有使用反射。

替换json-iterator/go后,代码的执行时间进一步下降到了0.02s,性能优化30倍。对于将来进一步的更大数据量,比如10万条数据的slice,代码执行时间如果能从6s下降为0.2s,还是非常可观的。