README
¶
b-digest 
B-digest is a Go library for fast and memory-efficient estimation of quantiles with guaranteed relative error and full mergeability.
package bdigest_test
import (
"fmt"
"math"
"math/rand"
"pgregory.net/bdigest"
)
func ExampleNewDigest() {
r := rand.New(rand.NewSource(0))
d := bdigest.NewDigest(0.05)
for i := 0; i < 100000; i++ {
v := math.Exp(r.NormFloat64())
d.Add(v)
}
fmt.Printf("%v buckets\n", d.Size())
for _, q := range []float64{0, 0.1, 0.25, 0.5, 0.75, 0.9, 0.95, 0.99, 0.999, 0.9999, 1} {
fmt.Printf("%v\tq%v\n", d.Quantile(q), q)
}
// Output:
// 98 buckets
// 0.015690260723105844 q0
// 0.2858480802952493 q0.1
// 0.5211100423907477 q0.25
// 1.05 q0.5
// 1.9141830301785612 q0.75
// 3.489615879070075 q0.9
// 5.2076333497857386 q0.95
// 10.493014090054524 q0.99
// 21.142683691165157 q0.999
// 42.601017193748824 q0.9999
// 258.10858921508054 q1
}
License
B-digest is licensed under the Apache License Version 2.0.
Documentation
¶
Overview ¶
Package bdigest provides tools for fast and memory-efficient estimation of quantiles with guaranteed relative error and full mergeability.
Index ¶
- type Digest
- func (d *Digest) Add(v float64)
- func (d *Digest) Count() uint64
- func (d *Digest) MarshalBinary() ([]byte, error)
- func (d *Digest) Merge(v *Digest) error
- func (d *Digest) Quantile(q float64) float64
- func (d *Digest) Reset()
- func (d *Digest) Size() int
- func (d *Digest) String() string
- func (d *Digest) UnmarshalBinary(data []byte) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Digest ¶
type Digest struct {
// contains filtered or unexported fields
}
Digest tracks distribution of values using histograms with exponentially sized buckets.
func NewDigest ¶
NewDigest returns digest suitable for calculating quantiles of finite non-negative values with maximum relative error err ∈ (0, 1).
Size of digest is proportional to the logarithm of minimum and maximum of the values added. Size of digest is inversely proportional to the relative error. That is, digest with 2% relative error is twice as small as digest with 1% relative error.
Example ¶
package main
import (
"fmt"
"math"
"math/rand"
"pgregory.net/bdigest"
)
func main() {
r := rand.New(rand.NewSource(0))
d := bdigest.NewDigest(0.05)
for i := 0; i < 100000; i++ {
v := math.Exp(r.NormFloat64())
d.Add(v)
}
fmt.Printf("%v buckets\n", d.Size())
for _, q := range []float64{0, 0.1, 0.25, 0.5, 0.75, 0.9, 0.95, 0.99, 0.999, 0.9999, 1} {
fmt.Printf("%v\tq%v\n", d.Quantile(q), q)
}
}
Output: 98 buckets 0.015690260723105844 q0 0.2858480802952493 q0.1 0.5211100423907477 q0.25 1.05 q0.5 1.9141830301785612 q0.75 3.489615879070075 q0.9 5.2076333497857386 q0.95 10.493014090054524 q0.99 21.142683691165157 q0.999 42.601017193748824 q0.9999 258.10858921508054 q1
func (*Digest) Add ¶
Add adds finite non-negative value v to the digest.
Add panics if v is outside [0, math.MaxFloat64].
func (*Digest) MarshalBinary ¶ added in v0.2.1
MarshalBinary implements the encoding.BinaryMarshaler interface.
func (*Digest) Merge ¶
Merge merges the content of v into the digest. Merge preserves relative error guarantees of Quantile.
Merge returns an error if digests have different relative errors.
func (*Digest) Quantile ¶
Quantile returns the q-quantile of added values with a maximum relative error of err.
Quantile panics if q is outside [0, 1]. Quantile returns NaN for empty digest.
func (*Digest) Reset ¶ added in v0.3.0
func (d *Digest) Reset()
Reset resets digest to the initial empty state.
func (*Digest) UnmarshalBinary ¶ added in v0.2.1
UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
Source Files