golang自定义类型slice去重问题探究

# 问题由来 最近在做一个需求，需要对不同类型slice做去重，比如去重的对象如下： ``` inArr := []int64{1, 3, 6, 3} strArr := []string{"11", "22", "22", "44"} ``` 按下面这样： ``` func Dedumplicate([]int64) []int64 {} func Dedumplicate([]string) []string {} ``` 这样去实现肯定是不妥的； 因为这种实现太繁琐，每增加一种类型都要增加一个函数，毫无通用性可言。 所以，**通用且好用的去重函数是必然的选择**。 # 千篇一律的答案 在网上搜了一圈，基本都是类似下面的方案： - 方案一：输入一个interface，函数体内不改变slice值，返回一个新的[]interface ``` func SliceRemoveDuplicate(a interface{}) (ret []interface{}) {} ``` - 方案二：输入的是具体的类型，函数体类改变输入的slice，没有返回值 ``` func UniqueSlice(slice *[]int) {} ``` 两种方案都能一定成都上满足项目的需求，但： 方案一使用时还不太方便，还需要再把[]interface{} 转化成 具体类型的slice， 方案二则不具备通用性，每新增类型都需要再增加函数； # 是否能更好用一点 我期望的结果是，函数实现后，能按照如下两种方式供业务选择： - 方式一：不改变输入的slice，输出的是一个interface ``` func Dedumplicate(data interface{}) interface{} {} ``` 这样使用时就如下： ``` inArr := []int64{1, 3, 6, 3} outData := Dedumplicate(inArr) outArr, ok := outData.([]int64) ``` 该方式省去了将[]interface转化为[]int64的逻辑，而直接用断言即可。 - 方式二：改变输入的slice，无返回值 ``` inArr := []int64{1, 3, 6, 3} outArr := DedumplicateOrigial(&inArr) ``` 该方式使用时则更方便了。 # show me code 上面两种方式我都实现了，先附上代码吧，有需要的同学可以直接拿去用。 ## 方式一的实现 ### 代码 ``` func Dedumplicate(data interface{}) interface{} { inArr := reflect.ValueOf(data) if inArr.Kind() != reflect.Slice && inArr.Kind() != reflect.Array { return data } existMap := make(map[interface{}]bool) outArr := reflect.MakeSlice(inArr.Type(), 0, inArr.Len()) for i := 0; i < inArr.Len(); i++ { iVal := inArr.Index(i) if _, ok := existMap[iVal.Interface()]; !ok { outArr = reflect.Append(outArr, inArr.Index(i)) existMap[iVal.Interface()] = true } } return outArr.Interface() } ``` ### 使用 ``` inArr := []int64{1, 3, 6, 3} fmt.Println("before: ", inArr) outArr := Dedumplicate(inArr).([]int64) fmt.Println("after: ", outArr) ``` ### 结果 ``` before: [1 3 6 3] after: [1 3 6] ``` 符合预期。 ## 方式二的实现 ### 代码 ``` // 传入的data必须是 指向切片的指针 func DedumplicateOrigial(data interface{}) { dataVal := reflect.ValueOf(data) if dataVal.Kind() != reflect.Ptr { fmt.Println("input data.kind is not pointer") return } tmpData := Dedumplicate(dataVal.Elem().Interface()) tmpDataVal := reflect.ValueOf(tmpData) dataVal.Elem().Set(tmpDataVal) } ``` 为了减少代码篇幅，实现中调用Dedumplicate函数复用了方案一的去重逻辑。 ### 使用 为了说明通用性，这次改为对[]string去重 ``` strArr := []string{"11", "22", "22", "44", "44", "55"} fmt.Println("before: ", strArr) DedumplicateOrigial(&strArr) // 注意：是切片的指针 fmt.Println("after: ", strArr) ``` ### 结果 ``` before: [11 22 22 44 44 55] after: [11 22 44 55] ``` 符合预期。 # 实现思路 说实话，实现上面的两个效果，还真的破费我的精神的； 中间有问过一些golang比较熟的同学，貌似都没考虑过该问题， 所以一时也没能帮忙给出答案。 下面简单给出我的思考过程，也希望能增强自己对golang的认识。 ## 具体类型的实现 **通用往往是对个例的抽象**，或者说是是归纳与演绎两大法宝之**归纳法**。 以对[]int64的去重为例： ``` func DedumplicateInt64(data []int64) []int64 { outArr := make([]int64, 0) existMap := make(map[int64]bool) for _, v := range data { if _, ok := existMap[v]; !ok { outArr = append(outArr, v) existMap[v] = true } } return outArr } ``` 小说明：这里的existMap其实就是充当set的作用。 ## 利用反射实现方式一 怎样将上面的逻辑***翻译***成对下面通用interface的处理呢？ ``` func Dedumplicate(data interface{}) interface{} {} ``` 答案是：反射！ 因为interface中保存着 **运行时** 原数据的类型和值， 而反射的特性用于处理运行时才知道类型的数据再合适不过了。 ### interface和reflect.Value的互转 - func ValueOf(i interface{}) Value 该函数可以获取到Interface{}实际存储的值； - func (v Value) Interface() (i interface{}) 该函数可以将实际存储的值转化为interface{}; ## 操作任意类型的slice - reflect.MakeSlice - reflect.Append 有了上面两个基础知识后，翻译也就水到渠成了。 ## 从方式一到方式二 方式二修改原slice，节约空间的方法是用类似于quicksort的**IN-PLACE**算法， 但本文主要是探究语言层面的实现，因而对算法的优化有所忽略， 所以这里先调用方案一拿到去重后的结果，再修改原输入的slice。 怎么修改原slice，我还真的卡了好长时间！ ### 注意点：slice的传参，是值传递！ 所以要想修改原切片，传给参数的值必须是 指向切片的指针！ ### reflect.Value的两个重要函数 - func (v Value) Elem() Value ``` // Elem returns the value that the interface v contains // or that the pointer v points to. // It panics if v's Kind is not Interface or Ptr. // It returns the zero Value if v is nil. ``` 所以Elem()相当于*ptr的作用，也就是解引用。 - func (v Value) Set(x Value) ### 发散：从另一种实现看slice的内部结构 ``` func DedumplicateOrigial(data interface{}) { dataVal := reflect.ValueOf(data) if dataVal.Kind() != reflect.Ptr { fmt.Println("input data.kind is not pointer") return } tmpData := Dedumplicate(dataVal.Elem().Interface()) tmpDataVal := reflect.ValueOf(tmpData) intArrP := (*reflect.SliceHeader)(unsafe.Pointer(dataVal.Pointer())) intArrP.Len = tmpDataVal.Len() intArrP.Cap = tmpDataVal.Cap() intArrP.Data = tmpDataVal.Pointer() } ``` 上面这种实现也是ok的。 因为slice实际上是下面这个结构： ``` // SliceHeader is the runtime representation of a slice. // It cannot be used safely or portably and its representation may // change in a later release. // Moreover, the Data field is not sufficient to guarantee the data // it references will not be garbage collected, so programs must keep // a separate, correctly typed pointer to the underlying data. type SliceHeader struct { Data uintptr Len int Cap int } ``` # 性能问题 文章发出后，有同学问到反射的性能问题， 我这里做了一个简单的实验，发现反射确实很耗性能的，具体说明如下： ## 先说结论 使用reflect比不使用reflect慢了80%左右！ ## 运行结果 ### 环境说明 macOs 版本 10.14.5 MacBook Pro (15-inch, 2019) 处理器 2.6 GHz Intel Core i7 ### 结果输出 运行去重函数 10000 次 DedumplicateInt64 spend time: %v 2845 微秒 DedumplicateInterface spend time: %v 14884 微秒 (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = 80 % 运行去重函数 50000 次 DedumplicateInt64 spend time: %v 14014 微秒 DedumplicateInterface spend time: %v 77174 微秒 (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = 81 % 运行去重函数 100000 次 DedumplicateInt64 spend time: %v 27523 微秒 DedumplicateInterface spend time: %v 116427 微秒 (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = 76 % 运行去重函数 500000 次 DedumplicateInt64 spend time: %v 108229 微秒 DedumplicateInterface spend time: %v 554998 微秒 (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = 80 % 运行去重函数 1000000 次 DedumplicateInt64 spend time: %v 232808 微秒 DedumplicateInterface spend time: %v 1113486 微秒 (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = 79 % 运行去重函数 5000000 次 DedumplicateInt64 spend time: %v 1114360 微秒 DedumplicateInterface spend time: %v 5022837 微秒 (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = 77 % ## 代码详情 timesArr := []int{10000, 50000, 100000, 500000, 1000000, 5000000} for _, times := range timesArr { inArr := []int64{1, 3, 6, 3, 2} fmt.Printf("运行去重函数 %v 次\n", times) now1 := nowNano() for i := 0; i < times; i++ { _ = DedumplicateInt64(inArr) } now2 := nowNano() deltTime12 := (now2 - now1) / 1000 fmt.Println(" DedumplicateInt64 spend time: %v", deltTime12, "微秒") now3 := nowNano() for i := 0; i < times; i++ { _ = Dedumplicate(inArr) // 这里使用反射 } now4 := nowNano() deltTime34 := (now4 - now3) / 1000 fmt.Println(" DedumplicateInterface spend time: %v", deltTime34, "微秒") fmt.Println(" (DedumplicateInterface-DedumplicateInt64)/DedumplicateInterface = ", 100*(deltTime34-deltTime12)/deltTime34, "%") } # 喜欢的话，关注我的公众号哦 公众号1： Golang道与术 （希望从日常工作中的一个小点，深入浅出讲解golang、后台开发的知识点，欢迎一起探讨。） 公众号2: 程序员再就业（旨在帮助程序员更好的就业） 内推群：