README
¶
tdigest
This is an implementation of Ted Dunning's t-digest in Go.
The implementation is based off Derrick Burns' C++ implementation.
Example
package main
import (
"log"
"github.com/influxdata/tdigest"
)
func main() {
td := tdigest.NewWithCompression(1000)
for _, x := range []float64{1, 2, 3, 4, 5, 5, 4, 3, 2, 1} {
td.Add(x, 1)
}
// Compute Quantiles
log.Println("50th", td.Quantile(0.5))
log.Println("75th", td.Quantile(0.75))
log.Println("90th", td.Quantile(0.9))
log.Println("99th", td.Quantile(0.99))
// Compute CDFs
log.Println("CDF(1) = ", td.CDF(1))
log.Println("CDF(2) = ", td.CDF(2))
log.Println("CDF(3) = ", td.CDF(3))
log.Println("CDF(4) = ", td.CDF(4))
log.Println("CDF(5) = ", td.CDF(5))
}
TODO
Only the methods for a single TDigest have been implemented. The methods to merge two or more existing t-digests into a single t-digest have yet to be implemented.
Documentation
¶
Index ¶
- Constants
- type Centroid
- type CentroidList
- type Error
- type TDigest
- func (t *TDigest) Add(x, w float64)
- func (t *TDigest) AddCentroid(c Centroid)
- func (t *TDigest) AddCentroidList(c CentroidList)
- func (t *TDigest) CDF(x float64) float64
- func (t *TDigest) Centroids() CentroidList
- func (t *TDigest) Count() float64
- func (t *TDigest) Quantile(q float64) float64
- func (t *TDigest) Reset()
Constants ¶
const ErrWeightLessThanZero = Error("centroid weight cannot be less than zero")
ErrWeightLessThanZero is used when the weight is not able to be processed.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Centroid ¶
type Centroid struct {
Mean float64
Weight float64
}
Centroid average position of all points in a shape
type CentroidList ¶
type CentroidList []Centroid
CentroidList is sorted by the Mean of the centroid, ascending.
func NewCentroidList ¶
func NewCentroidList(centroids []Centroid) CentroidList
NewCentroidList creates a priority queue for the centroids
type TDigest ¶
type TDigest struct {
Compression float64
// contains filtered or unexported fields
}
TDigest is a data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means.
func NewWithCompression ¶
func NewWithCompression(c float64) *TDigest
NewWithCompression initializes a new distribution with custom compression.
func (*TDigest) Add ¶
func (t *TDigest) Add(x, w float64)
Add adds a value x with a weight w to the distribution.
func (*TDigest) AddCentroid ¶
func (t *TDigest) AddCentroid(c Centroid)
AddCentroid adds a single centroid.
func (*TDigest) AddCentroidList ¶
func (t *TDigest) AddCentroidList(c CentroidList)
AddCentroidList can quickly add multiple centroids.
func (*TDigest) CDF ¶
func (t *TDigest) CDF(x float64) float64
CDF returns the cumulative distribution function for a given value x.
func (*TDigest) Centroids ¶
func (t *TDigest) Centroids() CentroidList
Centroids returns a copy of processed centroids. Useful when aggregating multiple t-digests.
Pass in the CentroidList as the buffer to write into.
Source Files
Directories