Golang 中如何实现 Set
在Go编程中,数据结构的选择对解决问题至关重要。本文将探讨如何在 GO 中实现 set 和 bitset 两种数据结构,以及它们在Go中的应用场景。
Go 的数据结构
Go 内置的数据结构并不多。工作中,我们最常用的两种数据结构分别是 slice 和 map,即切片和映射。 其实,Go 中也有数组,切片的底层就是数组,只不过因为切片的存在,我们平时很少使用它。
除了 Go 内置的数据结构,还有一些数据结构是由 Go 的官方 container 包提供,如 heap 堆、list 双向链表和ring 回环链表。但今天我们不讲它们,这些数据结构,对于熟手来说,看看文档就会使用了。
我们今天将来聊的是 set 和 bitset。据我所知,其他一些语言,比如 Java,是有这两种数据结构。但 Go 当前还没有以任何形式提供。
实现思路
先来看一篇文章,访问地址 2 basic set implementations 阅读。文中介绍了两种 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 { // Loopfmt.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 voidset := make(map[string]void) // New empty set
set["Foo"] = member // Add
for k := range set { // Loopfmt.Println(k)
}
delete(set, "Foo") // Delete
size := len(set) // Size
_, exists := set["Foo"] // Membership
之前在网上看到有人按这个思路做了封装,还写了一篇文章,可以去读一下。
其实,github 上已经有个成熟的包,名为 golang-set,它也是采用这个思路实现的。访问地址 golang-set,描述中说 Docker 用的也是它。包中提供了两种 set 实现,线程安全的 set 和非线程安全的 set。
演示一个简单的案例。
package mainimport ("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):
type Bits uint8const (F0 Bits = 1 << iotaF1F2
)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 Bitsb = 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 mainimport ("fmt"
)const (shift = 6mask = 0x3f // 即0b00111111
)type Bitset struct {data []int64
}func NewBitSet(n int) *Bitset {// 获取位置信息index := n >> shiftset := &Bitset{data: make([]int64, index+1),}// 根据 n 设置 bitsetset.data[index] |= 1 << uint(n&mask)return set
}func (set *Bitset) Contains(n int) bool {// 获取位置信息index := n >> shiftreturn 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。可以读读它的源码,实现思路和上面介绍差不多。
下面是一个使用案例。
package mainimport ("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 和 github.com/willf/bitset。
博文地址:Golang 中如何实现 Set
相关文章:

Golang 中如何实现 Set
在Go编程中,数据结构的选择对解决问题至关重要。本文将探讨如何在 GO 中实现 set 和 bitset 两种数据结构,以及它们在Go中的应用场景。 Go 的数据结构 Go 内置的数据结构并不多。工作中,我们最常用的两种数据结构分别是 slice 和 map&#…...

记录一下uniapp 集成腾讯im特别卡(已解决)
uniapp的项目运行在微信小程序 , 安卓 , ios手机三端 , 之前这个项目集成过im,不过版本太老了,0.x的版本, 现在需要添加客服功能,所以就升级了 由于是二开 , 也为了方便 , 沿用之前的webview嵌套腾讯IM的方案 , 选用uniapp集成ui ,升级之后所有安卓用户反馈点击进去特别卡,几…...
React16源码: React中的updateHostRoot的源码实现
HostRoot 的更新 1 )概述 HostRoot 是一个比较特殊的节点, 因为在一个react应用当中它只会有一个 HostRoot, 它对应的 Fiber 对象是我们的 RootFiber 对象重点在于它的更新过程 2 )源码 定位到 packages/react-reconciler/src/ReactFiberBeginWork.js…...
Template -- React
React 版本 Node 21.6.0Npm 10.2.4 项目 创建 npm init vite 项目名称reactjsnpm inpm run dev 依赖 npm i axios # 网络 npm i antd --save # UI npm i ant-design/icons npm i react-router-dom # 路由npm i sass -D # …...

HTML 入门手册(一)
目录 HTML 1-基础语法 单标签 双标签 整体结构 2-标题和水平线 标题 水平线 3-段落和换行 段落 换行 4-列表 无序列表 有序列表 嵌套列表 5-div和span div span 6-格式化标签 粗体 斜体 下划线中划线 上标和下标 7-超链接(a标签) 链接到URL 链接到本…...
GPT帮我快速解决工作上的问题案例
Python入门容易,但精通不易。自从跟着郭老师学Python后,工作中也想偷点懒,之前排班表的问题一直困扰着我,福音来了,现在随着郭老师的小蜜蜂AI出来,说干就干。马上来到郭老师为我们提供的AI网站:…...
Day32- 贪心算法part06
一、单调递增的数字 题目一:738. 单调递增的数字 738. 单调递增的数字 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时,我们称这个整数是单调递增的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递…...

.NetCore Flurl.Http 升级到4.0后 https 无法建立SSL连接
Flurl.Http-3.2.4 升级到 4.0.0 版本后,https请求异常:Call failed. The SSL connection could not be established. 如下图: Flurl.Http-3.2.4版本绕过https的代码,对于 Flurl.Http-4.0.0 版本来说方法不再适用,3.2.…...

【每周AI简讯】GPT-5将有指数级提升,GPT Store正式上线
AI7 - Chat中文版最强人工智能 OpenAI的CEO奥特曼表示GPT-5将有指数级提升 GPT奥特曼参加Y-Combinator W24启动会上表示,我们已经非常接近AGI。GPT-5将具有更好的推理能力、更高的准确性和视频支持。 GPT Store正式上线 OpenAI正式推出GPT store,目前…...

QT上位机开发(MFC vs QT)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 在qt之前,上位机开发的主要方法就是mfc。后来出现了c#语言之后,上位机的开发就有一部分人转成了c#。这些开发都是在windows平台完成的,而linux上面的界面,则都是通过各种小众库…...

线性代数:矩阵的定义
目录 一、定义 二、方阵 三、对角阵 四、单位阵 五、数量阵 六、行(列)矩阵 七、同型矩阵 八、矩阵相等 九、零矩阵 十、方阵的行列式 一、定义 二、方阵 三、对角阵 四、单位阵 五、数量阵 六、行(列)矩阵 七、同型矩…...

k8s 使用cert-manager证书管理自签
个人建议使用安装更快,比helm快,还要等待安装crd kubectl apply -f https://github.com/cert-manager/cert-manager/releases/download/v1.13.3/cert-manager.yaml#官网 https://cert-manager.io/docs/installation/kubectl/#创建自签的ClusterIssuer c…...

SpringSecurity+JWT前后端分离架构登录认证
目录 1. 数据库设计 2. 代码设计 登录认证过滤器 认证成功处理器AuthenticationSuccessHandler 认证失败处理器AuthenticationFailureHandler AuthenticationEntryPoint配置 AccessDeniedHandler配置 UserDetailsService配置 Token校验过滤器 登录认证过滤器接口配置…...

笔试面试题——二叉树进阶(一)
📘北尘_:个人主页 🌎个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上,不忘来时的初心 文章目录 一、根据二叉树创建字符串1、题目讲解2、思路讲解3、代码实现 二、二叉树的分层遍历1、题目讲…...
Java反射示例
Java反射示例 创建数据类型ReflectPoint.java package com.reflection;import java.util.Date;public class ReflectPoint {private Date birthday new Date();private int x;public int y;public String str1 "ball";public String str2 "basketball"…...
【WinForm.NET开发】实现使用后台操作的窗体
本文内容 创建使用后台操作的窗体使用设计器创建 BackgroundWorker添加异步事件处理程序添加进度报告和取消支持Checkpoint 如果某项操作需要很长的时间才能完成,并且不希望用户界面 (UI) 停止响应或阻塞,则可以使用 BackgroundWorker 类在另一个线程上…...

【操作系统和计网从入门到深入】(四)基础IO和文件系统
前言 这个专栏其实是博主在复习操作系统和计算机网络时候的笔记,所以如果是博主比较熟悉的知识点,博主可能就直接跳过了,但是所有重要的知识点,在这个专栏里面都会提到!而且我也一定会保证这个专栏知识点的完整性&…...

四.Winform使用Webview2加载本地HTML页面并互相通信
Winform使用Webview2加载本地HTML页面并互相通信 往期目录本节目标核心代码实现HTML代码实现的窗体Demo2代码效果图 往期目录 往期相关文章目录 专栏目录 本节目标 实现刷新按钮点击 C# winform按钮可以调用C# winform代码显示到html上点击HTML按钮可以调用C# winform代码更…...
如何有效清理您的Python环境:清除Pip缓存
Python是一个广泛使用的高级编程语言,以其强大的库和框架而闻名。然而,随着时间的推移和不断安装新的包,Python环境可能会变得混乱不堪,尤其是pip缓存可能占用大量的磁盘空间。本文将向您展示如何有效地清理pip缓存,保…...

Jira 母公司全面停服 Server 产品,用户如何迁移至极狐GitLab
Jira 母公司即将全面停服旗下部分 Server 端产品的销售和服务支持! Jira 母公司 Atlassian 在几年前确定了公司的战略为“全面上云”,为此做出了停止 Server 产品的销售和支持。整个时间线从 2021 年 2 月 2 日开始,直到今年 2 月 15 日&…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...