1package quantile 2 3import ( 4 "math" 5 "math/rand" 6 "sort" 7 "testing" 8) 9 10var ( 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 29const RelativeEpsilon = 0.01 30 31func 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 54func 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 69func 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 84func populateStream(s *Stream) []float64 { 85 a := make([]float64, 0, 1e5+100) 86 for i := 0; i < cap(a); i++ { 87 v := rand.NormFloat64() 88 // Add 5% asymmetric outliers. 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 98func TestTargetedQuery(t *testing.T) { 99 rand.Seed(42) 100 s := NewTargeted(Targets) 101 a := populateStream(s) 102 verifyPercsWithAbsoluteEpsilon(t, a, s) 103} 104 105func 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 // If not yet flushed, results should be precise: 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 129func TestLowBiasedQuery(t *testing.T) { 130 rand.Seed(42) 131 s := NewLowBiased(RelativeEpsilon) 132 a := populateStream(s) 133 verifyLowPercsWithRelativeEpsilon(t, a, s) 134} 135 136func TestHighBiasedQuery(t *testing.T) { 137 rand.Seed(42) 138 s := NewHighBiased(RelativeEpsilon) 139 a := populateStream(s) 140 verifyHighPercsWithRelativeEpsilon(t, a, s) 141} 142 143// BrokenTestTargetedMerge is broken, see Merge doc comment. 144func 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// BrokenTestLowBiasedMerge is broken, see Merge doc comment. 155func 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// BrokenTestHighBiasedMerge is broken, see Merge doc comment. 166func 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 176func 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 // Before compression, Query should have 100% accuracy. 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 193func 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 203func 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 211func 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