Go 判断元素是否在切片中
文章目录
1.问题
如何判断元素是否在切片中,Golang 并没有提供直接的库函数来判断,最容易想到的实现便是通过遍历来判断。
2.遍历查询
以字符串切片为例,判断字符串切片中是否包含某个字符串。
// ContainsInSlice 判断字符串是否在 slice 中
func ContainsInSlice(items []string, item string) bool {
for _, eachItem := range items {
if eachItem == item {
return true
}
}
return false
}
这种实现时间复杂度是 O(n),n 为切片元素个数。
如果切片长度比较短(10以内)或者不是频繁调用,该性能是可以接受的。但是如果切片长度较长且频繁调用,那么这种方法的性能将无法接受,我们可以借助 map 优化一波。
3.map 查询
具体实现是先将 slice 转为 map,通过查询 map 快速查看元素是否存在于 slice。
// ConvertStrSlice2Map 将字符串 slice 转为 map[string]struct{}
func ConvertStrSlice2Map(sl []string) map[string]struct{} {
set := make(map[string]struct{}, len(sl))
for _, v := range sl {
set[v] = struct{}{}
}
return set
}
// ContainsInMap 判断字符串是否在 map 中
func ContainsInMap(m map[string]struct{}, s string) bool {
_, ok := m[s]
return ok
}
注意:使用空结构体 struct{}
作为 value 的类型,因为 struct{}
不占用任何内存空间。
fmt.Println(unsafe.Sizeof(bool(false))) // 1
fmt.Println(unsafe.Sizeof(struct{}{})) // 0
虽然将 slice 转为 map 的时间复杂度为 O(n),但是只转换一次可以忽略。查询元素是否在 map 中的时间复杂度为 O(1)。
4.性能对比
我们可以看下在元素数量为 26 的情况下,取中位元素,做个基准测试(benchmark),对比下二者的查询性能。
func BenchmarkContainsInSlice(b *testing.B) {
for i := 0; i < b.N; i++ {
ContainsInSlice(sl, "m")
}
}
func BenchmarkContainsInMap(b *testing.B) {
m := ConvertStrSlice2Map(sl)
for i := 0; i < b.N; i++ {
ContainsInMap(m, "m")
}
}
执行测试命令输出:
D:codegotestcontain>go test -bench=.
goos: windows
goarch: amd64
pkg: main/contain
cpu: Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
BenchmarkContainsInSlice-8 30564058 38.35 ns/op
BenchmarkContainsInMap-8 134556465 8.846 ns/op
PASS
ok main/contain 3.479s
测试结果中,看到函数后面的 -8 个表示运行时对应的 GOMAXPROCS 的值。接着的一串很大的数字表示运行 for 循环的次数,也就是调用被测试代码的次数,最后的38.35 ns/op
表示每次需要花费 38.35 纳秒。
以上是测试时间默认是 1 秒,也就是1秒的时间,如果想让测试运行的时间更长,可以通过 -lunchtime 指定,比如 5 秒。
性能对比:
可以预料到的是随着切片长度增长,性能差距会越来越大。
5.转换通用化
我们可以借助空接口 interface{} 来实现任意类型的切片转换为 map,方便调用方使用。
// ToMapSetE converts a slice or array to map[interface{}]struct{} with error
func ToMapSetE(i interface{}) (map[interface{}]struct{}, error) {
// judge the validation of the input
if i == nil {
return nil, fmt.Errorf("unable to converts %#v of type %T to map[interface{}]struct{}", i, i)
}
kind := reflect.TypeOf(i).Kind()
if kind != reflect.Slice && kind != reflect.Array {
return nil, fmt.Errorf("the input %#v of type %T isn't a slice or array", i, i)
}
// execute the convert
v := reflect.ValueOf(i)
m := make(map[interface{}]struct{}, v.Len())
for j := 0; j < v.Len(); j++ {
m[v.Index(j).Interface()] = struct{}{}
}
return m, nil
}
func main() {
var sl = []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"}
m, _ := ToMapSetE(sl)
if _, ok := m["m"]; ok {
fmt.Println("in")
}
if _, ok := m["mm"]; !ok {
fmt.Println("not in")
}
}
运行输出:
in
not in
上面的转换函数ToMapSetE()
已经放到开源 Go 工具库go-huge-util,可直接通过 go mod 方式 import 使用。
import (
huge "github.com/dablelv/go-huge-util"
)
// 使用 go-huge-util
m, _ := huge.ToMapSetE(sl)
6.借助开源库 golang-set
上面其实是利用 map 实现了一个 set(元素不重复集合),然后再判断某个 set 中是否存在某个元素。Golang 标准库并没有 set,但是我们可以用 map 来间接实现,就像上面那样子。
如果想使用 set 的完整功能,如初始化、Add、Del、Clear、Contains等操作,推荐使用 github 上成熟的开源包 golang-set。描述中说 Docker 用的也是它。包中提供了两种 set 实现,线程安全的 set 和非线程安全的 set。
golang-set 提供了五个生成 set 的函数:
// NewSet creates and returns a reference to an empty set. Operations
// on the resulting set are thread-safe.
func NewSet(s ...interface{}) Set {}
// NewSetWith creates and returns a new set with the given elements.
// Operations on the resulting set are thread-safe.
func NewSetWith(elts ...interface{}) Set {}
// NewSetFromSlice creates and returns a reference to a set from an
// existing slice. Operations on the resulting set are thread-safe.
func NewSetFromSlice(s []interface{}) Set {}
// NewThreadUnsafeSet creates and returns a reference to an empty set.
// Operations on the resulting set are not thread-safe.
func NewThreadUnsafeSet() Set {}
// NewThreadUnsafeSetFromSlice creates and returns a reference to a
// set from an existing slice. Operations on the resulting set are
// not thread-safe.
func NewThreadUnsafeSetFromSlice(s []interface{}) Set {}
下面借助golang-set来判断切片中是否存在某个元素。
package main
import (
"fmt"
mapset "github.com/deckarep/golang-set"
)
func main() {
var sl = []interface{}{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
"s", "t",
"u", "v", "w", "x", "y", "z"}
s := mapset.NewSetFromSlice(sl)
fmt.Println(s.Contains("m")) // true
fmt.Println(s.Contains("mm")) // false
}
7.小结
本文从问题“判断元素是否在切片中”开始讨论,给出相关的实现方式。这个问题可以引申抽象为“如何将 slice 转为元素不重复的 set”,并给出自己的通用转换函数 go-huge-util ToMapSetE()。
当然,网上已经有很多成熟优秀的代码库直接使用,比如 golang-set,感兴趣的同学可以深入了解其用法和实现。
参考文献
相关文章
- 整个元素周期表通用,AI 即时预测材料结构与特性
- 一文盘点自动驾驶系统超全的系统时间同步方案设计
- AI短视频赛道:只需一个提示词,文本影像画外音一键搞定
- 禾多科技倪凯:自动驾驶不必纠结学苹果还是安卓,小步快跑最重要
- 当前prompt工程太像占卜了,与艺术AI交流就像文字游戏
- 预训练无需注意力,扩展到4096个token不成问题,与BERT相当
- 首个ChatGPT国产平替来了!ChatYuan发布测试版,无需注册,体验完全免费
- 2023 年你需要知道的七个重要科技词汇
- 一文聊聊自动驾驶汽车的安全技术特点
- 热点解读:大模型的突现能力和ChatGPT引爆的范式转变
- 将 Terraform 生态粘合到 Kubernetes 世界
- 写在Stack Overflow封禁ChatGPT之后,人工智能的危机时刻
- 对软件系统的一些理解
- 这种精度高,消耗资源少的大模型稀疏训练方法被找到了
- Linus Torvalds背后 :成功的五个残酷真相
- ChatGPT还在2G冲浪?新模型「youChat」:我已能够解说2022世界杯
- OpenAI CEO谈AI画图明星DALL·E 2:技术突破不多,地气接了不少
- ChatGPT怎么突然变得这么强?华人博士万字长文深度拆解GPT-3.5能力起源
- 大牛架构师珍藏的10条编程原则
- PS上的开源Stable Diffusion插件来了:一键AI脑补,即装即用