1 package quantile
2
3 import (
4 "math"
5 "math/rand"
6 "sort"
7 "testing"
8 )
9
10 var (
11 Targets = map[float64]float64{
12 0.01: 0.001,
13 0.10: 0.01,
14 0.50: 0.05,
15 0.90: 0.01,
16 0.99: 0.001,
17 }
18 TargetsSmallEpsilon = map[float64]float64{
19 0.01: 0.0001,
20 0.10: 0.001,
21 0.50: 0.005,
22 0.90: 0.001,
23 0.99: 0.0001,
24 }
25 LowQuantiles = []float64{0.01, 0.1, 0.5}
26 HighQuantiles = []float64{0.99, 0.9, 0.5}
27 )
28
29 const RelativeEpsilon = 0.01
30
31 func verifyPercsWithAbsoluteEpsilon(t *testing.T, a []float64, s *Stream) {
32 sort.Float64s(a)
33 for quantile, epsilon := range Targets {
34 n := float64(len(a))
35 k := int(quantile * n)
36 if k < 1 {
37 k = 1
38 }
39 lower := int((quantile - epsilon) * n)
40 if lower < 1 {
41 lower = 1
42 }
43 upper := int(math.Ceil((quantile + epsilon) * n))
44 if upper > len(a) {
45 upper = len(a)
46 }
47 w, min, max := a[k-1], a[lower-1], a[upper-1]
48 if g := s.Query(quantile); g < min || g > max {
49 t.Errorf("q=%f: want %v [%f,%f], got %v", quantile, w, min, max, g)
50 }
51 }
52 }
53
54 func verifyLowPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) {
55 sort.Float64s(a)
56 for _, qu := range LowQuantiles {
57 n := float64(len(a))
58 k := int(qu * n)
59
60 lowerRank := int((1 - RelativeEpsilon) * qu * n)
61 upperRank := int(math.Ceil((1 + RelativeEpsilon) * qu * n))
62 w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1]
63 if g := s.Query(qu); g < min || g > max {
64 t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g)
65 }
66 }
67 }
68
69 func verifyHighPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) {
70 sort.Float64s(a)
71 for _, qu := range HighQuantiles {
72 n := float64(len(a))
73 k := int(qu * n)
74
75 lowerRank := int((1 - (1+RelativeEpsilon)*(1-qu)) * n)
76 upperRank := int(math.Ceil((1 - (1-RelativeEpsilon)*(1-qu)) * n))
77 w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1]
78 if g := s.Query(qu); g < min || g > max {
79 t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g)
80 }
81 }
82 }
83
84 func populateStream(s *Stream) []float64 {
85 a := make([]float64, 0, 1e5+100)
86 for i := 0; i < cap(a); i++ {
87 v := rand.NormFloat64()
88
89 if i%20 == 0 {
90 v = v*v + 1
91 }
92 s.Insert(v)
93 a = append(a, v)
94 }
95 return a
96 }
97
98 func TestTargetedQuery(t *testing.T) {
99 rand.Seed(42)
100 s := NewTargeted(Targets)
101 a := populateStream(s)
102 verifyPercsWithAbsoluteEpsilon(t, a, s)
103 }
104
105 func TestTargetedQuerySmallSampleSize(t *testing.T) {
106 rand.Seed(42)
107 s := NewTargeted(TargetsSmallEpsilon)
108 a := []float64{1, 2, 3, 4, 5}
109 for _, v := range a {
110 s.Insert(v)
111 }
112 verifyPercsWithAbsoluteEpsilon(t, a, s)
113
114 if !s.flushed() {
115 for φ, want := range map[float64]float64{
116 0.01: 1,
117 0.10: 1,
118 0.50: 3,
119 0.90: 5,
120 0.99: 5,
121 } {
122 if got := s.Query(φ); got != want {
123 t.Errorf("want %f for φ=%f, got %f", want, φ, got)
124 }
125 }
126 }
127 }
128
129 func TestLowBiasedQuery(t *testing.T) {
130 rand.Seed(42)
131 s := NewLowBiased(RelativeEpsilon)
132 a := populateStream(s)
133 verifyLowPercsWithRelativeEpsilon(t, a, s)
134 }
135
136 func TestHighBiasedQuery(t *testing.T) {
137 rand.Seed(42)
138 s := NewHighBiased(RelativeEpsilon)
139 a := populateStream(s)
140 verifyHighPercsWithRelativeEpsilon(t, a, s)
141 }
142
143
144 func BrokenTestTargetedMerge(t *testing.T) {
145 rand.Seed(42)
146 s1 := NewTargeted(Targets)
147 s2 := NewTargeted(Targets)
148 a := populateStream(s1)
149 a = append(a, populateStream(s2)...)
150 s1.Merge(s2.Samples())
151 verifyPercsWithAbsoluteEpsilon(t, a, s1)
152 }
153
154
155 func BrokenTestLowBiasedMerge(t *testing.T) {
156 rand.Seed(42)
157 s1 := NewLowBiased(RelativeEpsilon)
158 s2 := NewLowBiased(RelativeEpsilon)
159 a := populateStream(s1)
160 a = append(a, populateStream(s2)...)
161 s1.Merge(s2.Samples())
162 verifyLowPercsWithRelativeEpsilon(t, a, s2)
163 }
164
165
166 func BrokenTestHighBiasedMerge(t *testing.T) {
167 rand.Seed(42)
168 s1 := NewHighBiased(RelativeEpsilon)
169 s2 := NewHighBiased(RelativeEpsilon)
170 a := populateStream(s1)
171 a = append(a, populateStream(s2)...)
172 s1.Merge(s2.Samples())
173 verifyHighPercsWithRelativeEpsilon(t, a, s2)
174 }
175
176 func TestUncompressed(t *testing.T) {
177 q := NewTargeted(Targets)
178 for i := 100; i > 0; i-- {
179 q.Insert(float64(i))
180 }
181 if g := q.Count(); g != 100 {
182 t.Errorf("want count 100, got %d", g)
183 }
184
185 for quantile := range Targets {
186 w := quantile * 100
187 if g := q.Query(quantile); g != w {
188 t.Errorf("want %f, got %f", w, g)
189 }
190 }
191 }
192
193 func TestUncompressedSamples(t *testing.T) {
194 q := NewTargeted(map[float64]float64{0.99: 0.001})
195 for i := 1; i <= 100; i++ {
196 q.Insert(float64(i))
197 }
198 if g := q.Samples().Len(); g != 100 {
199 t.Errorf("want count 100, got %d", g)
200 }
201 }
202
203 func TestUncompressedOne(t *testing.T) {
204 q := NewTargeted(map[float64]float64{0.99: 0.01})
205 q.Insert(3.14)
206 if g := q.Query(0.90); g != 3.14 {
207 t.Error("want PI, got", g)
208 }
209 }
210
211 func TestDefaults(t *testing.T) {
212 if g := NewTargeted(map[float64]float64{0.99: 0.001}).Query(0.99); g != 0 {
213 t.Errorf("want 0, got %f", g)
214 }
215 }
216
View as plain text