golang实现高效位集合操作插件库bitset的使用

Golang实现高效位集合操作插件库bitset的使用

简介

bitset是一个Go语言库，用于在非负整数和布尔值之间建立映射关系。它比使用map[uint]bool更高效。

该库提供了设置、清除、翻转和测试单个整数的方法，同时还支持集合的交集、并集、差集、补集和对称差运算，以及检查是否有位被设置、所有位是否被设置等功能。

安装

go get github.com/bits-and-blooms/bitset

基本使用示例

package main

import (
	"fmt"
	"math/rand"

	"github.com/bits-and-blooms/bitset"
)

func main() {
	fmt.Printf("Hello from BitSet!\n")
	var b bitset.BitSet
	// 模拟Go Fish游戏
	for i := 0; i < 100; i++ {
		card1 := uint(rand.Intn(52))
		card2 := uint(rand.Intn(52))
		b.Set(card1) // 设置位
		if b.Test(card2) { // 测试位是否设置
			fmt.Println("Go Fish!")
		}
		b.Clear(card1) // 清除位
	}

	// 方法链式调用
	b.Set(10).Set(11)

	// 遍历所有设置的位
	for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
		fmt.Println("The following bit is set:", i)
	}
	
	// 交集操作
	if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {
		fmt.Println("Intersection works.")
	} else {
		fmt.Println("Intersection doesn't work???")
	}
}

集合操作

bitset支持多种集合操作：

  • Intersection(b *BitSet) *BitSet - 交集
  • Union(b *BitSet) *BitSet - 并集
  • Difference(b *BitSet) *BitSet - 差集
  • SymmetricDifference(b *BitSet) *BitSet - 对称差
  • Complement() *BitSet - 补集

序列化

bitset支持序列化和反序列化：

const length = 9585
const oneEvery = 97
bs := bitset.New(length)
// 添加一些位
for i := uint(0); i < length; i += oneEvery {
    bs = bs.Set(i)
}

var buf bytes.Buffer
n, err := bs.WriteTo(&buf)
if err != nil {
    // 处理错误
}

// 从buf读取
bs = bitset.New()
n, err = bs.ReadFrom(&buf)
if err != nil {
    // 处理错误
}

性能提示

对于文件或网络IO操作，建议使用bufio包装流以提高性能：

f, err := os.Create("myfile")
w := bufio.NewWriter(f)

f, err := os.Open("myfile")
r := bufio.NewReader(f)

内存使用

使用N位的bitset至少需要N/8字节内存。bitset的大小至少与访问过的最大位索引一样大。如果需要处理大量位，可以考虑使用压缩位图如Roaring bitmaps。

并发安全

bitset默认不是并发安全的。如果需要在多个goroutine中使用，应该通过channel传递bitset指针或使用sync.Mutex进行同步。

测试

运行测试：

go test
go test -cover

bitset是一个功能强大且高效的位集合操作库，被多个重要系统如beego、CubeFS等在生产环境中使用。


更多关于golang实现高效位集合操作插件库bitset的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于golang实现高效位集合操作插件库bitset的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


Golang高效位集合操作：bitset库使用指南

bitset是Go语言中一个高效的位集合操作库，特别适合需要处理大量布尔值或进行位级操作的场景。下面详细介绍其使用方法。

安装bitset

go get github.com/willf/bitset

基本使用

创建bitset

package main

import (
	"fmt"
	"github.com/willf/bitset"
)

func main() {
	// 创建一个初始容量为100的bitset
	var b bitset.BitSet
	b.Set(10).Set(20).Set(30) // 设置第10、20、30位为1
	
	// 带初始容量的创建方式
	b2 := bitset.New(1000)
	b2.Set(100).Set(200)
	
	fmt.Println(b.String()) // 输出位集合的字符串表示
}

基本操作

// 设置位
b.Set(5)      // 将第5位设为1
b.SetTo(5, true) // 同上

// 清除位
b.Clear(5)    // 将第5位设为0
b.SetTo(5, false) // 同上

// 测试位
if b.Test(5) {
    fmt.Println("第5位是1")
}

// 翻转位
b.Flip(5)     // 如果第5位是0变为1，是1变为0

// 获取长度
length := b.Len() // 返回bitset的容量
count := b.Count() // 返回被设置为1的位数

高级操作

集合运算

b1 := bitset.New(100).Set(10).Set(20)
b2 := bitset.New(100).Set(20).Set(30)

// 并集
b1.Union(b2) // b1 = b1 ∪ b2

// 交集
b1.Intersection(b2) // b1 = b1 ∩ b2

// 差集
b1.Difference(b2) // b1 = b1 - b2

// 对称差集(XOR)
b1.SymmetricDifference(b2) // b1 = (b1 - b2) ∪ (b2 - b1)

遍历设置位

// 方法1：使用NextSet方法
for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
    fmt.Printf("位%d被设置\n", i)
}

// 方法2：转换为uint切片
setBits := b.Bytes()
for _, word := range setBits {
    // 处理每个word
}

序列化与反序列化

// 序列化为字节切片
data, err := b.MarshalBinary()
if err != nil {
    panic(err)
}

// 从字节切片反序列化
var newB bitset.BitSet
err = newB.UnmarshalBinary(data)
if err != nil {
    panic(err)
}

性能优化技巧

  1. 预分配足够空间：如果知道大概需要多少位，创建时指定足够容量避免扩容开销
// 预分配100万位的空间
b := bitset.New(1000000)

  1. 批量操作：尽量使用集合运算代替单一位操作

  2. 重用bitset：考虑使用sync.Pool来重用bitset对象

var bitsetPool = sync.Pool{
    New: func() interface{} {
        return bitset.New(10000)
    },
}

func getBitset() *bitset.BitSet {
    b := bitsetPool.Get().(*bitset.BitSet)
    b.ClearAll() // 清空重用
    return b
}

func putBitset(b *bitset.BitSet) {
    bitsetPool.Put(b)
}

实际应用示例

素数筛法

func sieve(max uint) *bitset.BitSet {
    b := bitset.New(max)
    
    // 0和1不是素数
    b.Set(0).Set(1)
    
    // 筛法
    for i := uint(2); i < max; i++ {
        if !b.Test(i) {
            for j := 2 * i; j < max; j += i {
                b.Set(j)
            }
        }
    }
    
    // 反转，使素数为1
    b.InPlaceNot()
    return b
}

布隆过滤器

type BloomFilter struct {
    bitset *bitset.BitSet
    size   uint
    seeds  []uint
}

func NewBloomFilter(size uint, seeds []uint) *BloomFilter {
    return &BloomFilter{
        bitset: bitset.New(size),
        size:   size,
        seeds:  seeds,
    }
}

func (bf *BloomFilter) Add(data []byte) {
    for _, seed := range bf.seeds {
        hash := murmur3.Sum32WithSeed(data, uint32(seed))
        bf.bitset.Set(uint(hash) % bf.size)
    }
}

func (bf *BloomFilter) Contains(data []byte) bool {
    for _, seed := range bf.seeds {
        hash := murmur3.Sum32WithSeed(data, uint32(seed))
        if !bf.bitset.Test(uint(hash) % bf.size) {
            return false
        }
    }
    return true
}

bitset库在内存使用和性能上都非常高效，特别适合需要处理大量布尔标志的场景，如布隆过滤器、权限系统、素数计算等。

回到顶部