脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Golang - Go 中 Set 的实现方案,你会吗?

Go 中 Set 的实现方案,你会吗?

2021-09-14 01:51Golang技术分享机器铃砍菜刀 Golang

Go 的设计是一种简单哲学,它摒弃了其他语言一些臃肿的功能和模块,以降低程序员的学习门槛,减少使用中的心智负担。

Go 的设计是一种简单哲学,Go 中 Set 的实现方案,你会吗?

它摒弃了其他语言一些臃肿的功能和模块,以降低程序员的学习门槛,减少使用中的心智负担。

本文,我们来探讨 Go 中缺失的数据结构:Set,以及它的最佳实现方案。

Set 语义与实现方案

Set 集合是其他语言中常见的数据结构。特性:集合中的对象不按特定的方式排序,并且没有重复对象。

Go 中 Set 的实现方案,你会吗?

学习 Go ,要记住:Go 没有包含的东西,不代表 Go 真的没有。根据 Set 特性,我们可以很轻松地想到使用 map 的实现方案(因为 map 的 key 是不重复的):把对象当做 key 存入 map。

使用 map 来实现 Set,意味着我们只关心 key 的存在,其 value 值并不重要。有其他语言编程经验的人也许会选择 bool 来作为 value,因为它是其它语言中内存消耗最少的类型(1个字节)。但是在 Go 中,还有另一种选择:struct{}。

  1. fmt.Println(unsafe.Sizeof(struct {}{})) // output: 0 

压测对比

为了探究哪种数据结构是作为 value 的最佳选择。我们选择了以下常用的类型作为 value 进行测试:bool、int、interface{}、struct{}。

  1. package main 
  2.  
  3. import ( 
  4.  "testing" 
  5.  
  6. const num = int(1 << 24) 
  7.  
  8. // 测试 bool 类型 
  9. func Benchmark_SetWithBoolValueWrite(b *testing.B) { 
  10.  set := make(map[int]bool) 
  11.  for i := 0; i < num; i++ { 
  12.   set[i] = true 
  13.  } 
  14.  
  15. // 测试 interface{} 类型 
  16. func Benchmark_SetWithInterfaceValueWrite(b *testing.B) { 
  17.  set := make(map[int]interface{}) 
  18.  for i := 0; i < num; i++ { 
  19.   set[i] = struct{}{} 
  20.  } 
  21.  
  22. // 测试 int 类型 
  23. func Benchmark_SetWithIntValueWrite(b *testing.B) { 
  24.  set := make(map[int]int
  25.  for i := 0; i < num; i++ { 
  26.   set[i] = 0 
  27.  } 
  28.  
  29. // 测试 struct{} 类型 
  30. func Benchmark_SetWithStructValueWrite(b *testing.B) { 
  31.  set := make(map[int]struct{}) 
  32.  for i := 0; i < num; i++ { 
  33.   set[i] = struct{}{} 
  34.  } 

我们运行以下命令,进行测试

  1. $ go test -v -bench=. -count=3 -benchmem | tee result.txt 
  2. goos: darwin 
  3. goarch: amd64 
  4. pkg: workspace/example/demoForSet 
  5. cpu: Intel(R) Core(TM) i5-8279U CPU @ 2.40GHz 
  6. Benchmark_SetWithBoolValueWrite 
  7. Benchmark_SetWithBoolValueWrite-8                1 3549312568 ns/op 883610264 B/op   614311 allocs/op 
  8. Benchmark_SetWithBoolValueWrite-8                1 3288521519 ns/op 883599440 B/op   614206 allocs/op 
  9. Benchmark_SetWithBoolValueWrite-8                1 3264097496 ns/op 883578624 B/op   614003 allocs/op 
  10. Benchmark_SetWithInterfaceValueWrite 
  11. Benchmark_SetWithInterfaceValueWrite-8           1 4397757645 ns/op 1981619632 B/op   614062 allocs/op 
  12. Benchmark_SetWithInterfaceValueWrite-8           1 4088301215 ns/op 1981553392 B/op   613743 allocs/op 
  13. Benchmark_SetWithInterfaceValueWrite-8           1 3990698218 ns/op 1981560880 B/op   613773 allocs/op 
  14. Benchmark_SetWithIntValueWrite 
  15. Benchmark_SetWithIntValueWrite-8                 1 3472910194 ns/op 1412326480 B/op   615131 allocs/op 
  16. Benchmark_SetWithIntValueWrite-8                 1 3519755137 ns/op 1412187928 B/op   614294 allocs/op 
  17. Benchmark_SetWithIntValueWrite-8                 1 3459182691 ns/op 1412057672 B/op   613390 allocs/op 
  18. Benchmark_SetWithStructValueWrite 
  19. Benchmark_SetWithStructValueWrite-8              1 3126746088 ns/op 802452368 B/op   614127 allocs/op 
  20. Benchmark_SetWithStructValueWrite-8              1 3161650835 ns/op 802431240 B/op   613632 allocs/op 
  21. Benchmark_SetWithStructValueWrite-8              1 3160410871 ns/op 802440552 B/op   613748 allocs/op 
  22. PASS 
  23. ok   workspace/example/demoForSet 42.660s 

此时的结果看起来不太直观,这里推荐一个 benchmark 统计工具:Benchstat。通过以下命令进行安装

  1. $ go get -u golang.org/x/perf/cmd/benchstat 

使用 benchstat 分析刚才得到的 benchmark 结果文件

  1. $ benchstat result.txt 
  2. name                           time/op 
  3. _SetWithBoolValueWrite-8        3.37s ± 5% 
  4. _SetWithInterfaceValueWrite-8   4.16s ± 6% 
  5. _SetWithIntValueWrite-8         3.48s ± 1% 
  6. _SetWithStructValueWrite-8      3.15s ± 1% 
  7.  
  8. name                           alloc/op 
  9. _SetWithBoolValueWrite-8        884MB ± 0% 
  10. _SetWithInterfaceValueWrite-8  1.98GB ± 0% 
  11. _SetWithIntValueWrite-8        1.41GB ± 0% 
  12. _SetWithStructValueWrite-8      802MB ± 0% 
  13.  
  14. name                           allocs/op 
  15. _SetWithBoolValueWrite-8         614k ± 0% 
  16. _SetWithInterfaceValueWrite-8    614k ± 0% 
  17. _SetWithIntValueWrite-8          614k ± 0% 
  18. _SetWithStructValueWrite-8       614k ± 0% 

从内存开销而言,struct{} 是最小的,反映在执行时间上也是最少的。由于 bool 类型仅占一个字节,它相较于空结构而言,相差的并不多。但是,如果使用 interface{} 类型,那差距就很明显了。

所以,毫无疑问,在 Set 的实现中, map 值类型应该选 struct{}。

总结

本文虽然讨论的是 Set 的实现方案,但本质是涉及空结构体 struct{}{} 的 零内存特性。

空结构体除了是实现 Set 的 value 值最佳方案,它还可以应用于以下方面:

  • 通知信号的 channel:当 channel 只用于通知 goroutine 的执行事件,此时 channel 就不需要发送任何实质性的数据,选择使用 chan struct{} 。
  • 没有状态数据的结构体:当对象只拥有方法,而不包含任何的属性字段时,选择使用空结构体定义该对象。

原文链接:https://mp.weixin.qq.com/s/pcwCW7jtr2_CJ_k58He-6Q

延伸 · 阅读

精彩推荐
  • Golanggo语言制作端口扫描器

    go语言制作端口扫描器

    本文给大家分享的是使用go语言编写的TCP端口扫描器,可以选择IP范围,扫描的端口,以及多线程,有需要的小伙伴可以参考下。 ...

    脚本之家3642020-04-25
  • Golanggolang的httpserver优雅重启方法详解

    golang的httpserver优雅重启方法详解

    这篇文章主要给大家介绍了关于golang的httpserver优雅重启的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...

    helight2992020-05-14
  • Golanggolang如何使用struct的tag属性的详细介绍

    golang如何使用struct的tag属性的详细介绍

    这篇文章主要介绍了golang如何使用struct的tag属性的详细介绍,从例子说起,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看...

    Go语言中文网11352020-05-21
  • GolangGolang中Bit数组的实现方式

    Golang中Bit数组的实现方式

    这篇文章主要介绍了Golang中Bit数组的实现方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...

    天易独尊11682021-06-09
  • Golanggolang 通过ssh代理连接mysql的操作

    golang 通过ssh代理连接mysql的操作

    这篇文章主要介绍了golang 通过ssh代理连接mysql的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...

    a165861639710342021-03-08
  • Golanggo日志系统logrus显示文件和行号的操作

    go日志系统logrus显示文件和行号的操作

    这篇文章主要介绍了go日志系统logrus显示文件和行号的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...

    SmallQinYan12302021-02-02
  • Golanggolang json.Marshal 特殊html字符被转义的解决方法

    golang json.Marshal 特殊html字符被转义的解决方法

    今天小编就为大家分享一篇golang json.Marshal 特殊html字符被转义的解决方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 ...

    李浩的life12792020-05-27
  • GolangGolang通脉之数据类型详情

    Golang通脉之数据类型详情

    这篇文章主要介绍了Golang通脉之数据类型,在编程语言中标识符就是定义的具有某种意义的词,比如变量名、常量名、函数名等等,Go语言中标识符允许由...

    4272021-11-24