-
Notifications
You must be signed in to change notification settings - Fork 0
/
summary.go
98 lines (87 loc) · 2.09 KB
/
summary.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
package main
import (
"errors"
"math"
"sort"
)
type Summary struct {
tuples []tuple
compressingInterval int
epsilon float64
n int
}
type tuple struct {
value float64
gap int
delta int
}
func NewSummary(epsilon float64) *Summary {
return &Summary{
epsilon: epsilon,
compressingInterval: int(math.Floor(1 / (2 * epsilon))),
}
}
func (s *Summary) Add(v float64) {
i := sort.Search(len(s.tuples), func(i int) bool { return s.tuples[i].value >= v })
delta := 0
if i > 0 && i < len(s.tuples) {
delta = int(math.Floor(2 * s.epsilon * float64(s.n)))
}
t := tuple{value: v, gap: 1, delta: delta}
if i < len(s.tuples) {
s.tuples = append(s.tuples, tuple{})
copy(s.tuples[i+1:], s.tuples[i:])
s.tuples[i] = t
} else {
s.tuples = append(s.tuples, t)
}
s.n++
if s.n%s.compressingInterval == 0 {
s.compress()
}
}
func (s *Summary) Quantile(p float64) (float64, error) {
if len(s.tuples) == 0 {
return 0, errors.New("no value added")
}
rank := p*float64(s.n) + 1
margin := int(math.Ceil(s.epsilon * float64(s.n)))
rankMinusMargin := int(rank) - margin
rankPlusMargin := int(rank) + margin
bestIndex := -1
bestDist := math.MaxFloat64
rMin := 0
for i := range s.tuples {
t := &s.tuples[i]
rMin += t.gap
rMax := rMin + t.delta
if rankMinusMargin <= rMin && rMax <= rankPlusMargin {
currentDist := math.Abs(rank - float64(rMin+rMax)/2)
if currentDist < bestDist {
bestDist = currentDist
bestIndex = i
}
}
}
if bestIndex == -1 {
return 0, errors.New("quantile not found")
}
return s.tuples[bestIndex].value, nil
}
func (s *Summary) compress() {
threshold := int(math.Floor(2 * s.epsilon * float64(s.n)))
for i := len(s.tuples) - 2; i >= 1; i-- {
for i < len(s.tuples)-1 && s.deleteIfNeeded(i, threshold) {
}
}
}
func (s *Summary) deleteIfNeeded(i, threshold int) bool {
t1, t2 := &s.tuples[i], &s.tuples[i+1]
if t1.delta >= t2.delta && t1.gap+t2.gap+t2.delta < threshold {
t2.gap += t1.gap
copy(s.tuples[i:], s.tuples[i+1:])
s.tuples = s.tuples[:len(s.tuples)-1]
return true
}
return false
}