README
¶
bitset
bitset is a package providing efficient bitset implementations for Go.
Documentation
[
]
(http://godoc.org/github.com/jrick/bitset)
Full go doc style documentation for the project can be viewed online without
installing this package by using the GoDoc site here:
http://godoc.org/github.com/jrick/bitset
You can also view the documentation locally once the package is installed with
the godoc tool by running godoc -http=":6060" and pointing your browser to
http://localhost:6060/pkg/github.com/jrick/bitset
Installation
$ go get github.com/jrick/bitset
License
bitset is licensed under the liberal ISC license.
Documentation
¶
Overview ¶
Package bitset provides bitset implementations for bit packing binary values into pointers and bytes.
A bitset, while logically equivalent to a []bool, is often preferable over a []bool due to the space and time efficiency of bit packing binary values. They are typically more space efficient than a []bool since (although implementation specifc) bools are typically byte size. Using a bitset in place of a []bool can therefore result in at least an 8x reduction in memory usage. While bitsets introduce bitshifting overhead for gets and sets unnecessary for a []bool, they may still more performant than a []bool due to the smaller data structure being more cache friendly.
This package contains three bitset implementations: Pointers for efficiency, Bytes for situations where bitsets must be serialized or deserialized, and Sparse for when memory efficiency is the most important factor when working with sparse datasets.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BitSet ¶
BitSet defines the method set of a bitset. Bitsets allow for bit packing of binary values to pointers or bytes for space and time efficiency.
The Grow methods of Pointers and Bytes are not part of this interface.
type Bytes ¶
type Bytes []byte
Bytes represents a bitset backed by a bytes slice. Bytes bitsets, while designed for efficiency, are slightly less efficient to use than Pointers bitsets, since pointer-sized data is faster to manipulate. However, Bytes have the nice property of easily and portably being (de)serialized to or from an io.Reader or io.Writer. Like a Pointers, Bytes bitsets do not automatically grow for indexed values outside of the allocated range. The Grow method is provided if it is necessary to grow a Bytes bitset beyond its initial allocation.
The len of a Bytes is the number of bytes in the set. Multiplying by eight will result in the number of bits the set can hold.
func NewBytes ¶
NewBytes returns a new bitset that is capable of holding numBits number of binary values. All bytes in the bitset are zeroed and each bit is therefore considered unset.
func (Bytes) Get ¶
Get returns whether the bit at index i is set or not. This method will panic if the index results in a byte index that exceeds the number of bytes held by the bitset.
func (*Bytes) Grow ¶
Grow ensures that the bitset s is large enough to hold numBits number of bits, potentially appending to and/or reallocating the slice if the current length is not sufficient.
func (Bytes) Set ¶
Set sets the bit at index i. This method will panic if the index results in a byte index that exceeds the number of a bytes held by the bitset.
type Pointers ¶
type Pointers []uintptr
Pointers represents a bitset backed by a uintptr slice. Pointers bitsets are designed for efficiency and do not automatically grow for indexed values outside of the allocated range. The Grow method is provided if it is necessary to grow a Pointers bitset beyond its initial allocation.
The len of a Pointers is the number of pointers in the set. Multiplying by the machine pointer size will result in the number of bits the set can hold.
func NewPointers ¶
NewPointers returns a new bitset that is capable of holding numBits number of binary values. All pointers in the bitset are zeroed and each bit is therefore considered unset.
func (Pointers) Get ¶
Get returns whether the bit at index i is set or not. This method will panic if the index results in a pointer index that exceeds the number of pointers held by the bitset.
func (*Pointers) Grow ¶
Grow ensures that the bitset w is large enough to hold numBits number of bits, potentially appending to and/or reallocating the slice if the current length is not sufficient.
func (Pointers) Set ¶
Set sets the bit at index i. This method will panic if the index results in a pointer index that exceeds the number of pointers held by the bitset.
type Sparse ¶
Sparse is a memory efficient bitset for sparsly-distributed set bits. Unlike a Pointers or Bytes which requires each pointer or byte between 0 and the highest index to be allocated, a Sparse only holds the pointers which contain set bits. Additionally, Sparse is the only BitSet implementation from this package which will dynamically expand and shrink as bits are set and unset.
As the map is unordered and there is no obvious way to (de)serialize this structure, no byte implementation is provided, and all map values are machine pointer-sized.
As Sparse bitsets are backed by a map, getting and setting bits are orders of magnitude slower than other slice-backed bitsets and should only be used with sparse datasets and when memory efficiency is a top concern. It is highly recommended to benchmark this type against the other bitsets using realistic sample data before using this type in an application.
New Sparse bitsets can be created using the builtin make function.
func (Sparse) Set ¶
Set sets the bit at index i. A map insert is performed if if no bits of the associated pointer have been previously set.
Source Files