一般找Golang相关的包都是先去 awesome-go 找,里面按分类都归类好了。今天要推荐的是 bitset 。之前在工作中对于已有项目的优化探索了很久,发现了这个包之后,让我眼前一亮,找到了未来优化的方向。
首先这是一个数据结构。从名字set不难发现,这是一个集合的数据结构。bit的含义也比较好懂,通过set是通过bit实现的。如果你需要一个集合,正好集合内的元素都是正整数,那么用这个就没错了。
import "github.com/willf/bitset" var b bitset.BitSet // 定义一个BitSet对象 b.Set(10).Set(11) // 给这个set新增两个值10和11 if b.Test(1000) { // 查看set中是否有1000这个值(我觉得Test这个名字起得是真差劲,为啥不叫Exist) b.Clear(1000) // 情况set } for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) { // 遍历整个Set fmt.Println("The following bit is set:",i); } if B.Intersection(bitset.New(100).Set(10)).Count() > 1 { // set求交集 fmt.Println("Intersection works.") }
这个包功能已经非常完善了,完整的文档可以参考它的 godoc
。我使用这些包,除了看重基础功能(对于集合,就是增删改查这些),还有就是得方便调试。bitset内部保存数字都是按位存的,如果调试的时候是把bitset的内部数据给我看,我也是看不懂的,还好这个包提供了 String()
方法,可以把我设置的数据已字符串的形式返回,棒棒哒。
研究一下实现原理才是我的Style。大概说一下原理。正整数集合可以都放到一个大的整数里面,用位来表示数字。比如 1001
就可以表示0和2这两个数字。用一个bit代替了一个 int
,可以大大降低内存的占用。但是一个整数最大也就64位,也就是说最大表示的数字就是64了,所以可以通过多个 int
拼接的形式来表示大整数。
bitset的内部数据结构,很亲切有木有:
type BitSet struct { length uint // set的大小 set []uint64 // 这个就会被用来表示一个大整数 }
通过下面的测试代码对于内部实现一探究竟:
var b bitset.BitSet // 定义一个BitSet对象 fmt.Println(b.Bytes()) b.Set(0) fmt.Println(b.Bytes(),0) b.Set(10) // 给这个set新增两个值10 fmt.Println(b.Bytes(),0,10) b.Set(64) fmt.Println(b.Bytes(),0,10,64) if b.Test(1000) { // 查看set中是否有1000这个值(我觉得Test这个名字起得是真差劲,为啥不叫Exist) b.Clear(1000) // 情况set }
输出: [] [1] 0 [1025] 0 10 [1025 1] 0 10 64
[]
0x00000001
0x00000041
0x00000041
和 0x00000001
。set这个数组里面,从前往后表示的数据依次增加,但是在 uint64
内部,是从低位开始,低位表示小的数。
表示正整数的集合,Golang有很多种方式,自带的 map
就可以,当然这是最差的一种选择,首先就是内存的浪费,其次是每次查找还涉及到hash计算,虽然理论上hashmap的复杂度是O(1),实际上跟bitset比完全就是渣渣。此外,bitset都得升级版 roaring
也是不错的选择。如果你要保存的数据是10000000000这种级别的,那么用bitset就会存在低位浪费内存的情况,roaring可以用来压缩空间。
import ( "testing" "github.com/RoaringBitmap/roaring" "github.com/willf/bitset" ) func BenchmarkMap(b *testing.B) { var B = make(map[int]int8, 3) B[10] = 1 B[11] = 1 for i := 0; i < b.N; i++ { if _, exists := B[1]; exists { } if _, exists := B[11]; exists { } if _, exists := B[1000000]; exists { } } } func BenchmarkBitset(b *testing.B) { var B bitset.BitSet B.Set(10).Set(11) for i := 0; i < b.N; i++ { if B.Test(1) { } if B.Test(11) { } if B.Test(1000000) { } } } func BenchmarkRoaring(b *testing.B) { for i := 0; i < b.N; i++ { B := roaring.BitmapOf(10, 11) if B.ContainsInt(1) { } if B.ContainsInt(11) { } if B.ContainsInt(1000000) { } } } $ go test -bench=.* -benchmem BenchmarkMap-2 50000000 28.4 ns/op 0 B/op 0 allocs/op BenchmarkBitset-2 2000000000 1.86 ns/op 0 B/op 0 allocs/op BenchmarkRoaring-2 3000000 492 ns/op 152 B/op 6 allocs/op
如果是比较连续的非负整数,推荐用bitset解决集合的问题。当然具体问题具体分析。
本文所涉及到的完整源码请 参考 。