Documentation
¶
Overview ¶
Package gohll counts distinct items approximately with HyperLogLog.
A Sketch keeps m = 2^14 one-byte registers (16 KiB, eight to a 64-bit word for lock-free updates) whatever the number of items, and estimates their cardinality with a standard error of 1.04/sqrt(m) ≈ 0.8%. Items are added as 64-bit hashes: the top 14 bits pick a register, the register keeps the longest run of leading zeros seen in the rest, plus one.
The estimate is the LogLog-Beta one (Qin, Kim, Tung, Wang, 2016): a single formula with a per-precision polynomial correction that covers the whole range, from a handful of items to billions, with the accuracy of the HyperLogLog++ bias tables and without its switch between estimators.
Add is lock-free (a compare-and-swap max on the register's word) and allocates nothing; Count walks the registers; Merge takes the union of two sketches; Reset starts over.
Index ¶
- Variables
- type Sketch
- func (s *Sketch) Add(hash uint64)
- func (s *Sketch) AppendBinary(data []byte) ([]byte, error)
- func (s *Sketch) Count() uint64
- func (s *Sketch) Empty() bool
- func (s *Sketch) MarshalBinary() ([]byte, error)
- func (s *Sketch) Merge(other *Sketch)
- func (s *Sketch) Reset()
- func (s *Sketch) UnmarshalBinary(data []byte) error
Constants ¶
This section is empty.
Variables ¶
var ( // ErrEncoding is wrapped by UnmarshalBinary for data it cannot read. ErrEncoding = errors.New("gohll: invalid encoding") // ErrSparseEncoding is wrapped by UnmarshalBinary for an axiomhq sketch in // its sparse representation. ErrSparseEncoding = errors.New("gohll: sparse encoding is not supported") )
Functions ¶
This section is empty.
Types ¶
type Sketch ¶
type Sketch struct {
// contains filtered or unexported fields
}
Sketch is a HyperLogLog counter. The zero value is ready to use.
func (*Sketch) Add ¶
Add records one item given by its 64-bit hash. The hash must spread well over all bits (xxhash, MetroHash...): the sketch does not hash again.
Sketches that are merged or restored with UnmarshalBinary must have been fed the same hash function with the same seed. hash/maphash seeds are random per process and cannot be saved, so maphash suits sketches that never leave the process; across processes use a stable hash.
func (*Sketch) AppendBinary ¶
AppendBinary appends the encoding of the sketch to data. Registers are read one by one, so Adds running concurrently may or may not be included.
func (*Sketch) MarshalBinary ¶
MarshalBinary encodes the sketch; see the package's encoding note.
func (*Sketch) Merge ¶
Merge adds every item of other to s: the union of the two sets, exact in the sense that it is the sketch the union would have produced. Both must have been fed the same hash function with the same seed (see Add). other is only read; s may be in use by concurrent Adds.
func (*Sketch) Reset ¶
func (s *Sketch) Reset()
Reset forgets every item. It is not atomic with respect to concurrent Adds: an Add racing with Reset may land before or after it.
func (*Sketch) UnmarshalBinary ¶
UnmarshalBinary replaces the sketch's registers with the encoded ones. It is not atomic with respect to concurrent Adds, like Reset.