A map-reduce and parallel streaming friendly data-structure for accurate quantile approximation.
This package provides a very crude implementation of Ted Dunning's t-digest data structure in Go.
go get github.com/caio/go-tdigest
package main
import (
"fmt"
"math/rand"
"github.com/caio/go-tdigest"
)
func main() {
var t = tdigest.New(100)
for i := 0; i < 10000; i++ {
t.Add(rand.Float64(), 1)
}
fmt.Printf("p(.5) = %.6f\n", t.Quantile(0.5))
}
I've written this solely with the purpose of understanding how the data-structure works, it hasn't been throughly verified nor battle tested in a production environment.
This is a very simple port of the reference implementation with some ideas borrowed from the python version. If you wanna get a quick grasp of how it works and why it's useful, this video and companion article is pretty helpful.