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.
go get github.com/robskie/fibvecGodoc documentation can be found here.
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