README
¶
fibvec
Package fibvec implements a vector that can store unsigned integers by first converting them to their fibonacci encoded values before saving to a bit array. This can save memory space (especially for small values) in exchange for slower operations.
This implements Random access to Fibonacci coded sequences described in Simple Random Access Compression by Kimmo Fredriksson and Fedor Nikitin with auxilliary structure to support fast select operations from Fast, Small, Simple Rank/Select on Bitmaps. The encoding algorithm was taken from Fast Fibonacci Encoding Algorithm and the decoding algorithm was taken from Fast decoding algorithm for variable-lengths codes and The Fast Fibonacci Decompression Algorithm.
Installation
go get github.com/robskie/fibvec
API Reference
Godoc documentation can be found here.
Benchmarks
These benchmarks are done on a Core i5 at 2.3GHz. You can run these benchmarks
by typing go test github.com/robskie/fibvec -bench=.* from terminal.
BenchmarkFibEnc-4 1000000 1414 ns/op
BenchmarkFibDec-4 3000000 447 ns/op
BenchmarkAdd-4 1000000 1508 ns/op
BenchmarkGet-4 3000000 570 ns/op
Documentation
¶
Overview ¶
Package fibvec provides a vector that can store unsigned integers by first converting them to their fibonacci encoded values before saving to a bit array. This can save memory space (especially for small values) in exchange for slower operations.
Index ¶
Constants ¶
const ( MaxValue = math.MaxInt64 - 3 MinValue = -MaxValue )
Maximum and minimum value that can be encoded.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Vector ¶
type Vector struct {
// contains filtered or unexported fields
}
Vector represents a container for unsigned integers.
Source Files