Summarize Percentiles with a Fixed Histogram

package main

import (
	"fmt"
	"math"
)

type Histogram struct {
	min    float64
	max    float64
	counts []int
	total  int
}

func NewHistogram(minimum, maximum float64, buckets int) *Histogram {
	if buckets <= 0 || maximum <= minimum {
		panic("invalid histogram bounds")
	}
	return &Histogram{
		min:    minimum,
		max:    maximum,
		counts: make([]int, buckets),
	}
}

func (histogram *Histogram) Observe(value float64) {
	if value < histogram.min {
		value = histogram.min
	}
	if value > histogram.max {
		value = histogram.max
	}
	width := (histogram.max - histogram.min) / float64(len(histogram.counts))
	index := int((value - histogram.min) / width)
	if index == len(histogram.counts) {
		index--
	}
	histogram.counts[index]++
	histogram.total++
}

func (histogram *Histogram) Percentile(percentile float64) float64 {
	if histogram.total == 0 {
		return math.NaN()
	}
	rank := int(math.Ceil(percentile / 100 * float64(histogram.total)))
	if rank < 1 {
		rank = 1
	}
	seen := 0
	width := (histogram.max - histogram.min) / float64(len(histogram.counts))
	for index, count := range histogram.counts {
		if seen+count >= rank {
			within := float64(rank-seen) / float64(count)
			return histogram.min + (float64(index)+within)*width
		}
		seen += count
	}
	return histogram.max
}

func main() {
	histogram := NewHistogram(0, 1000, 10)
	for _, value := range []float64{10, 20, 30, 40, 50, 60, 70, 80, 90, 1000} {
		histogram.Observe(value)
	}
	p50 := histogram.Percentile(50)
	p90 := histogram.Percentile(90)
	p99 := histogram.Percentile(99)
	fmt.Printf("p50=%.0f p90=%.0f p99=%.0f\n", p50, p90, p99)
	if !(p50 < p90 && p90 < p99) || p99 != 1000 {
		panic("unexpected percentile estimates")
	}
}