README
¶
bitset
Go language library to map between non-negative integers and boolean values
This library is part of the awesome go collection. It is used in production by several important systems:
Description
Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.
It provides methods for setting, clearing, flipping, and testing individual integers.
But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of positive bits.
BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.
Many of the methods, including Set, Clear, and Flip, return a BitSet pointer, which allows for chaining.
Example use:
package main
import (
"fmt"
"math/rand"
"github.com/bits-and-blooms/bitset"
)
func main() {
fmt.Printf("Hello from BitSet!\n")
var b bitset.BitSet
// play some 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)
}
// Chaining
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???")
}
}
Package documentation is at: https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc
Serialization
You may serialize a bitset safely and portably to a stream of bytes as follows:
const length = 9585
const oneEvery = 97
bs := bitset.New(length)
// Add some bits
for i := uint(0); i < length; i += oneEvery {
bs = bs.Set(i)
}
var buf bytes.Buffer
n, err := bs.WriteTo(&buf)
if err != nil {
// failure
}
// Here n == buf.Len()
You can later deserialize the result as follows:
// Read back from buf
bs = bitset.New()
n, err = bs.ReadFrom(&buf)
if err != nil {
// error
}
// n is the number of bytes read
The ReadFrom function attempts to read the data into the existing
BitSet instance, to minimize memory allocations.
Performance tip:
When reading and writing to a file or a network connection, you may get better performance by
wrapping your streams with bufio instances.
E.g.,
f, err := os.Create("myfile")
w := bufio.NewWriter(f)
f, err := os.Open("myfile")
r := bufio.NewReader(f)
Memory Usage
The memory usage of a bitset using N bits is at least N/8 bytes. The number of bits in a bitset is at least as large as one plus the greatest bit index you have accessed. Thus it is possible to run out of memory while using a bitset. If you have lots of bits, you might prefer compressed bitsets, like the Roaring bitmaps and its Go implementation.
The roaring library allows you to go back and forth between compressed Roaring bitmaps and the conventional bitset instances:
mybitset := roaringbitmap.ToBitSet()
newroaringbitmap := roaring.FromBitSet(mybitset)
Goroutine safety
In general, it not safe to access
the same BitSet using different goroutines--they are
unsynchronized for performance. Should you want to access
a BitSet from more than one goroutine, you should
provide synchronization. Typically this is done by using channels to pass
the *BitSet around (in Go style; so there is only ever one owner),
or by using sync.Mutex to serialize operations on BitSets.
Implementation Note
Go 1.9 introduced a native math/bits library. We provide backward compatibility to Go 1.7, which might be removed.
It is possible that a later version will match the math/bits return signature for counts (which is int, rather than our library's uint64). If so, the version will be bumped.
Installation
go get github.com/bits-and-blooms/bitset
Contributing
If you wish to contribute to this project, please branch and issue a pull request against master ("GitHub Flow")
Running all tests
Before committing the code, please check if it passes tests, has adequate coverage, etc.
go test
go test -cover
Documentation
¶
Overview ¶
Package bitset 实现了位集合，它是一个在非负整数和布尔值之间的映射。 相比于 map[uint]bool，它的效率更高。
它提供了设置、清除、翻转和测试单个整数的方法。
同时也提供了集合的交集、并集、差集、补集和对称操作，以及测试是否有任何位被设置、 所有位被设置或没有位被设置的方法，并可以查询位集合的当前长度和设置位的数量。
位集合会扩展到最大设置位的大小；内存分配大约是最大位数，其中最大位是最大的设置位。 位集合永远不会缩小。在创建时，可以给出将要使用的位数的提示。
许多方法，包括 Set、Clear 和 Flip，都返回一个 BitSet 指针，这允许链式调用。
使用示例:
import "bitset"
var b BitSet
b.Set(10).Set(11)
if b.Test(1000) {
b.Clear(1000)
}
if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
fmt.Println("Intersection works.")
}
作为 BitSets 的替代方案，应该查看 'big' 包，它提供了位集合的(较少集合理论)视图。
Index ¶
- func Base64StdEncoding()
- func BigEndian()
- func BinaryOrder() binary.ByteOrder
- func Cap() uint
- func LittleEndian()
- type BitSet
- func (b *BitSet) All() bool
- func (b *BitSet) Any() bool
- func (b *BitSet) BinaryStorageSize() int
- func (b *BitSet) Bytes() []uint64
- func (b *BitSet) Clear(i uint) *BitSet
- func (b *BitSet) ClearAll() *BitSet
- func (b *BitSet) Clone() *BitSet
- func (b *BitSet) Compact() *BitSet
- func (b *BitSet) Complement() (result *BitSet)
- func (b *BitSet) Copy(c *BitSet) (count uint)
- func (b *BitSet) CopyFull(c *BitSet)
- func (b *BitSet) Count() uint
- func (b *BitSet) DeleteAt(i uint) *BitSet
- func (b *BitSet) Difference(compare *BitSet) (result *BitSet)
- func (b *BitSet) DifferenceCardinality(compare *BitSet) uint
- func (b *BitSet) DumpAsBits() string
- func (b *BitSet) Equal(c *BitSet) bool
- func (b *BitSet) Flip(i uint) *BitSet
- func (b *BitSet) FlipRange(start, end uint) *BitSet
- func (b *BitSet) InPlaceDifference(compare *BitSet)
- func (b *BitSet) InPlaceIntersection(compare *BitSet)
- func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet)
- func (b *BitSet) InPlaceUnion(compare *BitSet)
- func (b *BitSet) InsertAt(idx uint) *BitSet
- func (b *BitSet) Intersection(compare *BitSet) (result *BitSet)
- func (b *BitSet) IntersectionCardinality(compare *BitSet) uint
- func (b *BitSet) IsStrictSuperSet(other *BitSet) bool
- func (b *BitSet) IsSuperSet(other *BitSet) bool
- func (b *BitSet) Len() uint
- func (b *BitSet) MarshalBinary() ([]byte, error)
- func (b BitSet) MarshalJSON() ([]byte, error)
- func (b *BitSet) NextClear(i uint) (uint, bool)
- func (b *BitSet) NextSet(i uint) (uint, bool)
- func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint)
- func (b *BitSet) None() bool
- func (b *BitSet) Rank(index uint) uint
- func (b *BitSet) ReadFrom(stream io.Reader) (int64, error)
- func (b *BitSet) Select(index uint) uint
- func (b *BitSet) Set(i uint) *BitSet
- func (b *BitSet) SetAll() *BitSet
- func (b *BitSet) SetBitsetFrom(buf []uint64)
- func (b *BitSet) SetTo(i uint, value bool) *BitSet
- func (b *BitSet) ShiftLeft(bits uint)
- func (b *BitSet) ShiftRight(bits uint)
- func (b *BitSet) Shrink(lastbitindex uint) *BitSet
- func (b *BitSet) String() string
- func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet)
- func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint
- func (b *BitSet) Test(i uint) bool
- func (b *BitSet) Union(compare *BitSet) (result *BitSet)
- func (b *BitSet) UnionCardinality(compare *BitSet) uint
- func (b *BitSet) UnmarshalBinary(data []byte) error
- func (b *BitSet) UnmarshalJSON(data []byte) error
- func (b *BitSet) WriteTo(stream io.Writer) (int64, error)
- type Error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Base64StdEncoding ¶
func Base64StdEncoding()
Base64StdEncoding 设置 Marshal/Unmarshal BitSet 使用标准的 base64 编码 (默认使用 base64.URLEncoding)
func BinaryOrder ¶
BinaryOrder 返回当前的二进制字节序 参见 LittleEndian() 和 BigEndian() 来更改字节序
func Cap ¶
func Cap() uint
Cap 返回可以存储在 BitSet 中的位的理论总容量 在 32 位系统上是 4294967295，在 64 位系统上是 18446744073709551615 注意这进一步受限于 Go 中的最大分配大小和可用内存，就像任何 Go 数据结构一样 返回值:
- uint: 最大容量
func LittleEndian ¶
func LittleEndian()
LittleEndian 设置 Marshal/Unmarshal 二进制使用小端序 (默认使用 binary.BigEndian)
Types ¶
type BitSet ¶
type BitSet struct {
// contains filtered or unexported fields
}
BitSet 是一个位集合。BitSet 的零值是一个长度为 0 的空集合。
func FromWithLength ¶
FromWithLength 从字数组和长度构造位集合 参数:
- len: uint 位集合的长度
- set: []uint64 用于创建位集合的字数组
返回值:
- *BitSet: 新创建的位集合
func (*BitSet) Bytes ¶
Bytes 返回位集合作为 64 位字的数组，提供对内部表示的直接访问 返回的不是副本，因此对返回的切片的更改会影响位集合 这是为高级用户设计的 返回值:
- []uint64: 位集合的内部表示
func (*BitSet) Clear ¶
Clear 将位 i 设置为 0。这永远不会导致内存分配。它总是安全的 参数:
- i: uint 要清除的位索引
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) Compact ¶
Compact 缩小位集合以保留所有设置的位，同时最小化内存使用 此函数会调用 Shrink 分配一个新的切片来存储新的位，所以在 GC 运行之前你可能会看到内存使用增加 通常这不应该是问题，但如果你有一个极大的位集合，重要的是要理解旧的位集合 将保留在内存中，直到 GC 释放它 如果内存受限，此函数可能会导致 panic 返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) Copy ¶
Copy 将当前位集合复制到目标位集合 使用Go数组复制语义:复制的位数是当前位集合(Len())和目标位集合中位数的较小值 参数:
- c: *BitSet 目标位集合
返回值:
- count: uint 复制到目标位集合的位数
func (*BitSet) DeleteAt ¶
DeleteAt 从位集合中删除指定索引位置的位 被删除位左侧的所有位向右移动 1 位 此操作的运行时间可能相对较慢，为 O(length) 参数:
- i: uint 要删除的位的索引
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) Difference ¶
Difference 计算基集合与其他集合的差集 这是BitSet的&^(与非)运算等价操作 参数:
- compare: *BitSet 要计算差集的位集合
返回值:
- *BitSet: 差集结果
func (*BitSet) DifferenceCardinality ¶
DifferenceCardinality 计算差集的基数 参数:
- compare: *BitSet 要计算差集的位集合
返回值:
- uint: 差集中的位数
func (*BitSet) DumpAsBits ¶
DumpAsBits 将位集合转储为位字符串 按照Go的惯例,最低有效位打印在最后(索引0在字符串末尾) 这对于调试和测试很有用。不适合序列化 返回值:
- string: 位字符串表示
func (*BitSet) Equal ¶
Equal 测试两个位集合是否相等 如果长度不同则返回false,否则只有当所有相同的位被设置时才返回true 参数:
- c: *BitSet 要比较的位集合
返回值:
- bool: 两个位集合是否相等
func (*BitSet) Flip ¶
Flip 翻转位 i 警告：对 'i' 使用非常大的值可能导致内存不足和 panic： 调用者负责根据其内存容量提供合理的参数 参数:
- i: uint 要翻转的位索引
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) FlipRange ¶
FlipRange 翻转区间 [start, end) 中的位 警告：对 'end' 使用非常大的值可能导致内存不足和 panic： 调用者负责根据其内存容量提供合理的参数 参数:
- start: uint 起始位索引(包含)
- end: uint 结束位索引(不包含)
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) InPlaceDifference ¶
InPlaceDifference 就地计算基集合与其他集合的差集 这是BitSet的&^(与非)运算等价操作 参数:
- compare: *BitSet 要计算差集的位集合
func (*BitSet) InPlaceIntersection ¶
InPlaceIntersection 就地计算基集合与比较集合的交集 这是BitSet的&(与)运算等价操作,会修改基集合 参数:
- compare: *BitSet 要计算交集的位集合
func (*BitSet) InPlaceSymmetricDifference ¶
InPlaceSymmetricDifference 就地计算基集合与比较集合的对称差 这是BitSet的^(异或)运算等价操作,会修改基集合 参数:
- compare: *BitSet 要计算对称差的位集合
func (*BitSet) InPlaceUnion ¶
InPlaceUnion 就地计算基集合与比较集合的并集 这是BitSet的|(或)运算等价操作,会修改基集合 参数:
- compare: *BitSet 要计算并集的位集合
func (*BitSet) InsertAt ¶
InsertAt 在指定索引处插入一个位 从给定的索引位置开始，将集合中的所有位向左移动 1 位， 并将索引位置设置为 0 根据位集合的大小和插入位置，此方法可能会非常慢， 在某些情况下可能会导致整个位集合被重新复制 参数:
- idx: uint 要插入位的索引
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) Intersection ¶
Intersection 计算基集合与其他集合的交集 这是BitSet的&(与)运算等价操作 参数:
- compare: *BitSet 要计算交集的位集合
返回值:
- *BitSet: 交集结果
func (*BitSet) IntersectionCardinality ¶
IntersectionCardinality 计算两个位集合交集的基数(设置为1的位的数量) 参数:
- compare: *BitSet 要计算交集的位集合
返回值:
- uint: 交集中设置为1的位的数量
func (*BitSet) IsStrictSuperSet ¶
IsStrictSuperSet 检查此集合是否是另一个集合的真超集 参数:
- other: *BitSet 要检查的子集
返回值:
- bool: 如果此集合是other的真超集返回true,否则返回false
func (*BitSet) IsSuperSet ¶
IsSuperSet 检查此集合是否是另一个集合的超集 参数:
- other: *BitSet 要检查的子集
返回值:
- bool: 如果此集合是other的超集返回true,否则返回false
func (*BitSet) Len ¶
Len 返回 BitSet 中的位数 注意它与 Count 函数不同 返回值:
- uint: 位集合的长度
Example ¶
var b BitSet
b.Set(8)
fmt.Println("len", b.Len())
fmt.Println("count", b.Count())
Output: len 9 count 1
func (*BitSet) MarshalBinary ¶
MarshalBinary 将BitSet编码为二进制形式并返回结果 详见WriteTo 返回值:
- []byte: 编码后的字节切片
- error: 如果发生错误则返回,否则返回nil
func (BitSet) MarshalJSON ¶
MarshalJSON 将位集合编码为 JSON 结构 返回值:
- []byte: 编码后的 JSON 字节切片
- error: 如果发生错误则返回,否则返回nil
func (*BitSet) NextClear ¶
NextClear 从指定索引开始查找下一个未设置的位，包括当前索引 参数:
- i: uint 开始查找的位索引
返回值:
- uint: 找到的第一个未设置位的索引
- bool: 是否找到未设置位(true=找到, false=未找到,即所有位都被设置)
func (*BitSet) NextSet ¶
NextSet 返回从指定索引开始的下一个设置的位 包括可能的当前索引，同时返回一个错误代码 (true = 有效, false = 未找到设置的位) 参数:
- i: uint 开始搜索的索引
返回值:
- uint: 下一个设置的位的索引
- bool: 是否找到设置的位
func (*BitSet) NextSetMany ¶
NextSetMany returns many next bit sets from the specified index, including possibly the current index and up to cap(buffer). If the returned slice has len zero, then no more set bits were found
buffer := make([]uint, 256) // this should be reused
j := uint(0)
j, buffer = bitmap.NextSetMany(j, buffer)
for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) {
for k := range buffer {
do something with buffer[k]
}
j += 1
}
It is possible to retrieve all set bits as follow:
indices := make([]uint, bitmap.Count()) bitmap.NextSetMany(0, indices)
However if bitmap.Count() is large, it might be preferable to use several calls to NextSetMany, for performance reasons.
func (*BitSet) Rank ¶
Rank 返回位集合中从开始到指定索引(包含)的已设置位的数量 参考 https://en.wikipedia.org/wiki/Ranking#Ranking_in_statistics 参数:
- index: uint 要计算到的索引位置
返回值:
- uint: 已设置位的数量
func (*BitSet) ReadFrom ¶
ReadFrom 从使用WriteTo写入的流中读取BitSet 格式为: 1. uint64 length 2. []uint64 set 详见WriteTo 成功时返回读取的字节数 如果当前BitSet不够大,它会被扩展 如果发生错误,BitSet要么保持不变,要么在错误发生太晚无法保留内容时被清空
性能提示:如果此函数用于从磁盘或网络连接读取, 使用bufio.Reader包装流可能会有益处 例如:
f, err := os.Open("myfile")
r := bufio.NewReader(f)
参数:
- stream: io.Reader 读取源流
返回值:
- int64: 读取的字节数
- error: 如果发生错误则返回,否则返回nil
func (*BitSet) Select ¶
Select 返回第 j 个已设置位的索引,其中 j 是参数 调用者负责确保 0 <= j < Count(): 当 j 超出范围时,函数返回位集合的长度(b.length) 注意:此函数与 Rank 函数的约定不同,Rank 函数在对最小值排名时返回 1 我们遵循 Select 和 Rank 的传统教科书定义 参数:
- index: uint 要查找的第几个已设置位
返回值:
- uint: 找到的已设置位的索引
func (*BitSet) Set ¶
Set 将位 i 设置为 1，位集合的容量会相应自动增加 警告：对 'i' 使用非常大的值可能导致内存不足和 panic： 调用者负责根据其内存容量提供合理的参数 内存使用量至少略高于 i/8 字节 参数:
- i: uint 要设置的位索引
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) SetBitsetFrom ¶
SetBitsetFrom 使用整数数组填充位集合，而不创建新的 BitSet 实例 参数:
- buf: []uint64 用于填充位集合的整数数组
func (*BitSet) SetTo ¶
SetTo 将位 i 设置为指定的值 警告：对 'i' 使用非常大的值可能导致内存不足和 panic： 调用者负责根据其内存容量提供合理的参数 参数:
- i: uint 要设置的位索引
- value: bool 要设置的值
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) ShiftLeft ¶
ShiftLeft 对位集合进行左移操作,类似于 << 运算 左移可能需要扩展位集合大小。我们通过检测最左边的已设置位来避免不必要的内存操作 如果移位导致超出容量,函数会 panic 参数:
- bits: uint 要左移的位数
func (*BitSet) Shrink ¶
Shrink 缩小位集合，使得提供的值成为最后一个可能设置的值 它清除所有大于提供的索引的位，并减少集合的大小和长度 注意：参数值不是新的位长度：它是函数调用后可以存储在位集合中的最大值 新的位长度是参数值 + 1。因此不可能使用此函数将长度设置为 0， 此函数调用后的最小长度值为 1
分配一个新的切片来存储新的位，所以在 GC 运行之前你可能会看到内存使用增加 通常这不应该是问题，但如果你有一个极大的位集合，重要的是要理解旧的位集合 将保留在内存中，直到 GC 释放它 如果内存受限，此函数可能会导致 panic 参数:
- lastbitindex: uint 最后一个可能设置的位的索引
返回值:
- *BitSet: 位集合本身，用于链式调用
func (*BitSet) SymmetricDifference ¶
SymmetricDifference 计算基集合与其他集合的对称差 这是BitSet的^(异或)运算等价操作 参数:
- compare: *BitSet 要计算对称差的位集合
返回值:
- result: *BitSet 对称差结果
func (*BitSet) SymmetricDifferenceCardinality ¶
SymmetricDifferenceCardinality 计算两个位集合对称差的基数(设置为1的位的数量) 参数:
- compare: *BitSet 要计算对称差的位集合
返回值:
- uint: 对称差中设置为1的位的数量
func (*BitSet) Union ¶
Union 计算基集合与其他集合的并集 这是BitSet的|(或)运算等价操作 参数:
- compare: *BitSet 要计算并集的位集合
返回值:
- result: *BitSet 并集结果
func (*BitSet) UnionCardinality ¶
UnionCardinality 计算两个位集合并集的基数(设置为1的位的数量) 参数:
- compare: *BitSet 要计算并集的位集合
返回值:
- uint: 并集中设置为1的位的数量
func (*BitSet) UnmarshalBinary ¶
UnmarshalBinary 解码由 MarshalBinary 生成的二进制形式 详见 WriteTo 方法 参数:
- data: []byte 要解码的二进制数据
返回值:
- error: 如果发生错误则返回,否则返回nil
func (*BitSet) UnmarshalJSON ¶
UnmarshalJSON 从使用 MarshalJSON 创建的 JSON 中解码位集合 参数:
- data: []byte 要解码的 JSON 数据
返回值:
- error: 如果发生错误则返回,否则返回nil
func (*BitSet) WriteTo ¶
WriteTo 将BitSet写入流 格式为: 1. uint64 length 2. []uint64 set length是BitSet中的位数
set是一个uint64切片,包含length到length+63位 默认情况下它被解释为大端序的uint64数组(参见BinaryOrder()) 这意味着前8位存储在字节索引7,接下来的8位存储在字节索引6... 位64到71存储在字节索引8,依此类推 如果你改变二进制顺序,需要同时改变读写操作 我们建议使用默认的二进制顺序
成功时返回写入的字节数
性能提示:如果此函数用于写入磁盘或网络连接, 使用bufio.Writer包装流可能会有益处 例如:
f, err := os.Create("myfile")
w := bufio.NewWriter(f)
参数:
- stream: io.Writer 写入目标流
返回值:
- int64: 写入的字节数
- error: 如果发生错误则返回,否则返回nil
Source Files