README

b-digest GoDoc CI

b-digest is a 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.01)

	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:
	// 486 buckets
	// 0.016404706383449263	q0
	// 0.2808056914403475	q0.1
	// 0.5116715635730887	q0.25
	// 1.01	q0.5
	// 1.993661701417351	q0.75
	// 3.6327611266266073	q0.9
	// 5.207005866310038	q0.95
	// 10.278225915562174	q0.99
	// 21.978242872649467	q0.999
	// 42.5242714134434	q0.9999
	// 267.7721258158505	q1
}
Expand ▾ Collapse ▴

Documentation

Overview

    Package bdigest provides tools for fast and memory-efficient estimation of quantiles with guaranteed relative error and full mergeability.

    Index

    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

      func NewDigest(err float64) *Digest

        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
        Output:
        
        486 buckets
        0.016404706383449263	q0
        0.2808056914403475	q0.1
        0.5116715635730887	q0.25
        1.01	q0.5
        1.993661701417351	q0.75
        3.6327611266266073	q0.9
        5.207005866310038	q0.95
        10.278225915562174	q0.99
        21.978242872649467	q0.999
        42.5242714134434	q0.9999
        267.7721258158505	q1
        

        func (*Digest) Add

        func (d *Digest) Add(v float64)

          Add adds finite non-negative value v to the digest.

          Add panics if v is outside [0, math.MaxFloat64].

          func (*Digest) Count

          func (d *Digest) Count() uint64

            Count returns the number of added values.

            func (*Digest) MarshalBinary

            func (d *Digest) MarshalBinary() ([]byte, error)

              MarshalBinary implements the encoding.BinaryMarshaler interface.

              func (*Digest) Merge

              func (d *Digest) Merge(v *Digest) error

                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

                func (d *Digest) Quantile(q float64) float64

                  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

                  func (d *Digest) Reset()

                    Reset resets digest to the initial empty state.

                    func (*Digest) Size

                    func (d *Digest) Size() int

                      Size returns the number of histogram buckets.

                      func (*Digest) String

                      func (d *Digest) String() string

                      func (*Digest) UnmarshalBinary

                      func (d *Digest) UnmarshalBinary(data []byte) error

                        UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.

                        Source Files