tdigest

package
v13.2.0+incompatible Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 1, 2020 License: MIT Imports: 11 Imported by: 30

Documentation

Overview

Package tdigest provides an implementation of Ted Dunning's t-digest, an approximate histogram for online, distributed applications. For more details, refer to Dunning's paper and the reference implementations.

https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf

https://github.com/tdunning/t-digest/blob/master/src/main/java/com/tdunning/math/stats/

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrInvalidLengthTdigest = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowTdigest   = fmt.Errorf("proto: integer overflow")
)

Functions

This section is empty.

Types

type Centroid 

type Centroid struct {
	Mean    float64   `protobuf:"fixed64,1,opt,name=mean,proto3" json:"mean,omitempty"`
	Weight  float64   `protobuf:"fixed64,2,opt,name=weight,proto3" json:"weight,omitempty"`
	Samples []float64 `protobuf:"fixed64,3,rep,packed,name=samples,proto3" json:"samples,omitempty"`
}

func (*Centroid) Descriptor added in v1.9.0 

func (*Centroid) Descriptor() ([]byte, []int)

func (*Centroid) GetMean added in v1.9.0 

func (m *Centroid) GetMean() float64

func (*Centroid) GetSamples added in v1.9.0 

func (m *Centroid) GetSamples() []float64

func (*Centroid) GetWeight added in v1.9.0 

func (m *Centroid) GetWeight() float64

func (*Centroid) Marshal added in v1.9.0 

func (m *Centroid) Marshal() (dAtA []byte, err error)

func (*Centroid) MarshalTo added in v1.9.0 

func (m *Centroid) MarshalTo(dAtA []byte) (int, error)

func (*Centroid) ProtoMessage added in v1.9.0 

func (*Centroid) ProtoMessage()

func (*Centroid) Reset added in v1.9.0 

func (m *Centroid) Reset()

func (*Centroid) Size added in v1.9.0 

func (m *Centroid) Size() (n int)

func (*Centroid) String added in v1.9.0 

func (m *Centroid) String() string

func (*Centroid) Unmarshal added in v1.9.0 

func (m *Centroid) Unmarshal(dAtA []byte) error

func (*Centroid) XXX_DiscardUnknown 

func (m *Centroid) XXX_DiscardUnknown()

func (*Centroid) XXX_Marshal 

func (m *Centroid) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Centroid) XXX_Merge 

func (m *Centroid) XXX_Merge(src proto.Message)

func (*Centroid) XXX_Size 

func (m *Centroid) XXX_Size() int

func (*Centroid) XXX_Unmarshal 

func (m *Centroid) XXX_Unmarshal(b []byte) error

type MergingDigest 

type MergingDigest struct {
	// contains filtered or unexported fields
}

A t-digest using the merging implementation. MergingDigest is not safe for use by multiple goroutines simultaneously, and its methods must not be invoked concurrently (including Quantile and CDF).

func NewMerging 

func NewMerging(compression float64, debug bool) *MergingDigest

Initializes a new merging t-digest using the given compression parameter. Lower compression values result in reduced memory consumption and less precision, especially at the median. Values from 20 to 1000 are recommended in Dunning's paper.

The debug flag adds a list to each centroid, which stores all the samples that have gone into that centroid. While this is useful for statistical analysis, it makes the t-digest significantly slower and requires it to store every sample. This defeats the purpose of using an approximating histogram at all, so this feature should only be used in tests.

func NewMergingFromData added in v1.9.0 

func NewMergingFromData(d *MergingDigestData) *MergingDigest

NewMergingFromData returns a MergingDigest with values initialized from MergingDigestData. This should be the way to generate a MergingDigest from a serialized protobuf.

func (*MergingDigest) Add 

func (td *MergingDigest) Add(value float64, weight float64)

Adds a new value to the t-digest, with a given weight that must be positive. Infinities and NaN cannot be added.

func (*MergingDigest) CDF 

func (td *MergingDigest) CDF(value float64) float64

Returns the approximate percentage of values in td that are below value (ie the cumulative distribution function). Returns NaN if the digest is empty.

func (*MergingDigest) Centroids 

func (td *MergingDigest) Centroids() []Centroid

This function provides direct access to the internal list of centroids in this t-digest. Having access to this list is very important for analyzing the t-digest's statistical properties. However, since it violates the encapsulation of the t-digest, it should be used sparingly. Mutating the returned slice can result in undefined behavior.

This function will panic if debug is not enabled for this t-digest.

func (*MergingDigest) Count 

func (td *MergingDigest) Count() float64

func (*MergingDigest) Data added in v1.9.0 

func (td *MergingDigest) Data() *MergingDigestData

Data returns a MergingDigestData based on the MergingDigest (which contains just a subset of the fields). This can be used with proto.Marshal to encode a MergingDigest as a protobuf.

func (*MergingDigest) GobDecode 

func (td *MergingDigest) GobDecode(b []byte) error

func (*MergingDigest) GobEncode 

func (td *MergingDigest) GobEncode() ([]byte, error)

func (*MergingDigest) Max 

func (td *MergingDigest) Max() float64

func (*MergingDigest) Merge 

func (td *MergingDigest) Merge(other *MergingDigest)

Merge another digest into this one. Neither td nor other can be shared concurrently during the execution of this method.

func (*MergingDigest) Min 

func (td *MergingDigest) Min() float64

func (*MergingDigest) Quantile 

func (td *MergingDigest) Quantile(quantile float64) float64

Returns a value such that the fraction of values in td below that value is approximately equal to quantile. Returns NaN if the digest is empty.

func (*MergingDigest) ReciprocalSum added in v1.9.0 

func (td *MergingDigest) ReciprocalSum() float64

func (*MergingDigest) Sum added in v1.9.0 

func (td *MergingDigest) Sum() float64

type MergingDigestData added in v1.9.0 

type MergingDigestData struct {
	// Use values rather than pointers for the Centroid array.  This avoids
	// a ton of code changes and probably a lot of allocations as well.
	MainCentroids []Centroid `protobuf:"bytes,1,rep,name=main_centroids,json=mainCentroids,proto3" json:"main_centroids"`
	Compression   float64    `protobuf:"fixed64,2,opt,name=compression,proto3" json:"compression,omitempty"`
	Min           float64    `protobuf:"fixed64,3,opt,name=min,proto3" json:"min,omitempty"`
	Max           float64    `protobuf:"fixed64,4,opt,name=max,proto3" json:"max,omitempty"`
	ReciprocalSum float64    `protobuf:"fixed64,5,opt,name=reciprocalSum,proto3" json:"reciprocalSum,omitempty"`
}

MergingDigestData contains all fields necessary to generate a MergingDigest. This type should generally just be used when serializing MergingDigest's, and doesn't have much of a purpose on its own.

func (*MergingDigestData) Descriptor added in v1.9.0 

func (*MergingDigestData) Descriptor() ([]byte, []int)

func (*MergingDigestData) GetCompression added in v1.9.0 

func (m *MergingDigestData) GetCompression() float64

func (*MergingDigestData) GetMainCentroids added in v1.9.0 

func (m *MergingDigestData) GetMainCentroids() []Centroid

func (*MergingDigestData) GetMax added in v1.9.0 

func (m *MergingDigestData) GetMax() float64

func (*MergingDigestData) GetMin added in v1.9.0 

func (m *MergingDigestData) GetMin() float64

func (*MergingDigestData) GetReciprocalSum added in v1.9.0 

func (m *MergingDigestData) GetReciprocalSum() float64

func (*MergingDigestData) Marshal added in v1.9.0 

func (m *MergingDigestData) Marshal() (dAtA []byte, err error)

func (*MergingDigestData) MarshalTo added in v1.9.0 

func (m *MergingDigestData) MarshalTo(dAtA []byte) (int, error)

func (*MergingDigestData) ProtoMessage added in v1.9.0 

func (*MergingDigestData) ProtoMessage()

func (*MergingDigestData) Reset added in v1.9.0 

func (m *MergingDigestData) Reset()

func (*MergingDigestData) Size added in v1.9.0 

func (m *MergingDigestData) Size() (n int)

func (*MergingDigestData) String added in v1.9.0 

func (m *MergingDigestData) String() string

func (*MergingDigestData) Unmarshal added in v1.9.0 

func (m *MergingDigestData) Unmarshal(dAtA []byte) error

func (*MergingDigestData) XXX_DiscardUnknown 

func (m *MergingDigestData) XXX_DiscardUnknown()

func (*MergingDigestData) XXX_Marshal 

func (m *MergingDigestData) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*MergingDigestData) XXX_Merge 

func (m *MergingDigestData) XXX_Merge(src proto.Message)

func (*MergingDigestData) XXX_Size 

func (m *MergingDigestData) XXX_Size() int

func (*MergingDigestData) XXX_Unmarshal 

func (m *MergingDigestData) XXX_Unmarshal(b []byte) error

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.