diff options
| -rw-r--r-- | go.mod | 2 | ||||
| -rw-r--r-- | go.sum | 4 | ||||
| -rw-r--r-- | vendor/github.com/VividCortex/gohistogram/.gitignore | 2 | ||||
| -rw-r--r-- | vendor/github.com/VividCortex/gohistogram/LICENSE | 19 | ||||
| -rw-r--r-- | vendor/github.com/VividCortex/gohistogram/README.md | 80 | ||||
| -rw-r--r-- | vendor/github.com/VividCortex/gohistogram/histogram.go | 23 | ||||
| -rw-r--r-- | vendor/github.com/VividCortex/gohistogram/numerichistogram.go | 160 | ||||
| -rw-r--r-- | vendor/github.com/VividCortex/gohistogram/weightedhistogram.go | 190 | ||||
| -rw-r--r-- | vendor/github.com/bsm/histogram/v3/.gitignore | 1 | ||||
| -rw-r--r-- | vendor/github.com/bsm/histogram/v3/LICENSE | 201 | ||||
| -rw-r--r-- | vendor/github.com/bsm/histogram/v3/Makefile | 10 | ||||
| -rw-r--r-- | vendor/github.com/bsm/histogram/v3/README.md | 14 | ||||
| -rw-r--r-- | vendor/github.com/bsm/histogram/v3/bins.go | 18 | ||||
| -rw-r--r-- | vendor/github.com/bsm/histogram/v3/histogram.go | 266 | ||||
| -rw-r--r-- | vendor/modules.txt | 6 |
15 files changed, 480 insertions, 516 deletions
@@ -8,7 +8,7 @@ require ( cloud.google.com/go/pubsub v1.38.0 cloud.google.com/go/secretmanager v1.13.1 cloud.google.com/go/storage v1.40.0 - github.com/bsm/histogram/v3 v3.0.2 + github.com/VividCortex/gohistogram v1.0.0 github.com/dvyukov/go-fuzz v0.0.0-20220726122315-1d375ef9f9f6 github.com/golangci/golangci-lint v1.57.2 github.com/google/flatbuffers v24.3.25+incompatible @@ -86,6 +86,8 @@ github.com/Masterminds/semver v1.5.0 h1:H65muMkzWKEuNDnfl9d70GUjFniHKHRbFPGBuZ3Q github.com/Masterminds/semver v1.5.0/go.mod h1:MB6lktGJrhw8PrUyiEoblNEGEQ+RzHPF078ddwwvV3Y= github.com/OpenPeeDeeP/depguard/v2 v2.2.0 h1:vDfG60vDtIuf0MEOhmLlLLSzqaRM8EMcgJPdp74zmpA= github.com/OpenPeeDeeP/depguard/v2 v2.2.0/go.mod h1:CIzddKRvLBC4Au5aYP/i3nyaWQ+ClszLIuVocRiCYFQ= +github.com/VividCortex/gohistogram v1.0.0 h1:6+hBz+qvs0JOrrNhhmR7lFxo5sINxBCGXrdtl/UvroE= +github.com/VividCortex/gohistogram v1.0.0/go.mod h1:Pf5mBqqDxYaXu3hDrrU+w6nw50o/4+TcAqDqk/vUH7g= github.com/aclements/go-gg v0.0.0-20170118225347-6dbb4e4fefb0/go.mod h1:55qNq4vcpkIuHowELi5C8e+1yUHtoLoOUR9QU5j7Tes= github.com/aclements/go-moremath v0.0.0-20210112150236-f10218a38794/go.mod h1:7e+I0LQFUI9AXWxOfsQROs9xPhoJtbsyWcjJqDd4KPY= github.com/ajstarks/svgo v0.0.0-20180226025133-644b8db467af/go.mod h1:K08gAheRH3/J6wwsYMMT4xOr94bZjxIelGM0+d/wbFw= @@ -129,8 +131,6 @@ github.com/breml/bidichk v0.2.7 h1:dAkKQPLl/Qrk7hnP6P+E0xOodrq8Us7+U0o4UBOAlQY= github.com/breml/bidichk v0.2.7/go.mod h1:YodjipAGI9fGcYM7II6wFvGhdMYsC5pHDlGzqvEW3tQ= github.com/breml/errchkjson v0.3.6 h1:VLhVkqSBH96AvXEyclMR37rZslRrY2kcyq+31HCsVrA= github.com/breml/errchkjson v0.3.6/go.mod h1:jhSDoFheAF2RSDOlCfhHO9KqhZgAYLyvHe7bRCX8f/U= -github.com/bsm/histogram/v3 v3.0.2 h1:qCApdlrQkpzA8WKq2jwefpJQur1U4bd38EEV6eIuhiE= -github.com/bsm/histogram/v3 v3.0.2/go.mod h1:V98nemomBkQGgi9Arhz4DTRWoKMtG/j3EpjqrexrWzM= github.com/butuzov/ireturn v0.3.0 h1:hTjMqWw3y5JC3kpnC5vXmFJAWI/m31jaCYQqzkS6PL0= github.com/butuzov/ireturn v0.3.0/go.mod h1:A09nIiwiqzN/IoVo9ogpa0Hzi9fex1kd9PSD6edP5ZA= github.com/butuzov/mirror v1.1.0 h1:ZqX54gBVMXu78QLoiqdwpl2mgmoOJTk7s4p4o+0avZI= 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 + + + +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: + + + +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: + + + +## 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 +} diff --git a/vendor/github.com/bsm/histogram/v3/.gitignore b/vendor/github.com/bsm/histogram/v3/.gitignore deleted file mode 100644 index 48b8bf907..000000000 --- a/vendor/github.com/bsm/histogram/v3/.gitignore +++ /dev/null @@ -1 +0,0 @@ -vendor/ diff --git a/vendor/github.com/bsm/histogram/v3/LICENSE b/vendor/github.com/bsm/histogram/v3/LICENSE deleted file mode 100644 index 1625b8474..000000000 --- a/vendor/github.com/bsm/histogram/v3/LICENSE +++ /dev/null @@ -1,201 +0,0 @@ - Apache License - Version 2.0, January 2004 - http://www.apache.org/licenses/ - - TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION - - 1. Definitions. - - "License" shall mean the terms and conditions for use, reproduction, - and distribution as defined by Sections 1 through 9 of this document. - - "Licensor" shall mean the copyright owner or entity authorized by - the copyright owner that is granting the License. - - "Legal Entity" shall mean the union of the acting entity and all - other entities that control, are controlled by, or are under common - control with that entity. For the purposes of this definition, - "control" means (i) the power, direct or indirect, to cause the - direction or management of such entity, whether by contract or - otherwise, or (ii) ownership of fifty percent (50%) or more of the - outstanding shares, or (iii) beneficial ownership of such entity. - - "You" (or "Your") shall mean an individual or Legal Entity - exercising permissions granted by this License. - - "Source" form shall mean the preferred form for making modifications, - including but not limited to software source code, documentation - source, and configuration files. - - "Object" form shall mean any form resulting from mechanical - transformation or translation of a Source form, including but - not limited to compiled object code, generated documentation, - and conversions to other media types. - - "Work" shall mean the work of authorship, whether in Source or - Object form, made available under the License, as indicated by a - copyright notice that is included in or attached to the work - (an example is provided in the Appendix below). - - "Derivative Works" shall mean any work, whether in Source or Object - form, that is based on (or derived from) the Work and for which the - editorial revisions, annotations, elaborations, or other modifications - represent, as a whole, an original work of authorship. For the purposes - of this License, Derivative Works shall not include works that remain - separable from, or merely link (or bind by name) to the interfaces of, - the Work and Derivative Works thereof. - - "Contribution" shall mean any work of authorship, including - the original version of the Work and any modifications or additions - to that Work or Derivative Works thereof, that is intentionally - submitted to Licensor for inclusion in the Work by the copyright owner - or by an individual or Legal Entity authorized to submit on behalf of - the copyright owner. For the purposes of this definition, "submitted" - means any form of electronic, verbal, or written communication sent - to the Licensor or its representatives, including but not limited to - communication on electronic mailing lists, source code control systems, - and issue tracking systems that are managed by, or on behalf of, the - Licensor for the purpose of discussing and improving the Work, but - excluding communication that is conspicuously marked or otherwise - designated in writing by the copyright owner as "Not a Contribution." - - "Contributor" shall mean Licensor and any individual or Legal Entity - on behalf of whom a Contribution has been received by Licensor and - subsequently incorporated within the Work. - - 2. Grant of Copyright License. Subject to the terms and conditions of - this License, each Contributor hereby grants to You a perpetual, - worldwide, non-exclusive, no-charge, royalty-free, irrevocable - copyright license to reproduce, prepare Derivative Works of, - publicly display, publicly perform, sublicense, and distribute the - Work and such Derivative Works in Source or Object form. - - 3. Grant of Patent License. Subject to the terms and conditions of - this License, each Contributor hereby grants to You a perpetual, - worldwide, non-exclusive, no-charge, royalty-free, irrevocable - (except as stated in this section) patent license to make, have made, - use, offer to sell, sell, import, and otherwise transfer the Work, - where such license applies only to those patent claims licensable - by such Contributor that are necessarily infringed by their - Contribution(s) alone or by combination of their Contribution(s) - with the Work to which such Contribution(s) was submitted. If You - institute patent litigation against any entity (including a - cross-claim or counterclaim in a lawsuit) alleging that the Work - or a Contribution incorporated within the Work constitutes direct - or contributory patent infringement, then any patent licenses - granted to You under this License for that Work shall terminate - as of the date such litigation is filed. - - 4. Redistribution. You may reproduce and distribute copies of the - Work or Derivative Works thereof in any medium, with or without - modifications, and in Source or Object form, provided that You - meet the following conditions: - - (a) You must give any other recipients of the Work or - Derivative Works a copy of this License; and - - (b) You must cause any modified files to carry prominent notices - stating that You changed the files; and - - (c) You must retain, in the Source form of any Derivative Works - that You distribute, all copyright, patent, trademark, and - attribution notices from the Source form of the Work, - excluding those notices that do not pertain to any part of - the Derivative Works; and - - (d) If the Work includes a "NOTICE" text file as part of its - distribution, then any Derivative Works that You distribute must - include a readable copy of the attribution notices contained - within such NOTICE file, excluding those notices that do not - pertain to any part of the Derivative Works, in at least one - of the following places: within a NOTICE text file distributed - as part of the Derivative Works; within the Source form or - documentation, if provided along with the Derivative Works; or, - within a display generated by the Derivative Works, if and - wherever such third-party notices normally appear. The contents - of the NOTICE file are for informational purposes only and - do not modify the License. You may add Your own attribution - notices within Derivative Works that You distribute, alongside - or as an addendum to the NOTICE text from the Work, provided - that such additional attribution notices cannot be construed - as modifying the License. - - You may add Your own copyright statement to Your modifications and - may provide additional or different license terms and conditions - for use, reproduction, or distribution of Your modifications, or - for any such Derivative Works as a whole, provided Your use, - reproduction, and distribution of the Work otherwise complies with - the conditions stated in this License. - - 5. Submission of Contributions. Unless You explicitly state otherwise, - any Contribution intentionally submitted for inclusion in the Work - by You to the Licensor shall be under the terms and conditions of - this License, without any additional terms or conditions. - Notwithstanding the above, nothing herein shall supersede or modify - the terms of any separate license agreement you may have executed - with Licensor regarding such Contributions. - - 6. Trademarks. This License does not grant permission to use the trade - names, trademarks, service marks, or product names of the Licensor, - except as required for reasonable and customary use in describing the - origin of the Work and reproducing the content of the NOTICE file. - - 7. Disclaimer of Warranty. Unless required by applicable law or - agreed to in writing, Licensor provides the Work (and each - Contributor provides its Contributions) on an "AS IS" BASIS, - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or - implied, including, without limitation, any warranties or conditions - of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A - PARTICULAR PURPOSE. You are solely responsible for determining the - appropriateness of using or redistributing the Work and assume any - risks associated with Your exercise of permissions under this License. - - 8. Limitation of Liability. In no event and under no legal theory, - whether in tort (including negligence), contract, or otherwise, - unless required by applicable law (such as deliberate and grossly - negligent acts) or agreed to in writing, shall any Contributor be - liable to You for damages, including any direct, indirect, special, - incidental, or consequential damages of any character arising as a - result of this License or out of the use or inability to use the - Work (including but not limited to damages for loss of goodwill, - work stoppage, computer failure or malfunction, or any and all - other commercial damages or losses), even if such Contributor - has been advised of the possibility of such damages. - - 9. Accepting Warranty or Additional Liability. While redistributing - the Work or Derivative Works thereof, You may choose to offer, - and charge a fee for, acceptance of support, warranty, indemnity, - or other liability obligations and/or rights consistent with this - License. However, in accepting such obligations, You may act only - on Your own behalf and on Your sole responsibility, not on behalf - of any other Contributor, and only if You agree to indemnify, - defend, and hold each Contributor harmless for any liability - incurred by, or claims asserted against, such Contributor by reason - of your accepting any such warranty or additional liability. - - END OF TERMS AND CONDITIONS - - APPENDIX: How to apply the Apache License to your work. - - To apply the Apache License to your work, attach the following - boilerplate notice, with the fields enclosed by brackets "[]" - replaced with your own identifying information. (Don't include - the brackets!) The text should be enclosed in the appropriate - comment syntax for the file format. We also recommend that a - file or class name and description of purpose be included on the - same "printed page" as the copyright notice for easier - identification within third-party archives. - - Copyright 2021 Black Square Media Ltd - - Licensed under the Apache License, Version 2.0 (the "License"); - you may not use this file except in compliance with the License. - You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - - Unless required by applicable law or agreed to in writing, software - distributed under the License is distributed on an "AS IS" BASIS, - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - See the License for the specific language governing permissions and - limitations under the License. diff --git a/vendor/github.com/bsm/histogram/v3/Makefile b/vendor/github.com/bsm/histogram/v3/Makefile deleted file mode 100644 index f9073368b..000000000 --- a/vendor/github.com/bsm/histogram/v3/Makefile +++ /dev/null @@ -1,10 +0,0 @@ -default: test - -test: - go test ./... - -bench: - go test ./... -run=NONE -bench=. -benchmem - -lint: - golangci-lint run diff --git a/vendor/github.com/bsm/histogram/v3/README.md b/vendor/github.com/bsm/histogram/v3/README.md deleted file mode 100644 index e52c241fd..000000000 --- a/vendor/github.com/bsm/histogram/v3/README.md +++ /dev/null @@ -1,14 +0,0 @@ -# Histogram - -[](https://travis-ci.org/bsm/histogram) [](https://godoc.org/github.com/bsm/histogram) - -Fast Go implementation of Ben-Haim's and Yom-Tov's streaming histogram algorithm, as described in their _A Streaming Parallel Decision Tree Algorithm_ -(2010, [PDF](http://jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf)) paper. - -## Documentation - -Please see the [API documentation](https://godoc.org/github.com/bsm/histogram) for package and API descriptions and examples. - -## Credits - -- Aaron Windsor - https://github.com/aaw/histosketch (released into the public domain). diff --git a/vendor/github.com/bsm/histogram/v3/bins.go b/vendor/github.com/bsm/histogram/v3/bins.go deleted file mode 100644 index 41e9e9252..000000000 --- a/vendor/github.com/bsm/histogram/v3/bins.go +++ /dev/null @@ -1,18 +0,0 @@ -package histogram - -import "math" - -type bin struct { - w float64 // weight - v float64 // value -} - -func (b bin) Sum() float64 { return math.Abs(b.w) * b.v } - -// ---------------------------------------------------------- - -type binSlice []bin - -func (s binSlice) Len() int { return len(s) } -func (s binSlice) Less(i, j int) bool { return s[i].v < s[j].v } -func (s binSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } diff --git a/vendor/github.com/bsm/histogram/v3/histogram.go b/vendor/github.com/bsm/histogram/v3/histogram.go deleted file mode 100644 index c7c68bf74..000000000 --- a/vendor/github.com/bsm/histogram/v3/histogram.go +++ /dev/null @@ -1,266 +0,0 @@ -package histogram - -import ( - "math" - "sort" -) - -// Histogram is a probabilistic, fixed-size data structure, able to -// accommodate massive data streams while predicting distributions -// and quantiles much more accurately than a sample-based approach. -// -// Please note that a historgram is not thread-safe. All operations -// must be protected by a mutex if used across multiple goroutines. -type Histogram struct { - bins []bin - size int - weight float64 - - min, max float64 -} - -// New creates a new histogram with a maximum size. -func New(sz int) *Histogram { - h := new(Histogram) - h.Reset(sz) - return h -} - -// Reset resets the struct to its initial state with -// a specific size. -func (h *Histogram) Reset(sz int) { - if sz < cap(h.bins) { - h.bins = h.bins[:0] - } else { - h.bins = make([]bin, 0, sz+1) - } - - h.size = sz - h.min = math.NaN() - h.max = math.NaN() - h.weight = 0 -} - -// Copy copies h to x and returns x. If x is passed as nil -// a new Histogram will be inited. -func (h *Histogram) Copy(x *Histogram) *Histogram { - if x == nil { - x = new(Histogram) - } - if sz := h.size; sz < cap(x.bins) { - x.bins = x.bins[:len(h.bins)] - } else { - x.bins = make([]bin, len(h.bins), sz+1) - } - copy(x.bins, h.bins) - - x.size = h.size - x.min = h.min - x.max = h.max - x.weight = h.weight - return x -} - -// Count returns the observed weight truncated to the next integer. -func (h *Histogram) Count() int { return int(h.weight) } - -// Weight returns the observed weight (usually, the number of items seen). -func (h *Histogram) Weight() float64 { return h.weight } - -// Min returns the smallest observed value. -// Returns NaN if Count is zero. -func (h *Histogram) Min() float64 { - if h.weight == 0 { - return math.NaN() - } - return h.min -} - -// Max returns the largest observed value. -// Returns NaN if Count is zero. -func (h *Histogram) Max() float64 { - if h.weight == 0 { - return math.NaN() - } - return h.max -} - -// Sum returns the (approximate) sum of all observed values. -// Returns NaN if Count is zero. -func (h *Histogram) Sum() float64 { - if h.weight == 0 { - return math.NaN() - } - - var sum float64 - for _, b := range h.bins { - sum += b.Sum() - } - return sum -} - -// Mean returns the (approximate) average observed value. -// Returns NaN if Count is zero. -func (h *Histogram) Mean() float64 { - if h.weight == 0 { - return math.NaN() - } - return h.Sum() / h.weight -} - -// Variance returns the (approximate) sample variance of the distribution. -// Returns NaN if Count is zero. -func (h *Histogram) Variance() float64 { - if h.weight <= 1 { - return math.NaN() - } - - var vv float64 - mean := h.Mean() - for _, b := range h.bins { - delta := mean - b.v - vv += delta * delta * b.w - } - return vv / (h.weight - 1) -} - -// Quantile returns the (approximate) quantile of the distribution. -// Accepted values for q are between 0.0 and 1.0. -// Returns NaN if Count is zero or bad inputs. -func (h *Histogram) Quantile(q float64) float64 { - if h.weight == 0 || q < 0.0 || q > 1.0 { - return math.NaN() - } else if q == 0.0 { - return h.min - } else if q == 1.0 { - return h.max - } - - delta := q * h.weight - pos := 0 - for w0 := 0.0; pos < len(h.bins); pos++ { - w1 := math.Abs(h.bins[pos].w) / 2.0 - if delta-w1-w0 < 0 { - break - } - delta -= (w1 + w0) - w0 = w1 - } - - switch pos { - case 0: // lower bound - return h.solve(bin{v: h.min, w: 0}, h.bins[pos], delta) - case len(h.bins): // upper bound - return h.solve(h.bins[pos-1], bin{v: h.max, w: 0}, delta) - default: - return h.solve(h.bins[pos-1], h.bins[pos], delta) - } -} - -// Add is the same as AddWeight(v, 1) -func (h *Histogram) Add(v float64) { h.AddWeight(v, 1) } - -// AddN is the same as AddWeight(v, float64(n)) -func (h *Histogram) AddN(v float64, n int) { h.AddWeight(v, float64(n)) } - -// AddWeight adds observations of v with the weight w to the distribution. -func (h *Histogram) AddWeight(v, w float64) { - if w <= 0 { - return - } - if h.weight == 0 || v < h.min { - h.min = v - } - if h.weight == 0 || v > h.max { - h.max = v - } - - h.insert(v, w) - h.weight += w - - h.prune() -} - -// Merge sets h to the union x ∪ y. -func (h *Histogram) Merge(x, y *Histogram) { - h.bins = append(h.bins[:0], x.bins...) - h.bins = append(h.bins, y.bins...) - sort.Sort(binSlice(h.bins)) - h.prune() -} - -// MergeWith sets h to the union h ∪ x. -func (h *Histogram) MergeWith(x *Histogram) { h.Merge(h, x) } - -// NumBins returns bin (bucket) count. -func (h *Histogram) NumBins() int { return len(h.bins) } - -// Bin returns bin (bucket) data. -// Requested index must be 0 <= i < NumBins() or it will panic. -func (h *Histogram) Bin(i int) (value, weight float64) { - b := h.bins[i] - return b.v, b.w -} - -func (h *Histogram) solve(b1, b2 bin, delta float64) float64 { - w1, w2 := b1.w, b2.w - - // return if both bins are exact (unmerged) - if w1 > 0 && w2 > 0 { - return b2.v - } - - // normalise - w1, w2 = math.Abs(w1), math.Abs(w2) - - // calculate multiplier - var z float64 - if w1 == w2 { - z = delta / w1 - } else { - a := 2 * (w2 - w1) - b := 2 * w1 - z = (math.Sqrt(b*b+4*a*delta) - b) / a - } - return b1.v + (b2.v-b1.v)*z -} - -func (h *Histogram) insert(v, w float64) { - pos := h.search(v) - if pos < len(h.bins) && h.bins[pos].v == v { - h.bins[pos].w += math.Copysign(w, h.bins[pos].w) - return - } - - maxi := len(h.bins) - h.bins = h.bins[:len(h.bins)+1] - if pos != maxi { - copy(h.bins[pos+1:], h.bins[pos:]) - } - h.bins[pos].w = w - h.bins[pos].v = v -} - -func (h *Histogram) prune() { - for len(h.bins) > h.size { - delta := math.MaxFloat64 - pos := 0 - for i := 0; i < len(h.bins)-1; i++ { - b1, b2 := h.bins[i], h.bins[i+1] - if x := b2.v - b1.v; x < delta { - pos, delta = i, x - } - } - - b1, b2 := h.bins[pos], h.bins[pos+1] - w := math.Abs(b1.w) + math.Abs(b2.w) - v := (b1.Sum() + b2.Sum()) / w - h.bins[pos+1].w = -w - h.bins[pos+1].v = v - h.bins = h.bins[:pos+copy(h.bins[pos:], h.bins[pos+1:])] - } -} - -func (h *Histogram) search(v float64) int { - return sort.Search(len(h.bins), func(i int) bool { return h.bins[i].v >= v }) -} diff --git a/vendor/modules.txt b/vendor/modules.txt index d18ccf39a..e0f764eb6 100644 --- a/vendor/modules.txt +++ b/vendor/modules.txt @@ -119,6 +119,9 @@ github.com/Masterminds/semver ## explicit; go 1.20 github.com/OpenPeeDeeP/depguard/v2 github.com/OpenPeeDeeP/depguard/v2/internal/utils +# github.com/VividCortex/gohistogram v1.0.0 +## explicit +github.com/VividCortex/gohistogram # github.com/alecthomas/go-check-sumtype v0.1.4 ## explicit; go 1.18 github.com/alecthomas/go-check-sumtype @@ -155,9 +158,6 @@ github.com/breml/bidichk/pkg/bidichk # github.com/breml/errchkjson v0.3.6 ## explicit; go 1.20 github.com/breml/errchkjson -# github.com/bsm/histogram/v3 v3.0.2 -## explicit; go 1.14 -github.com/bsm/histogram/v3 # github.com/butuzov/ireturn v0.3.0 ## explicit; go 1.18 github.com/butuzov/ireturn/analyzer |