-
Notifications
You must be signed in to change notification settings - Fork 0
/
percentile.go
101 lines (83 loc) · 2.48 KB
/
percentile.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// Copyright 2015 The faststats Authors. All rights reserved.
// Use of this source code is governed by the BSD 2-Clause license,
// which can be found in the LICENSE file.
package faststats
import (
"math"
"sort"
"sync/atomic"
)
// Percentile implements an efficient percentile calculation of
// arbitrary float64 samples.
type Percentile struct {
percentile float64
samples int64
offset int64
values []float64
value uint64 // These bits are really a float64.
}
// NewPercentile returns a Percentile with a given threshold.
func NewPercentile(percentile float64) *Percentile {
return &Percentile{
percentile: percentile,
// 256 samples is fast, and accurate for most distributions.
values: make([]float64, 0, 256),
}
}
// NewPercentileWithWindow returns a Percentile with a given threshold
// and window size (accuracy).
func NewPercentileWithWindow(percentile float64, sampleWindow int) *Percentile {
return &Percentile{
percentile: percentile,
values: make([]float64, 0, sampleWindow),
}
}
// Value returns the current value at the stored percentile.
// It is thread-safe, and may be called concurrently with AddSample.
func (p *Percentile) Value() float64 {
bits := atomic.LoadUint64(&p.value)
return math.Float64frombits(bits)
}
// AddSample adds a single float64 sample to the data set.
// It is not thread-safe, and must not be called in parallel.
func (p *Percentile) AddSample(sample float64) {
p.samples++
if len(p.values) == cap(p.values) {
target := float64(p.samples)*p.percentile - float64(cap(p.values))/2
offset := round(math.Max(target, 0))
if sample > p.values[0] {
if offset > p.offset {
idx := sort.SearchFloat64s(p.values[1:], sample)
copy(p.values, p.values[1:idx+1])
p.values[idx] = sample
p.offset++
} else if sample < p.values[len(p.values)-1] {
idx := sort.SearchFloat64s(p.values, sample)
copy(p.values[idx+1:], p.values[idx:])
p.values[idx] = sample
}
} else {
if offset > p.offset {
p.offset++
} else {
copy(p.values[1:], p.values)
p.values[0] = sample
}
}
} else {
idx := sort.SearchFloat64s(p.values, sample)
p.values = p.values[:len(p.values)+1]
copy(p.values[idx+1:], p.values[idx:])
p.values[idx] = sample
}
bits := math.Float64bits(p.values[p.index()])
atomic.StoreUint64(&p.value, bits)
}
func (p *Percentile) index() int64 {
idx := round(float64(p.samples)*p.percentile - float64(p.offset))
last := int64(len(p.values)) - 1
if idx > last {
return last
}
return idx
}