Go中如何使用set的方法示例

今天来聊一下 Go 如何使用 set,本文将会涉及 set 和 bitset 两种数据结构。

Go 的数据结构

Go 内置的数据结构并不多。工作中,我们最常用的两种数据结构分别是 slice 和 map,即切片和映射。其实,Go 中也有数组,切片的底层就是数组,只不过因为切片的存在,我们平时很少使用它。

除了 Go 内置的数据结构,还有一些数据结构是由 Go 的官方 container 包提供,如 heap 堆、list 双向链表和ring 回环链表。但今天我们不讲它们,这些数据结构,对于熟手来说,看看文档就会使用了。

我们今天将来聊的是 set 和 bitset。据我所知,其他一些语言,比如 Java,是有这两种数据结构。但 Go 当前还没有以任何形式提供。

实现思路

先来看一篇文章,访问地址 2 basic set implementations[1] 阅读。文中介绍了两种 go 实现 set 的思路, 分别是 map 和 bitset。

有兴趣可以读读这篇文章,我们接下来具体介绍下。

map

我们知道,map 的 key 肯定是唯一的,而这恰好与 set 的特性一致,天然保证 set 中成员的唯一性。而且通过 map 实现 set,在检查是否存在某个元素时可直接使用 _, ok := m[key] 的语法,效率高。

先来看一个简单的实现,如下:

set := make(map[string]bool) // New empty set
set["Foo"] = true   // Add
for k := range set {   // Loop
 fmt.Println(k)
}
delete(set, "Foo") // Delete
size := len(set)  // Size
exists := set["Foo"] // Membership

通过创建 map[string]bool 来存储 string 的集合,比较容易理解。但这里还有个问题,map 的 value 是布尔类型,这会导致 set 多占一定内存空间,而 set 不该有这个问题。

怎么解决这个问题?

设置 value 为空结构体,在 Go 中,空结构体不占任何内存。当然,如果不确定,也可以来证明下这个结论。

unsafe.Sizeof(struct{}{}) // 结果为 0

优化后的代码,如下:

type void struct{}
var member void

set := make(map[string]void) // New empty set
set["Foo"] = member   // Add
for k := range set {   // Loop
 fmt.Println(k)
}
delete(set, "Foo")  // Delete
size := len(set)  // Size
_, exists := set["Foo"] // Membership

之前在网上看到有人按这个思路做了封装,还写了一篇文章[2],可以去读一下。

其实,github 上已经有个成熟的包,名为 golang-set,它也是采用这个思路实现的。访问地址 golang-set[3],描述中说 Docker 用的也是它。包中提供了两种 set 实现,线程安全的 set 和非线程安全的 set。

演示一个简单的案例。

package main

import (
 "fmt"

 mapset "github.com/deckarep/golang-set"
)

func main() {
 // 默认创建的线程安全的,如果无需线程安全
 // 可以使用 NewThreadUnsafeSet 创建,使用方法都是一样的。
 s1 := mapset.NewSet(1, 2, 3, 4)
 fmt.Println("s1 contains 3: ", s1.Contains(3))
 fmt.Println("s1 contains 5: ", s1.Contains(5))

 // interface 参数,可以传递任意类型
 s1.Add("poloxue")
 fmt.Println("s1 contains poloxue: ", s1.Contains("poloxue"))
 s1.Remove(3)
 fmt.Println("s1 contains 3: ", s1.Contains(3))

 s2 := mapset.NewSet(1, 3, 4, 5)

 // 并集
 fmt.Println(s1.Union(s2))
}

输出如下:

s1 contains 3:  true
s1 contains 5:  false
s1 contains poloxue:  true
s1 contains 3:  false
Set{4, polxue, 1, 2, 3, 5}

例子中演示了简单的使用方式,如果有不明白的,看下源码,这些数据结构的操作方法名都是很常见的,比如交集 Intersect、差集 Difference 等,一看就懂。

bitset

继续聊聊 bitset,bitset 中每个数子用一个 bit 即能表示,对于一个 int8 的数字,我们可以用它表示 8 个数字,能帮助我们大大节省数据的存储空间。

bitset 最常见的应用有 bitmap 和 flag,即位图和标志位。这里,我们先尝试用它表示一些操作的标志位。比如某个场景,我们需要三个 flag 分别表示权限1、权限2和权限3,而且几个权限可以共存。我们可以分别用三个常量 F1、F2、F3 表示位 Mask。

示例代码如下(引用自文章 Bitmasks, bitsets and flags[4]):

type Bits uint8

const (
 F0 Bits = 1 << iota
 F1
 F2
)

func Set(b, flag Bits) Bits { return b | flag }
func Clear(b, flag Bits) Bits { return b &^ flag }
func Toggle(b, flag Bits) Bits { return b ^ flag }
func Has(b, flag Bits) bool { return b&flag != 0 }

func main() {
 var b Bits
 b = Set(b, F0)
 b = Toggle(b, F2)
 for i, flag := range []Bits{F0, F1, F2} {
  fmt.Println(i, Has(b, flag))
 }
}

例子中,我们本来需要三个数才能表示这三个标志,但现在通过一个 uint8 就可以。bitset 的一些操作,如设置 Set、清除 Clear、切换 Toggle、检查 Has 通过位运算就可以实现,而且非常高效。

bitset 对集合操作有着天然的优势,直接通过位运算符便可实现。比如交集、并集、和差集,示例如下:

  • 交集:a & b
  • 并集:a | b
  • 差集:a & (~b)

底层的语言、库、框架常会使用这种方式设置标志位。

以上的例子中只展示了少量数据的处理方式,uint8 占 8 bit 空间,只能表示 8 个数字。那大数据场景能否可以使用这套思路呢?

我们可以把 bitset 和 Go 中的切片结合起来,重新定义 Bits 类型,如下:

type Bitset struct {
 data []int64
}

但如此也会产生一些问题,设置 bit,我们怎么知道它在哪里呢?仔细想想,这个位置信息包含两部分,即保存该 bit 的数在切片索引位置和该 bit 在数字中的哪位,分别将它们命名为 index 和 position。那怎么获取?

index 可以通过整除获取,比如我们想知道表示 65 的 bit 在切片的哪个 index,通过 65 / 64 即可获得,如果为了高效,也可以用位运算实现,即用移位替换除法,比如 65 >> 6,6 表示移位偏移,即 2^n = 64 的 n。

postion 是除法的余数,我们可以通过模运算获得,比如 65 % 64 = 1,同样为了效率,也有相应的位运算实现,比如 65 & 0b00111111,即 65 & 63。

一个简单例子,如下:

package main

import (
 "fmt"
)

const (
 shift = 6
 mask = 0x3f // 即0b00111111
)

type Bitset struct {
 data []int64
}

func NewBitSet(n int) *Bitset {
 // 获取位置信息
 index := n >> shift

 set := &Bitset{
 data: make([]int64, index+1),
 }

 // 根据 n 设置 bitset
 set.data[index] |= 1 << uint(n&mask)

 return set
}

func (set *Bitset) Contains(n int) bool {
 // 获取位置信息
 index := n >> shift
 return set.data[index]&(1<<uint(n&mask)) != 0
}

func main() {
 set := NewBitSet(65)
 fmt.Println("set contains 65", set.Contains(65))
 fmt.Println("set contains 64", set.Contains(64))
}

输出结果

set contains 65 true
set contains 64 false

以上的例子功能很简单,只是为了演示,只有创建 bitset 和 contains 两个功能,其他诸如添加、删除、不同 bitset 间的交、并、差还没有实现。有兴趣的朋友可以继续尝试。

其实,bitset 包也有人实现了,github地址 bit[5]。可以读读它的源码,实现思路和上面介绍差不多。

下面是一个使用案例。

package main

import (
 "fmt"

 "github.com/yourbasic/bit"
)

func main() {
 s := bit.New(2, 3, 4, 65, 128)
 fmt.Println("s contains 65", s.Contains(65))
 fmt.Println("s contains 15", s.Contains(15))

 s.Add(15)
 fmt.Println("s contains 15", s.Contains(15))

 fmt.Println("next 20 is ", s.Next(20))
 fmt.Println("prev 20 is ", s.Prev(20))

 s2 := bit.New(10, 22, 30)

 s3 := s.Or(s2)
 fmt.Println("next 20 is ", s3.Next(20))

 s3.Visit(func(n int) bool {
 fmt.Println(n)
 return false // 返回 true 表示终止遍历
 })
}

执行结果:

s contains 65 true
s contains 15 false
s contains 15 true
next 20 is 65
prev 20 is 15
next 20 is 22
2
3
4
10
15
22
30
65
128

代码的意思很好理解,就是一些增删改查和集合的操作。要注意的是,bitset 和前面的 set 的区别,bitset 的成员只能是 int 整型,没有 set 灵活。平时的使用场景也比较少,主要用在对效率和存储空间要求较高的场景。

总结

本文介绍了Go 中两种 set 的实现原理,并在此基础介绍了对应于它们的两个包简单使用。我觉得,通过这篇文章,Go 中 set 的使用,基本都可以搞定了。

除这两个包,再补充两个,zoumo/goset[6] 和 github.com/willf/bitset[7]。

参考资料

[1]2 basic set implementations: https://yourbasic.org/golang/implement-set/

[2]一篇文章: https://www.jb51.net/article/170043.htm

[3]golang-set: https://github.com/deckarep/golang-set

[4]Bitmasks, bitsets and flags: https://yourbasic.org/golang/bitmask-flag-set-clear/

[5]bit: https://github.com/yourbasic/bit

[6]zoumo/goset: https://github.com/zoumo/goset

[7]github.com/willf/bitset: https://github.com/willf/bitset

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Go语言中的Array、Slice、Map和Set使用详解

    Array(数组) 内部机制 在 Go 语言中数组是固定长度的数据类型,它包含相同类型的连续的元素,这些元素可以是内建类型,像数字和字符串,也可以是结构类型,元素可以通过唯一的索引值访问,从 0 开始. 数组是很有价值的数据结构,因为它的内存分配是连续的,内存连续意味着可是让它在 CPU 缓存中待更久,所以迭代数组和移动元素都会非常迅速. 数组声明和初始化 通过指定数据类型和元素个数(数组长度)来声明数组. 复制代码 代码如下: // 声明一个长度为5的整数数组 var array [5]int

  • 详解Go中Set的实现方式

    本篇主要讲述如何利用Go语言的语法特性实现Set类型的数据结构. 需求 对于Set类型的数据结构,其实本质上跟List没什么多大的区别.无非是Set不能含有重复的Item的特性,Set有初始化.Add.Clear.Remove.Contains等操作.接下来看具体的实现方式分析吧. 实现 仍然按照已有的编程经验来联想如何实现基本Set功能,在Java中很容易知道HashSet的底层实现是HashMap,核心的就是用一个常量来填充Map键值对中的Value选项.除此之外,重点关注Go中Map的数据

  • Go语言之自定义集合Set

    一.Go语言实战--自定义集合Set 在Go语言中有作为Hash Table实现的字典(Map)类型,但标准数据类型中并没有集合(Set)这种数据类型.比较 Set 和 Map 的主要特性,有类似特性如下: 它们中的元素都是不可重复的. 它们都只能用迭代的方式取出其中的所有元素. 对它们中的元素进行迭代的顺序都是与元素插入顺序无关的,同时也不保证任何有序性. 但是,它们之间也有一些区别,如下: Set 的元素是一个单一的值,而 Map 的元素则是一个键值对. Set 的元素不可重复指的是不能存在

  • oracle中decode函数的使用方法示例

    decode的几种用法 1:使用decode判断字符串是否一样 DECODE(value,if1,then1,if2,then2,if3,then3,...,else) 含义为 IF 条件=值1 THEN RETURN(value 1) ELSIF 条件=值2 THEN RETURN(value 2) ...... ELSIF 条件=值n THEN RETURN(value 3) ELSE RETURN(default) END IF sql测试 select empno,decode(empn

  • Java中生成唯一ID的方法示例

    有时我们不依赖于数据库中自动递增的字段产生唯一ID,比如多表同一字段需要统一一个唯一ID,这时就需要用程序来生成一个唯一的全局ID. UUID 从Java 5开始, UUID 类提供了一种生成唯一ID的简单方法.UUID是通用唯一识别码 (Universally Unique Identifier)的缩写,UUID来源于OSF(Open Software Foundation,开源软件基金会)的DCE(Distributed Computing Environment,分布式计算环境)规范.UU

  • C语言中可变参数的使用方法示例

    前言 在C语言程序编写中我们使用最多的函数一定包括printf以及很多类似的变形体.这个函数包含在C库函数中,定义为 int printf( const char* format, ...); 除了一个格式化字符串之外还可以输入多个可变参量,如: printf("%d",i); printf("%s",s); printf("the number is %d ,string is:%s", i, s); 格式化字符串的判断本章暂且不论,下面分析一

  • 在SpringBoot项目中的使用Swagger的方法示例

    一. 首先Swagger是什么? Swagger 是一个规范和完整的框架,用于生成.描述.调用和可视化 RESTful 风格的 Web 服务.总体目标是使客户端和文件系统作为服务器以同样的速度来更新.文件的方法,参数和模型紧密集成到服务器端的代码,允许API来始终保持同步.Swagger官方API文档:https://swagger.io/ 作用:   1. 接口的文档在线自动生成.   2. 功能测试. Swagger的主见介绍:    Swagger Codegen: 通过Codegen 可

  • MyBatis-Plus中如何使用ResultMap的方法示例

    目录 问题说明 解决方法 自定义@AutoResultMap注解 MyBatis-Plus (简称MP)是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,为简化开发.提高效率而生. MyBatis-Plus对MyBatis基本零侵入,完全可以与MyBatis混合使用,这点很赞. 在涉及到关系型数据库增删查改的业务时,我比较喜欢用MyBatis-Plus,开发效率极高.具体的使用可以参考官网,或者自己上手摸索感受一下. 下面简单总结一下在MyBatis-Plus中如何使用R

  • java中的4种循环方法示例详情

    目录 java循环结构 1.while循环 2.do-while循环 3.for循环 4.java 增强for循环 java循环结构 顺序结构的程序语句只能 被执行一次.如果你要同样的操作执行多次,就需要使用循环结构. java中有三种主要的循环结构: while 循环 do...while 循环 for 循环 在java5中引入一种主要用于数组的增强型for循环. 1.while循环 while是最基本的循环,它的结构为: package com.example.lesson1; //whil

  • vue中的使用token的方法示例

    初始于登录页面 Home.vue <template> <div class="home"> </div> </template> <script> // @ is an alias to /src import HelloWorld from '@/components/HelloWorld.vue' import axios from 'axios'; export default { name: 'home', comp

  • Linux中gpio接口的使用方法示例

    前言 Linux内核中gpio是最简单,最常用的资源(和 interrupt ,dma,timer一样)驱动程序,应用程序都能够通过相应的接口使用gpio,gpio使用0-MAX_INT之间的整数标识,不能使用负数,gpio与硬件体系密切相关的,不过linux有一个框架处理gpio,能够使用统一的接口来操作gpio.在讲gpio核心(gpiolib.c)之前先来看看gpio是怎么使用的 使用gpio 使用gpio接口需要包含#include <linux/gpio.h> ,在驱动中使用延时函数

  • ASP.NET MVC4中使用Html.DropDownListFor的方法示例

    本文实例讲述了ASP.NET MVC4中使用Html.DropDownListFor的方法.分享给大家供大家参考,具体如下: 一.控制器部分: public ActionResult PageDetail() { var thisList = _sysDepartmentBll.GetAllDepartmentList();//数据源 //添加一条默认数据 var resultList = new List<SelectListItem> { new SelectListItem {Text

  • Python中shape计算矩阵的方法示例

    本文实例讲述了Python中shape计算矩阵的方法.分享给大家供大家参考,具体如下: 看到机器学习算法时,注意到了shape计算矩阵的方法接下来就讲讲我的理解吧 >>> from numpy import * >>> import operator >>> a =mat([[1,2,3],[5,6,9]]) >>> a matrix([[1, 2, 3], [5, 6, 9]]) >>> shape(a) (2,

随机推荐