如何为公司建立网站,Wordpress也,滁州网站seo,2d游戏制作软件文章目录 遍历二分查找map key性能总结 之前在知乎看到一个问题#xff1a;为什么 Golang 没有像 Python 中 in 一样的功能#xff1f;于是#xff0c;搜了下这个问题#xff0c;发现还是有不少人有这样的疑问。 补充#xff1a;本文写于 2019 年。GO 现在已经支持泛型为什么 Golang 没有像 Python 中 in 一样的功能于是搜了下这个问题发现还是有不少人有这样的疑问。 补充本文写于 2019 年。GO 现在已经支持泛型而且新增了一个 slices 包已经支持了 Contains 方法。 今天来谈谈这个话题。
in 是一个很常用的功能有些语言中可能也称为 contains虽然不同语言的表示不同但基本都是有的。不过可惜的是Go 却没有它即没有提供类似 Python 操作符 in也没有像其他语言那样提供这样的标准库函数如 PHP 中 in_array。
Go 的哲学是追求少即是多。我想或许 Go 团队觉得这是一个实现起来不足为道的功能吧。
为何说微不足道如果要自己实现又该如何做呢
我所想到的有三种实现方式一是遍历二是 sort 的二分查找三是 map 的 key 索引。
本文相关源码已经上传在我的 github 上poloxue/gotin。
遍历
遍历应该是我们最容易想到的最简单的实现方式。
示例如下
func InIntSlice(haystack []int, needle int) bool {for _, e : range haystack {if e needle {return true}}return false
}上面演示了如何在一个 []int 类型变量中查找指定 int 是否存在的例子是不是非常简单由此我们也可以感受到我为什么说它实现起来微不足道。
这个例子有个缺陷它只支持单一类型。如果要支持像解释语言一样的通用 in 功能则需借助反射实现。
代码如下
func In(haystack interface{}, needle interface{}) (bool, error) {sVal : reflect.ValueOf(haystack)kind : sVal.Kind()if kind reflect.Slice || kind reflect.Array {for i : 0; i sVal.Len(); i {if sVal.Index(i).Interface() needle {return true, nil}}return false, nil}return false, ErrUnSupportHaystack
}为了更加通用In 函数的输入参数 haystack 和 needle 都是 interface{} 类型。
简单说说输入参数都是 interface{} 的好处吧主要有两点如下
其一haystack 是 interface{} 类型使 in 支持的类型不止于 slice还包括 array。我们看到函数内部通过反射对 haystack 进行了类型检查支持 slice切片与 array数组。如果是其他类型则会提示错误增加新的类型支持如 map其实也很简单。但不推荐这种方式因为通过 _, ok : m[k] 的语法即可达到 in 的效果。
其二haystack 是 interface{}则 []interface{} 也满足要求并且 needle 是 interface{}。如此一来我们就可以实现类似解释型语言一样的效果了。
怎么理解直接示例说明如下
gotin.In([]interface{}{1, two, 3}, two)haystack 是 []interface{}{1, “two”, 3}而且 needle 是 interface{}此时的值是 “two”。如此看起来是不是实现了解释型语言中元素可以是任意类型不必完全相同效果。如此一来我们就可以肆意妄为的使用了。
但有一点要说明In 函数的实现中有这样一段代码
if sVal.Index(i).Interface() needle {...
}Go 中并非任何类型都可以使用 比较的如果元素中含有 slice 或 map则可能会报错。
二分查找
以遍历确认元素是否存在有个缺点那就是如果数组或切片中包含了大量数据比如 1000000 条数据即一百万最坏的情况是我们要遍历 1000000 次才能确认时间复杂度 On。
有什么办法可以降低遍历次数
自然而然地想到的方法是二分查找它的时间复杂度 log2(n) 。但这个算法有前提需要依赖有序序列。
于是第一个要我们解决的问题是使序列有序Go 的标准库已经提供了这个功能在 sort 包下。
示例代码如下
fmt.Println(sort.SortInts([]int{4, 2, 5, 1, 6}))对于 []int我们使用的函数是 SortInts如果是其他类型切片sort 也提供了相关的函数比如 []string 可通过 SortStrings 排序。
完成排序就可以进行二分查找幸运的是这个功能 Go 也提供了[]int 类型对应函数是 SearchInts。
简单介绍下这个函数先看定义
func SearchInts(a []int, x int) int输入参数容易理解从切片 a 中搜索 x。重点要说下返回值这对于我们后面确认元素是否存在至关重要。返回值的含义返回查找元素在切片中的位置如果元素不存在则返回在保持切片有序情况下插入该元素应该在什么位置。
比如序列如下
1 2 6 8 9 11假设x 为 6查找之后将发现它的位置在索引 2 处x 如果是 7发现不存在该元素如果插入序列将会放在 6 和 8 之间索引位置是 3因而返回值为 3。
代码测试下
fmt.Println(sort.SearchInts([]int{1, 2, 6, 8, 9, 11}, 6)) // 2
fmt.Println(sort.SearchInts([]int{1, 2, 6, 8, 9, 11}, 7)) // 3如果判断元素是否在序列中只要判断返回位置上的值是否和查找的值相同即可。
但还有另外一种情况如果插入元素位于序列最后例如元素值为 12插入位置即为序列的长度 6。如果直接查找 6 位置上的元素就可能发生越界的情况。那怎么办呢其实判断返回是否小于切片长度即可小于则说明元素在切片序列中。
完整的实现代码如下
func SortInIntSlice(haystack []int, needle int) bool {sort.Ints(haystack)index : sort.SearchInts(haystack, needle)return index len(haystack) haystack[index] needle
}但这还有个问题对于无序的场景如果每次查询都要经过一次排序并不划算。最好能实现一次排序稍微修改下代码。
func InIntSliceSortedFunc(haystack []int) func(int) bool {sort.Ints(haystack)return func(needle int) bool {index : sort.SearchInts(haystack, needle)return index len(haystack) haystack[index] needle}
}上面的实现我们通过调用 InIntSliceSortedFunc 对 haystack 切片排序并返回一个可多次使用的函数。
使用案例如下
in : gotin.InIntSliceSortedFunc(haystack)for i : 0; imaxNeedle; i {if in(i) {fmt.Printf(%d is in %v, i, haystack)}
}二分查找的方式有什么不足呢
我想到的重要一点要实现二分查找元素必须是可排序的如 intstringfloat 类型。而对于结构体、切片、数组、映射等类型使用起来就不是那么方便当然如果要用也是可以的不过需要我们进行一些适当扩展按指定标准排序比如结构的某个成员。
到此二分查找的 in 实现就介绍完毕了。
map key
本节介绍 map key 方式。它的算法复杂度是 O1无论数据量多大查询性能始终不变。它主要依赖的是 Go 中的 map 数据类型通过 hash map 直接检查 key 是否存在算法大家应该都比较熟悉通过 key 可直接映射到索引位置。
我们常会用到这个方法。
_, ok : m[k]
if ok {fmt.Println(Found)
}那么它和 in 如何结合呢一个案例就说明白了这个问题。
假设我们有一个 []int 类型变量如下
s : []int{1, 2, 3}为了使用 map 的能力检查某个元素是否存在可以将 s 转化 map[int]struct{}。
m : map[interface{}]struct{}{1: struct{}{},2: struct{}{},3: struct{}{},4: struct{}{},
}如果检查某个元素是否存在只需要通过如下写法即可确定
k : 4
if _, ok : m[k]; ok {fmt.Printf(%d is found\n, k)
}是不是非常简单
补充一点关于这里为什么使用 struct{}可以阅读我之前写的一篇关于 Go 中如何使用 set 的文章。
按照这个思路实现函数如下
func MapKeyInIntSlice(haystack []int, needle int) bool {set : make(map[int]struct{})for _ , e : range haystack {set[e] struct{}{}}_, ok : set[needle]return ok
}实现起来不难但和二分查找有着同样的问题开始要做数据处理将 slice 转化为 map。如果是每次数据相同稍微修改下它的实现。
func InIntSliceMapKeyFunc(haystack []int) func(int) bool {set : make(map[int]struct{})for _ , e : range haystack {set[e] struct{}{}}return func(needle int) bool {_, ok : set[needle]return ok}
}对于相同的数据它会返回一个可多次使用的 in 函数一个使用案例如下
in : gotin.InIntSliceMapKeyFunc(haystack)for i : 0; imaxNeedle; i {if in(i) {fmt.Printf(%d is in %v, i, haystack)}
}对比前两种算法这种方式的处理效率最高非常适合于大数据的处理。接下来的性能测试我们将会看到效果。
性能
介绍完所有方式我们来实际对比下每种算法的性能。测试源码位于 gotin_test.go 文件中。
基准测试主要是从数据量大小考察不同算法的性能本文中选择了三个量级的测试样本数据分别是 10、1000、1000000。
为便于测试首先定义了一个用于生成 haystack 和 needle 样本数据的函数。
代码如下
func randomHaystackAndNeedle(size int) ([]int, int){haystack : make([]int, size)for i : 0; isize ; i{haystack[i] rand.Int()}return haystack, rand.Int()
}输入参数是 size通过 rand.Int() 随机生成切片大小为 size 的 haystack 和 1 个 needle。在基准测试用例中引入这个随机函数生成数据即可。
举个例子如下
func BenchmarkIn_10(b *testing.B) {haystack, needle : randomHaystackAndNeedle(10)b.ResetTimer()for i : 0; i b.N; i {_, _ gotin.In(haystack, needle)}
}首先通过 randomHaystackAndNeedle 随机生成了一个含有 10 个元素的切片。因为生成样本数据的时间不应该计入到基准测试中我们使用 b.ResetTimer() 重置了时间。
其次压测函数是按照 Test函数名样本数据量 规则编写如案例中 BenchmarkIn_10表示测试 In 函数样本数据量为 10。如果我们要用 1000 数据量测试 InIntSlice压测函数名为 BenchmarkInIntSlice_1000。
测试开始吧简单说下我的笔记本配置Mac Pro 15 版16G 内存512 SSD4 核 8 线程的 CPU。
测试所有函数在数据量在 10 的情况下的表现。
$ go test -runnone -bench10$ -benchmem匹配所有以 10 结尾的压测函数。
测试结果
goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_10-8 3000000 501 ns/op 112 B/op 11 allocs/op
BenchmarkInIntSlice_10-8 200000000 7.47 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_10-8 100000000 22.3 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_10-8 10000000 162 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_10-8 100000000 17.7 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_10-8 3000000 513 ns/op 163 B/op 1 allocs/op
PASS
ok github.com/poloxue/gotin 13.162s表现最好的并非 SortedFunc 和 MapKeyFunc而是最简单的针对单类型的遍历查询平均耗时 7.47ns/op当然另外两种方式表现也不错分别是 22.3ns/op 和 17.7ns/op。
表现最差的是 In、SortIn每次重复排序 和 MapKeyIn每次重复创建 map两种方式平均耗时分别为 501ns/op 和 513ns/op。
测试所有函数在数据量在 1000 的情况下的表现。
$ go test -runnone -bench1000$ -benchmem测试结果
goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_1000-8 30000 45074 ns/op 8032 B/op 1001 allocs/op
BenchmarkInIntSlice_1000-8 5000000 313 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_1000-8 30000000 44.0 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_1000-8 20000 65401 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_1000-8 100000000 17.6 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_1000-8 20000 82761 ns/op 47798 B/op 65 allocs/op
PASS
ok github.com/poloxue/gotin 11.312s表现前三依然是 InIntSlice、InIntSliceSortedFunc 和 InIntSliceMapKeyFunc但这次顺序发生了变化MapKeyFunc 表现最好17.6 ns/op与数据量 10 的时候相比基本无变化。再次验证了前文的说法。
同样的数据量 1000000 的时候。
$ go test -runnone -bench1000000$ -benchmem测试结果如下
goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_1000000-8 30 46099678 ns/op 8000098 B/op 1000001 allocs/op
BenchmarkInIntSlice_1000000-8 3000 424623 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_1000000-8 20000000 72.8 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_1000000-8 10 138873420 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_1000000-8 100000000 16.5 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_1000000-8 10 156215889 ns/op 49824225 B/op 38313 allocs/op
PASS
ok github.com/poloxue/gotin 15.178sMapKeyFunc 依然表现最好每次操作用时 17.2 nsSort 次之而 InIntSlice 呈现线性增加的趋势。一般情况下如果不是对性能要特殊要求数据量特别大的场景针对单类型的遍历已经有非常好的性能了。
从测试结果可以看出反射实现的通用 In 函数每次执行需要进行大量的内存分配方便的同时也是以牺牲性能为代价的。
总结
本文通过一个问题引出主题为什么 Go 中没有类似 Python 的 In 方法。我认为一方面是实现非常简单没有必要。除此以外另一方面在不同场景下我们还需要根据实际情况分析用哪种方式实现而不是一种固定的方式。
接着我们介绍了 In 实现的三种方式并分析了各自的优劣。通过性能分析测试我们能得出大致的结论什么方式适合什么场景但总体还是不能说足够细致有兴趣的朋友可以继续研究下。
