README
¶
ranksel
Package ranksel provides a bit vector that can answer rank and select queries. More specifically, it implements the data structure described by G. Navarro and E. Providel's A Structure for Plain Bitmaps: Combined Sampling in Fast, Small, Simple Rank/Select on Bitmaps with some minor modifications.
Installation
go get github.com/robskie/ranksel
API Reference
Godoc documentation can be found here.
Benchmarks
All these benchmarks are done on a machine with a Core i5 running at 2.3GHz. Note that Select0 is slower than Select1 in most cases. This is because the implementation of Select1 is more optimized than Select0. The only case where Select0 is faster than Select1 is when the bit density is lower than 3% as shown from BenchmarkSelectDX where X is the bit density. Another thing to point out is that Select1 starts to slow down when the bit density gets lower than 3%. So you might want to use another data structure if you have a sparse bitmap and you want a fast Select1 operation.
You can run these benchmarks by typing
go test github.com/robskie/ranksel -bench=.* from terminal.
BenchmarkRank1 10000000 160 ns/op
BenchmarkRank0 10000000 170 ns/op
BenchmarkSelect1 5000000 253 ns/op
BenchmarkSelect0 3000000 427 ns/op
BenchmarkSelect1D3 5000000 261 ns/op
BenchmarkSelect0D3 10000000 207 ns/op
BenchmarkSelect1D2 5000000 336 ns/op
BenchmarkSelect0D2 10000000 195 ns/op
BenchmarkSelect1D1 3000000 561 ns/op
BenchmarkSelect0D1 10000000 214 ns/op
Documentation
¶
Overview ¶
Package ranksel provides a bit vector that can answer rank and select queries.
Index ¶
- type BitVector
- func (v *BitVector) Add(bits uint64, size int)
- func (v *BitVector) Bit(i int) uint
- func (v *BitVector) Get(idx, size int) uint64
- func (v *BitVector) GobDecode(data []byte) error
- func (v *BitVector) GobEncode() ([]byte, error)
- func (v *BitVector) Len() int
- func (v *BitVector) PopCount() int
- func (v *BitVector) Rank0(i int) int
- func (v *BitVector) Rank1(i int) int
- func (v *BitVector) Select0(i int) int
- func (v *BitVector) Select1(i int) int
- func (v *BitVector) Size() int
- func (v *BitVector) String() string
- type Options
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BitVector ¶
type BitVector struct {
// contains filtered or unexported fields
}
BitVector is a bitmap with added data structure described by G. Navarro and E. Providel's `A Structure for Plain Bitmaps: Combined Sampling` in "Fast, Small, Simple Rank/Select on Bitmaps" with some minor modifications.
See http://dcc.uchile.cl/~gnavarro/ps/sea12.1.pdf for more details.
func NewBitVector ¶
NewBitVector creates a new BitVector.
func (*BitVector) Get ¶
Get returns the uint64 representation of bits starting from index idx given the bit size.
func (*BitVector) Select0 ¶
Select0 returns the index of the ith zero. Panics if i is zero or greater than the number of zeroes. This is slower than Select1 in most cases.
type Options ¶
type Options struct {
// Sr is the rank sampling block size.
// This represents the number of bits in
// each rank sampling block. Default is 1024.
Sr int
// Ss is the select sampling block size.
// This represents the number of 1s in each
// select sampling block. Default is 8192.
Ss int
}
Options determines the size of the rank and select sampling block. Lower values translates to faster operations but results in larger size.
func NewOptions ¶
func NewOptions() *Options
NewOptions creates an Options object with default values.
Source Files