golang集合数据结构与位操作功能插件库bit的使用

Golang集合数据结构与位操作功能插件库bit的使用

基本介绍

bit是一个高效的集合数据结构库，它使用位数组(bit array)或位集合(bit set)来紧凑地存储位数据，并利用位级并行性快速执行操作。

Venn diagram

安装

安装Go后，运行以下命令安装bit包：

go get github.com/yourbasic/bit

使用示例

下面是一个完整的使用示例，展示bit库的基本功能：

package main

import (
	"fmt"
	"github.com/yourbasic/bit"
)

func main() {
	// 创建一个新的位集合，最大值为100
	s := bit.New(100)

	// 添加元素
	s.Add(1)
	s.Add(2)
	s.Add(3)
	s.Add(64)  // 可以处理大数字

	// 检查元素是否存在
	fmt.Println("Contains 3:", s.Contains(3)) // true
	fmt.Println("Contains 4:", s.Contains(4)) // false

	// 删除元素
	s.Delete(2)
	fmt.Println("After deleting 2, contains 2:", s.Contains(2)) // false

	// 创建另一个位集合
	t := bit.New(100)
	t.Add(3)
	t.Add(4)
	t.Add(5)

	// 集合操作
	fmt.Println("Intersection:", s.And(t))   // 交集
	fmt.Println("Union:", s.Or(t))          // 并集
	fmt.Println("Difference:", s.AndNot(t)) // 差集

	// 遍历集合中的元素
	fmt.Print("Elements in s: ")
	s.Visit(func(n int) bool {
		fmt.Print(n, " ")
		return false // 返回true停止遍历
	})
	fmt.Println()

	// 集合大小
	fmt.Println("Size of s:", s.Size())
}

主要功能

bit库提供了以下主要功能：

  1. 基本操作：

    • Add(n) - 添加元素
    • Delete(n) - 删除元素
    • Contains(n) - 检查元素是否存在
    • Size() - 获取集合大小

  2. 集合操作：

    • And(t) - 交集
    • Or(t) - 并集
    • AndNot(t) - 差集
    • Xor(t) - 对称差集

  3. 遍历操作：

    • Visit(func(n int) bool) - 遍历集合中的元素

性能特点

  • 高效的内存使用：使用位数组紧凑存储数据
  • 快速操作：利用位级并行性加速集合操作
  • 适合处理正整数集合

注意事项

  • 该库API已冻结，不会轻易更改
  • 版本号遵循语义化版本控制
  • 仅处理正整数

更多关于golang集合数据结构与位操作功能插件库bit的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于golang集合数据结构与位操作功能插件库bit的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


Golang 集合数据结构与位操作功能插件库 bits 使用指南

在 Go 语言中，处理集合数据结构和位操作可以使用标准库中的 math/bits 包以及一些第三方库。下面我将详细介绍这些工具的使用方法。

标准库 math/bits

Go 1.9 引入了 math/bits 包，提供了丰富的位操作功能。

基本位操作

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// 计算前导零的数量
	fmt.Println(bits.LeadingZeros8(8))  // 4 (00001000 前有4个0)
	
	// 计算1的个数
	fmt.Println(bits.OnesCount8(0b10101010)) // 4
	
	// 反转位
	fmt.Printf("%08b\n", bits.Reverse8(0b11010010)) // 01001011
	
	// 循环左移
	fmt.Printf("%08b\n", bits.RotateLeft8(0b00000001, 3)) // 00001000
}

集合操作示例

虽然 math/bits 不直接提供集合操作，但我们可以用 uint 值来表示集合：

type Set uint64

func (s Set) Add(element uint) Set {
	return s | (1 << element)
}

func (s Set) Remove(element uint) Set {
	return s &^ (1 << element)
}

func (s Set) Contains(element uint) bool {
	return s&(1<<element) != 0
}

func (s Set) Union(other Set) Set {
	return s | other
}

func (s Set) Intersection(other Set) Set {
	return s & other
}

func main() {
	var s Set
	s = s.Add(1).Add(3).Add(5)
	fmt.Println(s.Contains(3)) // true
	fmt.Println(s.Contains(2)) // false
	
	s = s.Remove(3)
	fmt.Println(s.Contains(3)) // false
}

第三方库 github.com/willf/bitset

对于更复杂的位集合操作，可以使用 github.com/willf/bitset 库。

安装

go get github.com/willf/bitset

使用示例

package main

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

func main() {
	var b bitset.BitSet
	
	// 添加元素
	b.Set(10)
	b.Set(100)
	b.Set(1000)
	
	// 检查元素是否存在
	fmt.Println(b.Test(10))  // true
	fmt.Println(b.Test(11))  // false
	
	// 删除元素
	b.Clear(10)
	fmt.Println(b.Test(10))  // false
	
	// 遍历所有设置位
	for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
		fmt.Printf("Bit %d is set\n", i)
	}
	
	// 集合运算
	b1 := bitset.New(100).Set(10).Set(20)
	b2 := bitset.New(100).Set(20).Set(30)
	
	// 并集
	union := b1.Union(b2)
	fmt.Println(union.String()) // {10,20,30}
	
	// 交集
	intersection := b1.Intersection(b2)
	fmt.Println(intersection.String()) // {20}
	
	// 差集
	difference := b1.Difference(b2)
	fmt.Println(difference.String()) // {10}
}

性能考虑

  1. 对于小规模集合（元素数量<64），使用 uint64 和标准位操作是最快的
  2. 对于中等规模集合（元素数量<1000），math/bits 和简单位操作仍然高效
  3. 对于大规模稀疏集合，bitset 库更节省内存

实际应用案例

布隆过滤器

package main

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

type BloomFilter struct {
	m     uint
	k     uint
	bits  *bitset.BitSet
	seeds []uint
}

func NewBloomFilter(m, k uint) *BloomFilter {
	return &BloomFilter{
		m:     m,
		k:     k,
		bits:  bitset.New(m),
		seeds: []uint{31, 131, 1313, 13131, 131313},
	}
}

func (bf *BloomFilter) Add(item string) {
	for i := uint(0); i < bf.k; i++ {
		hash := bf.hash(item, i) % bf.m
		bf.bits.Set(hash)
	}
}

func (bf *BloomFilter) Contains(item string) bool {
	for i := uint(0); i < bf.k; i++ {
		hash := bf.hash(item, i) % bf.m
		if !bf.bits.Test(hash) {
			return false
		}
	}
	return true
}

func (bf *BloomFilter) hash(item string, seedIdx uint) uint {
	h := fnv.New32a()
	h.Write([]byte(item))
	return uint(h.Sum32()) + bf.seeds[seedIdx%uint(len(bf.seeds))]
}

func main() {
	filter := NewBloomFilter(1000, 5)
	filter.Add("hello")
	filter.Add("world")
	
	fmt.Println(filter.Contains("hello")) // true
	fmt.Println(filter.Contains("world")) // true
	fmt.Println(filter.Contains("golang")) // false (可能)
}

总结

Go 语言提供了多种处理集合和位操作的方式：

  1. 对于简单场景，使用 math/bits 和原生位操作
  2. 对于需要动态大小或更复杂操作的场景，使用 bitset 库
  3. 位集合特别适合实现布隆过滤器、权限系统等需要高效集合操作的应用

选择哪种方式取决于你的具体需求，包括集合大小、性能要求和功能需求等因素。

回到顶部