vendor: use VividCortex/gohistogram instead

6 files changed, 474 insertions, 0 deletions

diff --git a/vendor/github.com/VividCortex/gohistogram/.gitignore b/vendor/github.com/VividCortex/gohistogram/.gitignore
new file mode 100644
index 000000000..4c51178c9
--- /dev/null
+++ b/vendor/github.com/VividCortex/gohistogram/.gitignore
@@ -0,0 +1,2 @@
+\#*
+.\#*
\ No newline at end of file
diff --git a/vendor/github.com/VividCortex/gohistogram/LICENSE b/vendor/github.com/VividCortex/gohistogram/LICENSE
new file mode 100644
index 000000000..d23fea365
--- /dev/null
+++ b/vendor/github.com/VividCortex/gohistogram/LICENSE
@@ -0,0 +1,19 @@
+Copyright (c) 2013 VividCortex
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/vendor/github.com/VividCortex/gohistogram/README.md b/vendor/github.com/VividCortex/gohistogram/README.md
new file mode 100644
index 000000000..eeb14d366
--- /dev/null
+++ b/vendor/github.com/VividCortex/gohistogram/README.md
@@ -0,0 +1,80 @@
+# gohistogram - Histograms in Go
+
+![build status](https://circleci.com/gh/VividCortex/gohistogram.png?circle-token=d37ec652ea117165cd1b342400a801438f575209)
+
+This package provides [Streaming Approximate Histograms](https://vividcortex.com/blog/2013/07/08/streaming-approximate-histograms/)
+for efficient quantile approximations.
+
+The histograms in this package are based on the algorithms found in
+Ben-Haim & Yom-Tov's *A Streaming Parallel Decision Tree Algorithm*
+([PDF](http://jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf)).
+Histogram bins do not have a preset size. As values stream into
+the histogram, bins are dynamically added and merged.
+
+Another implementation can be found in the Apache Hive project (see
+[NumericHistogram](http://hive.apache.org/docs/r0.11.0/api/org/apache/hadoop/hive/ql/udf/generic/NumericHistogram.html)).
+
+An example:
+
+![histogram](http://i.imgur.com/5OplaRs.png)
+
+The accurate method of calculating quantiles (like percentiles) requires
+data to be sorted. Streaming histograms make it possible to approximate
+quantiles without sorting (or even individually storing) values.
+
+NumericHistogram is the more basic implementation of a streaming
+histogram. WeightedHistogram implements bin values as exponentially-weighted
+moving averages.
+
+A maximum bin size is passed as an argument to the constructor methods. A
+larger bin size yields more accurate approximations at the cost of increased
+memory utilization and performance.
+
+A picture of kittens:
+
+![stack of kittens](http://i.imgur.com/QxRTWAE.jpg)
+
+## Getting started
+
+### Using in your own code
+
+    $ go get github.com/VividCortex/gohistogram
+    
+```go
+import "github.com/VividCortex/gohistogram"
+```
+
+### Running tests and making modifications
+
+Get the code into your workspace:
+
+    $ cd $GOPATH
+    $ git clone git@github.com:VividCortex/gohistogram.git ./src/github.com/VividCortex/gohistogram
+
+You can run the tests now:
+
+    $ cd src/github.com/VividCortex/gohistogram
+    $ go test .
+
+## API Documentation
+
+Full source documentation can be found [here][godoc].
+
+[godoc]: http://godoc.org/github.com/VividCortex/gohistogram
+
+## Contributing
+
+We only accept pull requests for minor fixes or improvements. This includes:
+
+* Small bug fixes
+* Typos
+* Documentation or comments
+
+Please open issues to discuss new features. Pull requests for new features will be rejected,
+so we recommend forking the repository and making changes in your fork for your use case.
+
+## License
+
+Copyright (c) 2013 VividCortex
+
+Released under MIT License. Check `LICENSE` file for details.
diff --git a/vendor/github.com/VividCortex/gohistogram/histogram.go b/vendor/github.com/VividCortex/gohistogram/histogram.go
new file mode 100644
index 000000000..ede21fd31
--- /dev/null
+++ b/vendor/github.com/VividCortex/gohistogram/histogram.go
@@ -0,0 +1,23 @@
+package gohistogram
+
+// Copyright (c) 2013 VividCortex, Inc. All rights reserved.
+// Please see the LICENSE file for applicable license terms.
+
+// Histogram is the interface that wraps the Add and Quantile methods.
+type Histogram interface {
+	// Add adds a new value, n, to the histogram. Trimming is done
+	// automatically.
+	Add(n float64)
+
+	// Quantile returns an approximation.
+	Quantile(n float64) (q float64)
+
+	// String returns a string reprentation of the histogram,
+	// which is useful for printing to a terminal.
+	String() (str string)
+}
+
+type bin struct {
+	value float64
+	count float64
+}
diff --git a/vendor/github.com/VividCortex/gohistogram/numerichistogram.go b/vendor/github.com/VividCortex/gohistogram/numerichistogram.go
new file mode 100644
index 000000000..20dea740d
--- /dev/null
+++ b/vendor/github.com/VividCortex/gohistogram/numerichistogram.go
@@ -0,0 +1,160 @@
+package gohistogram
+
+// Copyright (c) 2013 VividCortex, Inc. All rights reserved.
+// Please see the LICENSE file for applicable license terms.
+
+import (
+	"fmt"
+)
+
+type NumericHistogram struct {
+	bins    []bin
+	maxbins int
+	total   uint64
+}
+
+// NewHistogram returns a new NumericHistogram with a maximum of n bins.
+//
+// There is no "optimal" bin count, but somewhere between 20 and 80 bins
+// should be sufficient.
+func NewHistogram(n int) *NumericHistogram {
+	return &NumericHistogram{
+		bins:    make([]bin, 0),
+		maxbins: n,
+		total:   0,
+	}
+}
+
+func (h *NumericHistogram) Add(n float64) {
+	defer h.trim()
+	h.total++
+	for i := range h.bins {
+		if h.bins[i].value == n {
+			h.bins[i].count++
+			return
+		}
+
+		if h.bins[i].value > n {
+
+			newbin := bin{value: n, count: 1}
+			head := append(make([]bin, 0), h.bins[0:i]...)
+
+			head = append(head, newbin)
+			tail := h.bins[i:]
+			h.bins = append(head, tail...)
+			return
+		}
+	}
+
+	h.bins = append(h.bins, bin{count: 1, value: n})
+}
+
+func (h *NumericHistogram) Quantile(q float64) float64 {
+	count := q * float64(h.total)
+	for i := range h.bins {
+		count -= float64(h.bins[i].count)
+
+		if count <= 0 {
+			return h.bins[i].value
+		}
+	}
+
+	return -1
+}
+
+// CDF returns the value of the cumulative distribution function
+// at x
+func (h *NumericHistogram) CDF(x float64) float64 {
+	count := 0.0
+	for i := range h.bins {
+		if h.bins[i].value <= x {
+			count += float64(h.bins[i].count)
+		}
+	}
+
+	return count / float64(h.total)
+}
+
+// Mean returns the sample mean of the distribution
+func (h *NumericHistogram) Mean() float64 {
+	if h.total == 0 {
+		return 0
+	}
+
+	sum := 0.0
+
+	for i := range h.bins {
+		sum += h.bins[i].value * h.bins[i].count
+	}
+
+	return sum / float64(h.total)
+}
+
+// Variance returns the variance of the distribution
+func (h *NumericHistogram) Variance() float64 {
+	if h.total == 0 {
+		return 0
+	}
+
+	sum := 0.0
+	mean := h.Mean()
+
+	for i := range h.bins {
+		sum += (h.bins[i].count * (h.bins[i].value - mean) * (h.bins[i].value - mean))
+	}
+
+	return sum / float64(h.total)
+}
+
+func (h *NumericHistogram) Count() float64 {
+	return float64(h.total)
+}
+
+// trim merges adjacent bins to decrease the bin count to the maximum value
+func (h *NumericHistogram) trim() {
+	for len(h.bins) > h.maxbins {
+		// Find closest bins in terms of value
+		minDelta := 1e99
+		minDeltaIndex := 0
+		for i := range h.bins {
+			if i == 0 {
+				continue
+			}
+
+			if delta := h.bins[i].value - h.bins[i-1].value; delta < minDelta {
+				minDelta = delta
+				minDeltaIndex = i
+			}
+		}
+
+		// We need to merge bins minDeltaIndex-1 and minDeltaIndex
+		totalCount := h.bins[minDeltaIndex-1].count + h.bins[minDeltaIndex].count
+		mergedbin := bin{
+			value: (h.bins[minDeltaIndex-1].value*
+				h.bins[minDeltaIndex-1].count +
+				h.bins[minDeltaIndex].value*
+					h.bins[minDeltaIndex].count) /
+				totalCount, // weighted average
+			count: totalCount, // summed heights
+		}
+		head := append(make([]bin, 0), h.bins[0:minDeltaIndex-1]...)
+		tail := append([]bin{mergedbin}, h.bins[minDeltaIndex+1:]...)
+		h.bins = append(head, tail...)
+	}
+}
+
+// String returns a string reprentation of the histogram,
+// which is useful for printing to a terminal.
+func (h *NumericHistogram) String() (str string) {
+	str += fmt.Sprintln("Total:", h.total)
+
+	for i := range h.bins {
+		var bar string
+		for j := 0; j < int(float64(h.bins[i].count)/float64(h.total)*200); j++ {
+			bar += "."
+		}
+		str += fmt.Sprintln(h.bins[i].value, "\t", bar)
+	}
+
+	return
+}
diff --git a/vendor/github.com/VividCortex/gohistogram/weightedhistogram.go b/vendor/github.com/VividCortex/gohistogram/weightedhistogram.go
new file mode 100644
index 000000000..16eed3719
--- /dev/null
+++ b/vendor/github.com/VividCortex/gohistogram/weightedhistogram.go
@@ -0,0 +1,190 @@
+// Package gohistogram contains implementations of weighted and exponential histograms.
+package gohistogram
+
+// Copyright (c) 2013 VividCortex, Inc. All rights reserved.
+// Please see the LICENSE file for applicable license terms.
+
+import "fmt"
+
+// A WeightedHistogram implements Histogram. A WeightedHistogram has bins that have values
+// which are exponentially weighted moving averages. This allows you keep inserting large
+// amounts of data into the histogram and approximate quantiles with recency factored in.
+type WeightedHistogram struct {
+	bins    []bin
+	maxbins int
+	total   float64
+	alpha   float64
+}
+
+// NewWeightedHistogram returns a new WeightedHistogram with a maximum of n bins with a decay factor
+// of alpha.
+//
+// There is no "optimal" bin count, but somewhere between 20 and 80 bins should be
+// sufficient.
+//
+// Alpha should be set to 2 / (N+1), where N represents the average age of the moving window.
+// For example, a 60-second window with an average age of 30 seconds would yield an
+// alpha of 0.064516129.
+func NewWeightedHistogram(n int, alpha float64) *WeightedHistogram {
+	return &WeightedHistogram{
+		bins:    make([]bin, 0),
+		maxbins: n,
+		total:   0,
+		alpha:   alpha,
+	}
+}
+
+func ewma(existingVal float64, newVal float64, alpha float64) (result float64) {
+	result = newVal*(1-alpha) + existingVal*alpha
+	return
+}
+
+func (h *WeightedHistogram) scaleDown(except int) {
+	for i := range h.bins {
+		if i != except {
+			h.bins[i].count = ewma(h.bins[i].count, 0, h.alpha)
+		}
+	}
+}
+
+func (h *WeightedHistogram) Add(n float64) {
+	defer h.trim()
+	for i := range h.bins {
+		if h.bins[i].value == n {
+			h.bins[i].count++
+
+			defer h.scaleDown(i)
+			return
+		}
+
+		if h.bins[i].value > n {
+
+			newbin := bin{value: n, count: 1}
+			head := append(make([]bin, 0), h.bins[0:i]...)
+
+			head = append(head, newbin)
+			tail := h.bins[i:]
+			h.bins = append(head, tail...)
+
+			defer h.scaleDown(i)
+			return
+		}
+	}
+
+	h.bins = append(h.bins, bin{count: 1, value: n})
+}
+
+func (h *WeightedHistogram) Quantile(q float64) float64 {
+	count := q * h.total
+	for i := range h.bins {
+		count -= float64(h.bins[i].count)
+
+		if count <= 0 {
+			return h.bins[i].value
+		}
+	}
+
+	return -1
+}
+
+// CDF returns the value of the cumulative distribution function
+// at x
+func (h *WeightedHistogram) CDF(x float64) float64 {
+	count := 0.0
+	for i := range h.bins {
+		if h.bins[i].value <= x {
+			count += float64(h.bins[i].count)
+		}
+	}
+
+	return count / h.total
+}
+
+// Mean returns the sample mean of the distribution
+func (h *WeightedHistogram) Mean() float64 {
+	if h.total == 0 {
+		return 0
+	}
+
+	sum := 0.0
+
+	for i := range h.bins {
+		sum += h.bins[i].value * h.bins[i].count
+	}
+
+	return sum / h.total
+}
+
+// Variance returns the variance of the distribution
+func (h *WeightedHistogram) Variance() float64 {
+	if h.total == 0 {
+		return 0
+	}
+
+	sum := 0.0
+	mean := h.Mean()
+
+	for i := range h.bins {
+		sum += (h.bins[i].count * (h.bins[i].value - mean) * (h.bins[i].value - mean))
+	}
+
+	return sum / h.total
+}
+
+func (h *WeightedHistogram) Count() float64 {
+	return h.total
+}
+
+func (h *WeightedHistogram) trim() {
+	total := 0.0
+	for i := range h.bins {
+		total += h.bins[i].count
+	}
+	h.total = total
+	for len(h.bins) > h.maxbins {
+
+		// Find closest bins in terms of value
+		minDelta := 1e99
+		minDeltaIndex := 0
+		for i := range h.bins {
+			if i == 0 {
+				continue
+			}
+
+			if delta := h.bins[i].value - h.bins[i-1].value; delta < minDelta {
+				minDelta = delta
+				minDeltaIndex = i
+			}
+		}
+
+		// We need to merge bins minDeltaIndex-1 and minDeltaIndex
+		totalCount := h.bins[minDeltaIndex-1].count + h.bins[minDeltaIndex].count
+		mergedbin := bin{
+			value: (h.bins[minDeltaIndex-1].value*
+				h.bins[minDeltaIndex-1].count +
+				h.bins[minDeltaIndex].value*
+					h.bins[minDeltaIndex].count) /
+				totalCount, // weighted average
+			count: totalCount, // summed heights
+		}
+		head := append(make([]bin, 0), h.bins[0:minDeltaIndex-1]...)
+		tail := append([]bin{mergedbin}, h.bins[minDeltaIndex+1:]...)
+		h.bins = append(head, tail...)
+	}
+}
+
+// String returns a string reprentation of the histogram,
+// which is useful for printing to a terminal.
+func (h *WeightedHistogram) String() (str string) {
+	str += fmt.Sprintln("Total:", h.total)
+
+	for i := range h.bins {
+		var bar string
+		for j := 0; j < int(float64(h.bins[i].count)/float64(h.total)*200); j++ {
+			bar += "."
+		}
+		str += fmt.Sprintln(h.bins[i].value, "\t", bar)
+	}
+
+	return
+}