详细介绍 Go 中如何实现 bitset

最近测验在 B 站录些小视频。录视频当是为了彻底搞懂某个常识点的终究一步吧,一起也希望能习得一些额定的才能。在讲 Go 怎样完结 bitset 的时分,发现这块内容有点难讲。思考后,我决议经过文字辅以视频的办法阐明,于是就写了这篇文章。

相关代码现已放在了 github,地址如下: go-set-example

假如发现有什么不当的当地,欢迎大佬们纠正,感谢。

之前我现已写过一篇题为 Go 中怎样运用 Set 的文章,其间介绍了 bitset 一种最简略的运用场景,状况标志位,趁便还提了下 bitset 的完结思路。

状况标志和一般的调集有什么区别呢?

我的总结是首要一点,那便是状况标志中元素个数一般是固定的。而一般的调集中,元素个数一般是动态改变的。这会导致什么问题?

一般,咱们运用一个整数就足以标明状况标志中的悉数状况,最大的 int64 类型,足足有 64 个二进制位,最多能够包括 64 个元素,彻底满意运用。但假如是调集,元素数量和值一般都不固定。

比方一个 bitset 调集开端或许只包括 1、2、4 几个元素,只需一个 int64 就能标明。如下:

但假如再添加了一个元素,比方 64,这现已超出了一个 int64 能标明的规模。该怎样办?

一个 int64 无法标明,那就用多个呗。此刻的结构如下:

一个 int64 切片正好契合上面的结构。那咱们就能够界说一个新的类型 BitSet ,如下:

type BitSet struct {
 data []int64
 size int
}

data 成员用于寄存调集元素,切片的特色便是能动态扩容。

还有,由于 bitset 中元素个数无法经过 len 函数获取,而详细的办法相对杂乱一点,可添加一个 size 字段记载调集元素的个数。然后就能够添加一个 Size 办法。

func  Size int {
 return set.size
}

界说好了 BitSet 类型,又产生了一个新的问题,怎样定位寄存元素的方位?在标志位的场景下,元素的值便是方位,所以这个问题不必考虑。但通用的调集不是如此。

先看下 BitSet 的二进制位的散布状况。

相似队伍的作用,假定用 index 标明行, pos 标明列。切片索引从 0 到 n,n 与调集中的最大元素有关。

接下来确认 index 和 pos 的值。其实,之前的文章现已介绍过了。

index 可经过元素值整除字长,即 value / 64 ,转化为高效的位运算,即 value 6 。

pos 能够经过元素值取模字长,即 value % 64 ,转化为高效的位运算,即 value 0x3f ,获取对应方位,然后用 1 uint 即可将方位转化为值。

理论再多,都不如 show me your code 。开端编写代码吧!

先界说一些常量。

const 

便是前面说到的用于核算 index 和 pos 的两个常量。

供给两个函数,用于便利 index 和 pos 上对应值的核算,代码如下:

func index int {
 return n shift
// 相对于标志位运用场景中某个标志的值
func posVal uint64 {
 return 1 uint
}

供给了一个函数,用于创立初始 BitSet ,且支撑设置初始的元素。

函数原型如下:

func NewBitSet *BitSet {
 // ...
}

输出参数 ns 是一个 int 类型的变长参数,用于设置调集中的初始值。

假如输入参数 ns 为空的话, new 回来空调集即可。

if len == 0 {
 return new
}

假如长度非空,则要核算要拓荒的空间,经过核算最大元素的 index 可确认。

// 核算多 bitset 拓荒多个空间
max := ns[0]
for _, n := range ns {
 if n max {
 max = n
// 假如 max 0,直接回来空。
if max 0 {
 return new
// 经过 max shift 1 核算最大值 max 地点 index
// 而 index   1 即为要拓荒的空间
s := BitSet{
 data: make 1),
}

现在,能够向 BitSet 中添加元素了。

for _, n := range ns {
 if n = 0 {
 // e shift 获取索引方位,即行,一般叫 index
 // e mask 获取地点列,一般叫 pos,F1 0 F2 1
 s.data[n shift] |= posVal
 // 添加元素个数
 s.size  
// 回来创立的 BitSet
return s

元素现已悉数添加完结!

接下来是重点了,为 BitSet 添加一些办法。首要是分红两类,一是常见的增删查等根底办法,二是调集的特有操作,交并差。

首要是几个办法,分别是 Add 、 Clear 、 Contains 以及回来元素个数。假如要有更好的功能和空间运用率, Add 和 Clear 还有考虑灵敏的。

先讲 Contains ,即查看是否存在某个元素。

函数界说如下:

func  Contains bool {
}

输入参数便是要查看的元素,输出是查看成果。

完结代码如下:

// 获取元素对应 
i := index
if i = len {
 return false
return set.data[i] posVal != 0

中心便是 set.data[i] posVal != 0 这句代码,经过它判别是否存在指定元素。

再谈 Clear ,从调集中铲除某个元素,

函数界说如下:

func  Clear *BitSet {
 // ...
}

完结代码如下:

// 元素不能小于 0
if n 0 {
 return set
// 核算切片索引方位,假如超出当时索引标明的规模,回来即可。
i := index
if i = len {
 return set
// 查看是否存在元素
if d[i] posVal != 0 {
 set.data[i] ^= posVal
 set.size--
}

经过 ^ 完结指定位铲除。一起要记住 set.size-- 更新调集中元素的值。

上面的完结中有个瑕疵,便是假如一些为被置零后,或许会呈现高位悉数为 0,此刻应要经过 reslice 缩短 data 空间。

详细怎样操作呢?

经过对 set.data 履行查看,从高位查看首个不为 0 的 uint64 ,以此为基准进行 reslice 。假定,这个办法名为 trim 。

完结代码如下:

func  trim {
 d := set.data
 n := len - 1
 for n = 0 d[n] == 0 {
 set.data = d[:n 1]
}

接着,再说 Add 办法,向调集中添加某个元素。

函数界说如下:

func  Add *BitSet {
}

添加元素的话,先查看下是否有满意空间寄存新元素。假如新元素的索引方位不在当时 data 标明的规模,则要进行扩容。

完结如下:

// 检测是否有满意的空间寄存新元素
i := index
if i = len {
 // 扩容巨细为 i 1
 ndata := make
 copy
 set.data = ndata
}

悉数准备就绪后,接下来就能够进行置位添加了。在添加前,先检测下调集是否现已包括了该元素。在添加完结后,还要记住要更新下 size 。

完结代码如下:

if set.data[i] posVal == 0 {
 // 设置元素到调集中
 set.data[i] |= posVal
 s.size  
}

好了!根底的办法就介绍这么多吧。

当然,这儿的办法还能够添加更多,比方查找当时元素的下一个元素,将某个规模值都添加进调集等等等。

介绍完了根底的办法,再持续介绍调集一些特有的办法,交并差。

在正式介绍这些办法前,先引进一个辅佐办法,用于核算调集中的元素个数。之所以要引进这个办法,是由于交并差没有办法像之前在增删的时分更新 size ,要从头核算一下。

完结代码如下:

func  computeSize int {
 d := set.data
 n := 0
 for i, len := 0, len; i len; i   {
 if w := d[i]; w != 0 {
 n  = bits.OnesCount64
 return n
}

这是一个不行导出的办法,只能内部运用。遍历 data 的每个 uint64 ,假如非 0,则核算其间的元素个数。元素个数核算用到了规范库中的 bits.OnesCount64 办法。

持续介绍调集的几个办法,它们的界说相似,都是一个 BitSet 与另一个 BitSet 的运算,如下:

// 交集
func  Intersect *BitSet {
 // ...
// 并集
func  Union *BitSet {
 // ...
// 差集
func  Difference *BitSet {
 // ...
}

先介绍 Intersect ,即核算交集的办法。

一个重要条件,由于交集是 与运算 ,成果必定坐落两个参加运算的那个小规模调集中,所以,拓荒空间和遍历能够缩小到这个规模进行。

完结代码如下:

// 首要,获取这个小规模的调集的长度
minLen := min, len)
// 以 minLen 拓荒空间
intersectSet := BitSet{
 data: make,
// 以 minLen 进行遍历核算交集
for i := minLen - 1; i i-- {
 intersectSet.data[i] = set.data[i] other.data[i]
intersectSet.size = set.computeSize

这儿经过遍历逐个对每个 uint64 履行 与运算 完结交集。在完结操作后,记住核算下 intersectSet 中元素个数,即 size 的值。

再介绍并集 Union 办法。

它的核算逻辑和 Intersect 相反。并集成果所占有的空间和以参加运算的两个调集的较大调集为准。

完结代码如下:

var maxSet, minSet *BitSet
if len len {
 maxSet, minSet = set, other
} else {
 maxSet, minSet = other, set
unionSet := BitSet{
 data: make),
}

创立的 unionSet 中, data 分配空间是 len 。

由于两个调集中的悉数元素满意终究成果,但 maxSet 的高位部分无法经过遍历和 minSet 履行运算,直接复制进成果中即可。

minLen := len
copy

终究,遍历两个调集 data ,经过 或运算 核算剩下的部分。

for i := 0; i minLen; i   {
 unionSet.data[i] = set.data[i] | other.data[i]
// 更新核算 size
unionSet.size = unionSet.computeSize

介绍终究一个与调集相关的办法, Difference ,即差集操作。

差集核算成果 differenceSet 的分配空间由被减调集 set 决议。其他的操作和 Intersect 和 Union 相似,位运算经过 ^ 完结。

setLen := len
differenceSet := BitSet{
 data: make,
// 遍历 data 履行位运算。
for i := 0; i setLen; i   {
 differenceSet.data[i] = set.data[i] ^ other.data[i]
differenceSet.size = differenceSet.computeSize

独自说下调集元素的遍历,之前查看调集元素一向都是经过 Contains 办法查看是否存在。能不能把调集中的每个元素悉数遍历出来呢?

再看下 bitset 的结构,如下:

上面的调集中,榜首行 int64 的榜首个元素是 1,尾部有一位被置零。经过调查发现,前面有几个 0,榜首个元素便是什么值。

第二行 int64 的榜首元素尾部没有 0,那它的值便是 0 吗?当然不是,还有前面一行的 64 位根底,所以它的值是 64 0。

总结出什么规则了吗?笨,理论功底太差,满脑子理解,便是感觉写不清楚。看代码吧!

先看函数界说:

func  Visit )  {
 //...
}

输入参数是一个回调函数,经过它获取元素的值,否则每次都要写一大串循环运算逻辑,不太或许。回调函数的回来值 bool ,标明是否持续遍历。 Visit 的回来值标明是函数对错正常完毕的。

完结代码如下:

d := set.data
for i, len := 0, len; i len; i   {
 w := d[i]
 if w == 0 {
 continue
 // 理论功力欠好,不知道怎样描绘了。哈哈
 // 这小段代码能够理解为从元素值到 index 的逆运算,
 // 只不过得到的值是比方 0、64、128 的榜首个方位的值。
 // 0 6,仍是 0,1 6 便是 64,2 6 的便是 128
 n := i shift 
 for w != 0 {
 // 000.....000100 64~128 的话,标明 66,即 64   2,这个 2 能够由结束 0 的个数确认
 // 那怎样获取成果 0 的个数呢?能够运用 bits.TrailingZeros64 函数
 b := bits.TrailingZeros64
 if do {
 return true
 // 将现已查看的位清零
 // 为了确保尾部 0 的个数能代表元素的值
 w ^= 1 uint64 
}

运用也十分便利,示例代码如下:

set := NewBitSet
set.Visit bool {
 fmt.Println
 return false
})

好了,就说这么多吧!

本篇文章首要是参阅了几个开源包的根底上,介绍了 bitset 的完结,比方 bit 和 bitset 等。总的来说,位运算便是没有那么直观,感觉脑子不行用了。

最近在深挖 Go 言语,逐渐发现了自己的一些短板,理论常识的缺失逐渐闪现。比方,我在写这篇文章的时分,了解到 bits 规范库顶用到了 德布鲁因序列 ,此前并不清楚。前几天在研讨怎样进行 JSON 解析时,了解到了有限状况机这个常识,Go 的源码中几乎完美体现了这个常识的重要性。在学习 Go 言语组成的时分,知道了 扩展巴克斯范式 ,许多言语的文档都是这种办法来体现语法,一门了然。

作为一名电子信息专业结业的专科生,算不上核算机的科班出世,作业六年才了解到这些常识,有点愁闷,也有点振奋。假如说前六年是广度的提高,那么,接下来就应该是愈加专心的研讨了。

个人介绍

网址:

介绍:最近测验在 B 站录些小视频。录视频当是为了彻底搞懂某个常识点的终究一步吧,一起也希望能习得一些额定的才能。在讲 Go 怎样完结 bitset 的时分,发现这块内容有点难讲。思考后,

合作联系

邮箱:

电话:

地址: