| 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 |
} |