Golang中Bit数组的实现方式
Go语言里的集合一般会用map[T]bool这种形式来表示,T代表元素类型。集合用map类型来表示虽然非常灵活,但我们可以以一种更好的形式来表示它。
例如在数据流分析领域,集合元素通常是一个非负整数,集合会包含很多元素,并且集合会经常进行并集、交集操作,这种情况下,bit数组会比map表现更加理想。
一个bit数组通常会用一个无符号数或者称之为“字”的slice来表示,每一个元素的每一位都表示集合里的一个值。当集合的第i位被设置时,我们才说这个集合包含元素i。
下面的这个程序展示了一个简单的bit数组类型,并且实现了三个函数来对这个bit数组来进行操作:
package main import ( "bytes" "fmt" ) // An IntSet is a set of small non-negative integers. // Its zero value represents the empty set. type IntSet struct { words []uint } const ( bitNum = (32 << (^uint(0) >> 63)) //根据平台自动判断决定是32还是64 ) // Has reports whether the set contains the non-negative value x. func (s *IntSet) Has(x int) bool { word, bit := x/bitNum, uint(x%bitNum) return word < len(s.words) && s.words[word]&(1<<bit) != 0 } // Add adds the non-negative value x to the set. func (s *IntSet) Add(x int) { word, bit := x/bitNum, uint(x%bitNum) for word >= len(s.words) { s.words = append(s.words, 0) } s.words[word] |= 1 << bit } //A与B的交集,合并A与B // UnionWith sets s to the union of s and t. func (s *IntSet) UnionWith(t *IntSet) { for i, tword := range t.words { if i < len(s.words) { s.words[i] |= tword } else { s.words = append(s.words, tword) } } }
因为每一个字都有64个二进制位,所以为了定位x的bit位,我们用了x/64的商作为字的下标,并且用x%64得到的值作为这个字内的bit的所在位置。
例如,对于数字1,将其加入比特数组:
func (s *IntSet) Add(x int) { word, bit := x/bitNum, uint(x%bitNum) //0, 1 := 1/64, uint(1%64) for word >= len(s.words) { // 条件不满足 s.words = append(s.words, 0) } s.words[word] |= 1 << bit // s.words[0] |= 1 << 1 } // 把1存入后,words数组变为了[]uint64{2}
同理,假如我们再将66加入比特数组:
func (s *IntSet) Add(x int) { word, bit := x/bitNum, uint(x%bitNum) //1, 2 := 66/64, uint(66%64) for word >= len(s.words) { // 条件满足 s.words = append(s.words, 0) // 此时s.words = []uint64{2, 0} } s.words[word] |= 1 << bit // s.words[1] |= 1 << 2 } // 继续把66存入后,words数组变为了[]uint64{2, 4}
所以,对于words,每个元素可存储的值有64个,每超过64个则进位,即添加一个元素。(注意,0也占了一位,所以64才要进位,第一个元素可存储0-63)。
所以,对于words中的一个元素,要转换为具体的值时:首先取到其位置i,用 64 * i 作为已进位数(类似于每10位要进位), 然后将这个元素转换为二进制数,从右往左数,第多少位为1则表示相应的有这个值,用这个位数 x+64 *i 即为我们存入的值。
相应的,可有如下String()函数
// String returns the set as a string of the form "{1 2 3}". func (s *IntSet) String() string { var buf bytes.Buffer buf.WriteByte('{') for i, word := range s.words { if word == 0 { continue } for j := 0; j < bitNum; j++ { if word&(1<<uint(j)) != 0 { if buf.Len() > len("{") { buf.WriteByte(' ') } fmt.Fprintf(&buf, "%d", bitNum*i+j) } } } buf.WriteByte('}') return buf.String() }
例如,前面存入了1和66后,转换过程为:
// []uint64{2 4} // 对于2: 1 << 1 = 2; 所以 x = 0 * 64 + 1 // 对于4: 1 << 2 = 4; 所以 x = 1 * 64 + 2 // 所以转换为String为{1 66}
实现比特数组的其他方法函数
func (s *IntSet) Len() int { var len int for _, word := range s.words { for j := 0; j < bitNum; j++ { if word&(1<<uint(j)) != 0 { len++ } } } return len } func (s *IntSet) Remove(x int) { word, bit := x/bitNum, uint(x%bitNum) if s.Has(x) { s.words[word] ^= 1 << bit } } func (s *IntSet) Clear() { s.words = append([]uint{}) } func (s *IntSet) Copy() *IntSet { intSet := &IntSet{ words: []uint{}, } for _, value := range s.words { intSet.words = append(intSet.words, value) } return intSet } func (s *IntSet) AddAll(args ...int) { for _, x := range args { s.Add(x) } } //A与B的并集,A与B中均出现 func (s *IntSet) IntersectWith(t *IntSet) { for i, tword := range t.words { if i >= len(s.words) { continue } s.words[i] &= tword } } //A与B的差集,元素出现在A未出现在B func (s *IntSet) DifferenceWith(t *IntSet) { t1 := t.Copy() //为了不改变传参t,拷贝一份 t1.IntersectWith(s) for i, tword := range t1.words { if i < len(s.words) { s.words[i] ^= tword } } } //A与B的并差集,元素出现在A没有出现在B,或出现在B没有出现在A func (s *IntSet) SymmetricDifference(t *IntSet) { for i, tword := range t.words { if i < len(s.words) { s.words[i] ^= tword } else { s.words = append(s.words, tword) } } } //获取比特数组中的所有元素的slice集合 func (s *IntSet) Elems() []int { var elems []int for i, word := range s.words { for j := 0; j < bitNum; j++ { if word&(1<<uint(j)) != 0 { elems = append(elems, bitNum*i+j) } } } return elems }
至此,比特数组的常用方法函数都已实现,现在可以来使用它。
func main() { var x, y IntSet x.Add(1) x.Add(144) x.Add(9) fmt.Println("x:", x.String()) // "{1 9 144}" y.Add(9) y.Add(42) fmt.Println("y:", y.String()) // "{9 42}" x.UnionWith(&y) fmt.Println("x unionWith y:", x.String()) // "{1 9 42 144}" fmt.Println("x has 9,123:", x.Has(9), x.Has(123)) // "true false" fmt.Println("x len:", x.Len()) //4 fmt.Println("y len:", y.Len()) //2 x.Remove(42) fmt.Println("x after Remove 42:", x.String()) //{1 9 144} z := x.Copy() fmt.Println("z copy from x:", z.String()) //{1 9 144} x.Clear() fmt.Println("clear x:", x.String()) //{} x.AddAll(1, 2, 9) fmt.Println("x addAll 1,2,9:", x.String()) //{1 2 9} x.IntersectWith(&y) fmt.Println("x intersectWith y:", x.String()) //{9} x.AddAll(1, 2) fmt.Println("x addAll 1,2:", x.String()) //{1 2 9} x.DifferenceWith(&y) fmt.Println("x differenceWith y:", x.String()) //{1 2} x.AddAll(9, 144) fmt.Println("x addAll 9,144:", x.String()) //{1 2 9 144} x.SymmetricDifference(&y) fmt.Println("x symmetricDifference y:", x.String()) //{1 2 42 144} for _, value := range x.Elems() { fmt.Print(value, " ") //1 2 42 144 } }
以上为个人经验,希望能给大家一个参考,也希望大家多多支持猪先飞。如有错误或未考虑完全的地方,望不吝赐教。
相关文章
- 在php中eval是一个函数并且不能直接禁用了,但eval函数又相当的危险了经常会出现一些问题了,今天我们就一起来看看eval函数对数组的操作 例子, <?php $data="array...2016-11-25
- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 本文章提供在量的数据中级操作实例有如对键名比较计算数组的差集 计算差集 给指定数组中插入一个元素 反转数组 交集赋值新的数组实例。 //定义回调函数 funct...2016-11-25
- 这篇文章主要介绍了C#二维数组基本用法,以实例形式分析了C#中二维数组的定义、初始化、遍历及打印等用法,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- Array数组在C#中同样是最基本的数据结构,下面为大家C#数组的常用操作方法小结,皆为细小的代码段,欢迎收看收藏...2020-06-25
- 下面一段代码给大家介绍php curl模拟post请求的示例代码,具体代码如下: <?php$uri = "http://www.cnblogs.com/test.php";//这里换成自己的服务器的地址// 参数数组$data = array ( 'name' => 'tanteng'// 'passwor...2015-11-24
- 下面小编就为大家带来一篇C# 拷贝数组的几种方法(总结)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了golang 调用 php7详解及实例的相关资料,需要的朋友可以参考下...2017-01-15
- 本文记录的要实现的功能类似于 MySQL 中的 ORDER BY,上个项目中有遇到这样的一个需求。 要求:从两个不同的表中获取各自的4条数据,然后整合(array_merge)成一个数组,再根据数据的创建时间降序排序取前4条。 遇到这个...2014-06-07
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#将字节数组转成易读的字符串的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了C#读取文件所有行到数组的方法,涉及C#针对文件及数组的相关操作技巧,需要的朋友可以参考下...2020-06-25
- 如何将下面的二维数组转为一维数组。复制代码 代码如下:$msg = array( array( 'id'=>'45', 'name'=>'jack' ), array( 'id'=>'34', 'name'=>'mary' ), array( 'id...2014-05-31
- 在php中为我们提供了一个函数var_export 他可以直接将php代码入到一个文件中哦。 代码如下 复制代码 var_export($times,true);后面不加tru...2016-11-25
- 本文为代码分享,也是在工作中看到一些“大牛”的代码,做做分享。 具体是这样的,如下一个二维数组,是从库中读取出来的。 代码清单: 复制代码 代码如下: $user = array( 0 => array( 'id' => 1, 'name' => '张三', 'ema...2014-06-07
- 1.前言 昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题。但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件。2.简单但效率不高的算法 我首先想到的是使用...2013-10-04
- 今天小编就为大家分享一篇python 实现将Numpy数组保存为图像,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
C#中数组、ArrayList、List、Dictionary的用法与区别浅析(存取数据)
在工作中经常遇到C#数组、ArrayList、List、Dictionary存取数据,但是该选择哪种类型进行存储数据呢?很迷茫,今天小编抽空给大家整理下这方面的内容,需要的朋友参考下吧...2020-06-25- 这篇文章主要介绍了C#中List和数组之间转换的方法,涉及比较简单的转换技巧,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇Perl与JS的对比分析(数组、哈希)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-29