From 7b4377ad9d8a7205416df8d6217ef2b010f89481 Mon Sep 17 00:00:00 2001 From: Taras Madan Date: Wed, 22 Jan 2025 16:07:17 +0100 Subject: vendor: delete --- .../github.com/VividCortex/gohistogram/.gitignore | 2 - vendor/github.com/VividCortex/gohistogram/LICENSE | 19 --- .../github.com/VividCortex/gohistogram/README.md | 80 --------- .../VividCortex/gohistogram/histogram.go | 23 --- .../VividCortex/gohistogram/numerichistogram.go | 160 ----------------- .../VividCortex/gohistogram/weightedhistogram.go | 190 --------------------- 6 files changed, 474 deletions(-) delete mode 100644 vendor/github.com/VividCortex/gohistogram/.gitignore delete mode 100644 vendor/github.com/VividCortex/gohistogram/LICENSE delete mode 100644 vendor/github.com/VividCortex/gohistogram/README.md delete mode 100644 vendor/github.com/VividCortex/gohistogram/histogram.go delete mode 100644 vendor/github.com/VividCortex/gohistogram/numerichistogram.go delete mode 100644 vendor/github.com/VividCortex/gohistogram/weightedhistogram.go (limited to 'vendor/github.com/VividCortex') diff --git a/vendor/github.com/VividCortex/gohistogram/.gitignore b/vendor/github.com/VividCortex/gohistogram/.gitignore deleted file mode 100644 index 4c51178c9..000000000 --- a/vendor/github.com/VividCortex/gohistogram/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -\#* -.\#* \ No newline at end of file diff --git a/vendor/github.com/VividCortex/gohistogram/LICENSE b/vendor/github.com/VividCortex/gohistogram/LICENSE deleted file mode 100644 index d23fea365..000000000 --- a/vendor/github.com/VividCortex/gohistogram/LICENSE +++ /dev/null @@ -1,19 +0,0 @@ -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 deleted file mode 100644 index eeb14d366..000000000 --- a/vendor/github.com/VividCortex/gohistogram/README.md +++ /dev/null @@ -1,80 +0,0 @@ -# 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 deleted file mode 100644 index ede21fd31..000000000 --- a/vendor/github.com/VividCortex/gohistogram/histogram.go +++ /dev/null @@ -1,23 +0,0 @@ -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 deleted file mode 100644 index 20dea740d..000000000 --- a/vendor/github.com/VividCortex/gohistogram/numerichistogram.go +++ /dev/null @@ -1,160 +0,0 @@ -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 deleted file mode 100644 index 16eed3719..000000000 --- a/vendor/github.com/VividCortex/gohistogram/weightedhistogram.go +++ /dev/null @@ -1,190 +0,0 @@ -// 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 -} -- cgit mrf-deployment