Debian Codegraph @

stats/quantile.go

raw
1 package stats
2
3 import (
4 "math"
5
6 "github.com/twotwotwo/sorts"
7 )
8
9 type valueCount struct {
10 Value, Count float64
11 }
12
13 type valueCounts []valueCount
14
15 func (c valueCounts) Len() int { return len(c) }
16 func (c valueCounts) Less(i, j int) bool { return c[i].Value < c[j].Value }
17 func (c valueCounts) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
18
19 type Quantiler struct {
20 count map[float64]float64 // value -> count
21
22 n uint64 // n
23 min, max, sum float64 // sum
24
25 // for sorting
26 counts []valueCount // value, count
27 accCounts []valueCount // value, accumulative count
28 sorted bool
29 }
30
31 // NewQuantiler initializes a Quantiler
32 func NewQuantiler() *Quantiler {
33 return &Quantiler{count: make(map[float64]float64, 1024), min: math.MaxFloat64}
34 }
35
36 // Add adds a new element
37 func (stats *Quantiler) Add(value float64) {
38 stats.n++
39 stats.sum += value
40 stats.count[value]++
41
42 if value > stats.max {
43 stats.max = value
44 }
45 if value < stats.min {
46 stats.min = value
47 }
48
49 stats.sorted = false
50 }
51
52 func (stats *Quantiler) sort() {
53 stats.counts = make([]valueCount, 0, len(stats.count))
54 for value, count := range stats.count {
55 stats.counts = append(stats.counts, valueCount{value, count})
56 }
57 sorts.Quicksort(valueCounts(stats.counts))
58
59 stats.accCounts = make([]valueCount, len(stats.count))
60 for i, data := range stats.counts {
61 if i == 0 {
62 stats.accCounts[i] = valueCount{data.Value, data.Count}
63 } else {
64 stats.accCounts[i] = valueCount{data.Value, data.Count + stats.accCounts[i-1].Count}
65 }
66 }
67
68 stats.sorted = true
69 }
70
71 // Count returns number of elements
72 func (stats *Quantiler) Count() uint64 {
73 return stats.n
74 }
75
76 // Min returns the minimum value
77 func (stats *Quantiler) Min() float64 {
78 if stats.n == 0 {
79 return 0
80 }
81 return stats.min
82 }
83
84 // Max returns the maxinimum length
85 func (stats *Quantiler) Max() float64 {
86 return stats.max
87 }
88
89 // Sum returns the sum
90 func (stats *Quantiler) Sum() float64 {
91 return stats.sum
92 }
93
94 // Mean returns mean
95 func (stats *Quantiler) Mean() float64 {
96 return float64(stats.sum) / float64(stats.n)
97 }
98
99 // Q2 returns Q2
100 func (stats *Quantiler) Q2() float64 {
101 return stats.Median()
102 }
103
104 // Median returns median
105 func (stats *Quantiler) Median() float64 {
106 if !stats.sorted {
107 stats.sort()
108 }
109 if len(stats.counts) == 0 {
110 return 0
111 }
112
113 if len(stats.counts) == 1 {
114 return float64(stats.counts[0].Value)
115 }
116
117 even := stats.n&1 == 0 // %2 == 0
118 var iMedianL, iMedianR uint64 // 0-based
119 if even {
120 iMedianL = uint64(stats.n/2) - 1 // 3
121 iMedianR = uint64(stats.n / 2) // 4
122 } else {
123 iMedianL = uint64(stats.n / 2)
124 }
125
126 return stats.getValue(even, iMedianL, iMedianR)
127 }
128
129 // Q1 returns Q1
130 func (stats *Quantiler) Q1() float64 {
131 if !stats.sorted {
132 stats.sort()
133 }
134 if len(stats.counts) == 0 {
135 return 0
136 }
137
138 if len(stats.counts) == 1 {
139 return stats.counts[0].Value
140 }
141
142 even := stats.n&1 == 0 // %2 == 0
143 var iMedianL, iMedianR uint64 // 0-based
144 var n uint64
145 if even {
146 n = stats.n / 2
147 } else {
148 n = (stats.n + 1) / 2
149 }
150
151 even = n%2 == 0
152 if even {
153 iMedianL = uint64(n/2) - 1
154 iMedianR = uint64(n / 2)
155 } else {
156 iMedianL = uint64(n / 2)
157 }
158
159 return stats.getValue(even, iMedianL, iMedianR)
160 }
161
162 // Q3 returns Q3
163 func (stats *Quantiler) Q3() float64 {
164 if !stats.sorted {
165 stats.sort()
166 }
167 if len(stats.counts) == 0 {
168 return 0
169 }
170
171 if len(stats.counts) == 1 {
172 return stats.counts[0].Value
173 }
174
175 even := stats.n&1 == 0 // %2 == 0
176 var iMedianL, iMedianR uint64 // 0-based
177 var mean, n uint64
178 if even {
179 n = stats.n / 2
180 mean = n
181 } else {
182 n = (stats.n + 1) / 2
183 mean = stats.n / 2
184 }
185
186 even = n%2 == 0
187 if even {
188 iMedianL = uint64(n/2) - 1 + mean
189 iMedianR = uint64(n/2) + mean
190 } else {
191 iMedianL = uint64(n/2) + mean
192 }
193
194 return stats.getValue(even, iMedianL, iMedianR)
195 }
196
197 func (stats *Quantiler) getValue(even bool, iMedianL uint64, iMedianR uint64) float64 {
198
199 var accCount float64
200
201 var flag bool
202 var prev float64
203
204 for _, data := range stats.accCounts {
205 accCount = data.Count
206
207 if flag {
208 // the middle two having different value.
209 // example: 1, 2, 3, 4 or 1, 2
210 return (data.Value + prev) / 2
211 }
212
213 if accCount >= float64(iMedianL+1) {
214 if even {
215 if accCount >= float64(iMedianR+1) {
216 // having >=2 of same value in the middle.
217 // example: 2, 2, 2, 3, 3, 4, 8, 8
218 return data.Value
219 }
220 flag = true
221 prev = data.Value
222 } else {
223 // right here
224 return data.Value
225 }
226 }
227 }
228
229 // never happen
230 // panic("should never happen")
231 return 0
232 }
233
234 func (stats *Quantiler) Percentile(percent float64) float64 {
235 if percent <= 0 || percent > 100 {
236 panic("invalid percentile")
237 }
238 if !stats.sorted {
239 stats.sort()
240 }
241 if len(stats.counts) == 0 {
242 return 0
243 }
244
245 if len(stats.counts) == 1 {
246 return float64(stats.counts[0].Value)
247 }
248
249 i0 := float64(stats.n) * percent / 100
250 i := math.Floor(i0)
251
252 even := math.Abs(i0-i) > 0.001
253 var iMedianL, iMedianR uint64 // 0-based
254 if even {
255 iMedianL = uint64(i) - 1
256 iMedianR = uint64(i)
257 } else {
258 iMedianL = uint64(i - 1)
259 }
260
261 return stats.getValue(even, iMedianL, iMedianR)
262 }