README
¶
gocroaring 
/badge.svg)
Well-tested Go wrapper for CRoaring (a C/C++ implementation of Roaring Bitmaps)
Roaring bitmaps are used by several important systems:
- Apache Lucene and derivative systems such as Solr and Elastic,
- Metamarkets' Druid,
- Apache Spark,
- Netflix Atlas,
- LinkedIn Pinot,
- OpenSearchServer,
- Cloud Torrent,
- Whoosh,
- Pilosa,
- Microsoft Visual Studio Team Services (VSTS),
- eBay's Apache Kylin.
Roaring bitmaps are found to work well in many important applications:
Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods (Wang et al., SIGMOD 2017)
The original java version can be found at https://github.com/RoaringBitmap/RoaringBitmap
There is a native Go version at https://github.com/RoaringBitmap/roaring
This code is licensed under Apache License, Version 2.0 (ASL2.0).
Copyright 2016 by the authors.
Benchmarking
See https://github.com/lemire/gobitmapbenchmark for a comparison between this wrapper and the Go native version.
References
- Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Roaring Bitmaps: Implementation of an Optimized Software Library arXiv:1709.07821
- Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience Volume 46, Issue 5, pages 709–719, May 2016 http://arxiv.org/abs/1402.6407 This paper used data from http://lemire.me/data/realroaring2014.html
- Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience (accepted in 2016, to appear) http://arxiv.org/abs/1603.06549
Dependencies
None in particular.
Naturally, you also need to grab the roaring code itself:
- go get github.com/RoaringBitmap/gocroaring
Example
Here is a simplified but complete example:
package main
import (
"fmt"
"github.com/RoaringBitmap/gocroaring"
)
func main() {
// example inspired by https://github.com/fzandona/goroar
fmt.Println("==roaring==")
rb1 := gocroaring.New(1, 2, 3, 4, 5, 100, 1000)
rb1.RunOptimize() // improves compression
fmt.Println("Cardinality: ", rb1.Cardinality())
fmt.Println("Contains 3? ", rb1.Contains(3))
rb2 := gocroaring.New()
rb2.Add(3, 4, 1000)
rb2.RunOptimize() // improves compression
rb1.And(rb2)
// prints {3,4,1000}
fmt.Println(rb1)
rb3 := gocroaring.New(1, 5)
rb3.Or(rb1)
// prints 1, 3, 4, 5, 1000
i := rb3.Iterator()
for i.HasNext() {
fmt.Println(i.Next())
}
fmt.Println()
fmt.Println(rb3.ToArray())
fmt.Println(rb3)
rb4 := gocroaring.FastOr(rb1, rb2, rb3) // optimized way to compute unions between many bitmaps
fmt.Println(rb4)
// next we include an example of serialization
buf := make([]byte, rb1.SerializedSizeInBytes())
rb1.Write(buf) // we omit error handling
newrb, _ := gocroaring.Read(buf)
if rb1.Equals(newrb) {
fmt.Println("I wrote the content to a byte stream and read it back.")
}
fmt.Println(rb1.Stats()) // show the cardinality and the numbers of each type of container used.
}
Documentation
Current documentation is available at http://godoc.org/github.com/RoaringBitmap/gocroaring
Mailing list/discussion group
https://groups.google.com/forum/#!forum/roaring-bitmaps
Compatibility with Java RoaringBitmap library
You can read bitmaps in Go, Java, C, C++ that have been serialized in Go, Java, C, C++.
Documentation
¶
Overview ¶
Package gocroaring is an wrapper for CRoaring in go It provides a fast compressed bitmap data structure. See http://roaringbitmap.org for details.
Index ¶
- Constants
- type Bitmap
- func And(x1, x2 *Bitmap) *Bitmap
- func AndNot(x1, x2 *Bitmap) *Bitmap
- func FastOr(bitmaps ...*Bitmap) *Bitmap
- func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap
- func New(x ...uint32) *Bitmap
- func Or(x1, x2 *Bitmap) *Bitmap
- func Read(b []byte) (*Bitmap, error)
- func ReadFrozenView(b []byte) (*Bitmap, error)
- func Xor(x1, x2 *Bitmap) *Bitmap
- func (rb *Bitmap) Add(x ...uint32)
- func (rb *Bitmap) AddRange(min, max uint64)
- func (rb *Bitmap) And(x2 *Bitmap)
- func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64
- func (rb *Bitmap) AndNot(x2 *Bitmap)
- func (rb *Bitmap) AndNotCardinality(x2 *Bitmap) uint64
- func (rb *Bitmap) Assign(x2 *Bitmap) bool
- func (rb *Bitmap) Cardinality() uint64
- func (rb *Bitmap) Clear()
- func (rb *Bitmap) Clone() *Bitmap
- func (rb *Bitmap) Contains(x uint32) bool
- func (rb *Bitmap) ContainsRange(x, y uint64) bool
- func (rb *Bitmap) Equals(o interface{}) bool
- func (rb *Bitmap) Flip(rangeStart, rangeEnd uint64)
- func (rb *Bitmap) Free()
- func (rb *Bitmap) FrozenSizeInBytes() int
- func (rb *Bitmap) GetCardinality() uint64
- func (rb *Bitmap) Intersect(x2 *Bitmap) bool
- func (rb *Bitmap) IsEmpty() bool
- func (rb *Bitmap) Iterator() IntIterable
- func (rb *Bitmap) JaccardIndex(x2 *Bitmap) float64
- func (rb *Bitmap) Maximum() uint32
- func (rb *Bitmap) Minimum() uint32
- func (rb *Bitmap) Or(x2 *Bitmap)
- func (rb *Bitmap) OrCardinality(x2 *Bitmap) uint64
- func (rb *Bitmap) Printf()
- func (rb *Bitmap) Rank(x uint32) uint64
- func (rb *Bitmap) Remove(x uint32)
- func (rb *Bitmap) RemoveRange(min, max uint64)
- func (rb *Bitmap) RemoveRunCompression() bool
- func (rb *Bitmap) RunOptimize() bool
- func (rb *Bitmap) Select(rank uint32) (uint32, error)
- func (rb *Bitmap) SerializedSizeInBytes() int
- func (rb *Bitmap) Stats() map[string]uint64
- func (rb *Bitmap) StatsStruct() Statistics
- func (rb *Bitmap) String() string
- func (rb *Bitmap) ToArray() []uint32
- func (rb *Bitmap) Write(b []byte) error
- func (rb *Bitmap) WriteFrozen(b []byte) error
- func (rb *Bitmap) Xor(x2 *Bitmap)
- func (rb *Bitmap) XorCardinality(x2 *Bitmap) uint64
- type IntIterable
- type Statistics
Constants ¶
const CRoaringMajor = C.ROARING_VERSION_MAJOR
const CRoaringMinor = C.ROARING_VERSION_MINOR
const CRoaringRevision = C.ROARING_VERSION_REVISION
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Bitmap ¶
type Bitmap struct {
// contains filtered or unexported fields
}
Bitmap is the roaring bitmap
func And ¶
And computes the intersection between two bitmaps and returns the result This function may panic if the allocation failed.
func AndNot ¶
AndNot computes the difference between two bitmaps and returns the result This function may panic if the allocation failed.
func FastOr ¶
FastOr computes the union between many bitmaps quickly, as opposed to having to call Or repeatedly. It might also be faster than calling Or repeatedly. This function may panic if the allocation failed.
func Flip ¶
Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed. This function may panic if the allocation failed.
func New ¶ added in v0.2.0
New creates a new Bitmap with any number of initial values. This function may panic if the allocation failed.
func Or ¶
Or computes the union between two bitmaps and returns the result This function may panic if the allocation failed.
func Read ¶
Read reads a serialized version of the bitmap (you need to call Free on it once you are done)
func ReadFrozenView ¶ added in v0.2.65
ReadFrozenView reads a frozen serialized version of the bitmap this is immutable and attempting to mutate it will fail catastrophically It keeps a reference to the buffer internally to make sure it's alive for the complete lifetime of the view
func Xor ¶
Xor computes the symmetric difference between two bitmaps and returns the result This function may panic if the allocation failed.
func (*Bitmap) And ¶
And computes the intersection between two bitmaps and stores the result in the current bitmap
func (*Bitmap) AndCardinality ¶ added in v0.2.7
AndCardinality computes the size of the intersection between two bitmaps
func (*Bitmap) AndNot ¶
AndNot computes the difference between two bitmaps and stores the result in the current bitmap
func (*Bitmap) AndNotCardinality ¶ added in v0.2.7
AndNotCardinality computes the size of the difference between two bitmaps
func (*Bitmap) Cardinality ¶ added in v0.2.0
Cardinality returns the number of integers contained in the bitmap
func (*Bitmap) Clear ¶ added in v0.2.9
func (rb *Bitmap) Clear()
Clear removes all elements from the bitmap
func (*Bitmap) Clone ¶
Clone creates a copy of the Bitmap This function may panic if the allocation failed.
func (*Bitmap) ContainsRange ¶ added in v0.3.0
ContainsRange returns true if the integers in the range [x, y) are contained in the bitmap
func (*Bitmap) Flip ¶
Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed.
func (*Bitmap) FrozenSizeInBytes ¶ added in v0.2.65
FrozenSizeInBytes computes the frozen serialized size in bytes
func (*Bitmap) GetCardinality ¶
Cardinality returns the number of integers contained in the bitmap
func (*Bitmap) IsEmpty ¶
IsEmpty returns true if the Bitmap is empty (it is faster than doing (Cardinality() == 0))
func (*Bitmap) Iterator ¶ added in v0.2.3
func (rb *Bitmap) Iterator() IntIterable
Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order
func (*Bitmap) JaccardIndex ¶ added in v0.2.7
JaccardIndex computes the Jaccard index between two bitmaps
func (*Bitmap) Maximum ¶ added in v0.2.4
Maximum returns the largest of the integers contained in the bitmap assuming that it is not empty
func (*Bitmap) Minimum ¶ added in v0.2.4
Minimum returns the smallest of the integers contained in the bitmap assuming that it is not empty
func (*Bitmap) Or ¶
Or computes the union between two bitmaps and stores the result in the current bitmap
func (*Bitmap) OrCardinality ¶ added in v0.2.7
OrCardinality computes the size of the union between two bitmaps
func (*Bitmap) Printf ¶
func (rb *Bitmap) Printf()
Printf writes a description of the bitmap to stdout
func (*Bitmap) RemoveRange ¶ added in v0.3.0
RemoveRange - remove all values in range [min, max)
func (*Bitmap) RemoveRunCompression ¶
RemoveRunCompression Remove run-length encoding even when it is more space efficient return whether a change was applied
func (*Bitmap) RunOptimize ¶
RunOptimize the compression of the bitmap (call this after populating a new bitmap), return true if the bitmap was modified
func (*Bitmap) Select ¶ added in v0.2.4
Select returns the element having the designated rank, if it exists
func (*Bitmap) SerializedSizeInBytes ¶ added in v0.2.0
SerializedSizeInBytes computes the serialized size in bytes the Bitmap.
func (*Bitmap) StatsStruct ¶ added in v0.3.0
func (rb *Bitmap) StatsStruct() Statistics
StatsStruct - same as Stats but returns typed struct. See https://github.com/RoaringBitmap/roaring/pull/73 for rationale
func (*Bitmap) ToArray ¶
ToArray creates a new slice containing all of the integers stored in the Bitmap in sorted order
func (*Bitmap) Write ¶
Write writes a serialized version of this bitmap to stream (you should have enough space)
func (*Bitmap) WriteFrozen ¶ added in v0.2.65
WriteFrozen writes a serialized version of bitmap to the stream in the Frozen format
func (*Bitmap) Xor ¶
Xor computes the symmetric difference between two bitmaps and stores the result in the current bitmap
func (*Bitmap) XorCardinality ¶ added in v0.2.7
XorCardinality computes the size of the symmetric difference between two bitmaps
type IntIterable ¶ added in v0.2.3
IntIterable allows you to iterate over the values in a Bitmap
Source Files
Directories