| package quantile |
| |
| import ( |
| "math" |
| "math/rand" |
| "sort" |
| "testing" |
| ) |
| |
| var ( |
| Targets = map[float64]float64{ |
| 0.01: 0.001, |
| 0.10: 0.01, |
| 0.50: 0.05, |
| 0.90: 0.01, |
| 0.99: 0.001, |
| } |
| TargetsSmallEpsilon = map[float64]float64{ |
| 0.01: 0.0001, |
| 0.10: 0.001, |
| 0.50: 0.005, |
| 0.90: 0.001, |
| 0.99: 0.0001, |
| } |
| LowQuantiles = []float64{0.01, 0.1, 0.5} |
| HighQuantiles = []float64{0.99, 0.9, 0.5} |
| ) |
| |
| const RelativeEpsilon = 0.01 |
| |
| func verifyPercsWithAbsoluteEpsilon(t *testing.T, a []float64, s *Stream) { |
| sort.Float64s(a) |
| for quantile, epsilon := range Targets { |
| n := float64(len(a)) |
| k := int(quantile * n) |
| if k < 1 { |
| k = 1 |
| } |
| lower := int((quantile - epsilon) * n) |
| if lower < 1 { |
| lower = 1 |
| } |
| upper := int(math.Ceil((quantile + epsilon) * n)) |
| if upper > len(a) { |
| upper = len(a) |
| } |
| w, min, max := a[k-1], a[lower-1], a[upper-1] |
| if g := s.Query(quantile); g < min || g > max { |
| t.Errorf("q=%f: want %v [%f,%f], got %v", quantile, w, min, max, g) |
| } |
| } |
| } |
| |
| func verifyLowPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) { |
| sort.Float64s(a) |
| for _, qu := range LowQuantiles { |
| n := float64(len(a)) |
| k := int(qu * n) |
| |
| lowerRank := int((1 - RelativeEpsilon) * qu * n) |
| upperRank := int(math.Ceil((1 + RelativeEpsilon) * qu * n)) |
| w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1] |
| if g := s.Query(qu); g < min || g > max { |
| t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g) |
| } |
| } |
| } |
| |
| func verifyHighPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) { |
| sort.Float64s(a) |
| for _, qu := range HighQuantiles { |
| n := float64(len(a)) |
| k := int(qu * n) |
| |
| lowerRank := int((1 - (1+RelativeEpsilon)*(1-qu)) * n) |
| upperRank := int(math.Ceil((1 - (1-RelativeEpsilon)*(1-qu)) * n)) |
| w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1] |
| if g := s.Query(qu); g < min || g > max { |
| t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g) |
| } |
| } |
| } |
| |
| func populateStream(s *Stream) []float64 { |
| a := make([]float64, 0, 1e5+100) |
| for i := 0; i < cap(a); i++ { |
| v := rand.NormFloat64() |
| // Add 5% asymmetric outliers. |
| if i%20 == 0 { |
| v = v*v + 1 |
| } |
| s.Insert(v) |
| a = append(a, v) |
| } |
| return a |
| } |
| |
| func TestTargetedQuery(t *testing.T) { |
| rand.Seed(42) |
| s := NewTargeted(Targets) |
| a := populateStream(s) |
| verifyPercsWithAbsoluteEpsilon(t, a, s) |
| } |
| |
| func TestTargetedQuerySmallSampleSize(t *testing.T) { |
| rand.Seed(42) |
| s := NewTargeted(TargetsSmallEpsilon) |
| a := []float64{1, 2, 3, 4, 5} |
| for _, v := range a { |
| s.Insert(v) |
| } |
| verifyPercsWithAbsoluteEpsilon(t, a, s) |
| // If not yet flushed, results should be precise: |
| if !s.flushed() { |
| for φ, want := range map[float64]float64{ |
| 0.01: 1, |
| 0.10: 1, |
| 0.50: 3, |
| 0.90: 5, |
| 0.99: 5, |
| } { |
| if got := s.Query(φ); got != want { |
| t.Errorf("want %f for φ=%f, got %f", want, φ, got) |
| } |
| } |
| } |
| } |
| |
| func TestLowBiasedQuery(t *testing.T) { |
| rand.Seed(42) |
| s := NewLowBiased(RelativeEpsilon) |
| a := populateStream(s) |
| verifyLowPercsWithRelativeEpsilon(t, a, s) |
| } |
| |
| func TestHighBiasedQuery(t *testing.T) { |
| rand.Seed(42) |
| s := NewHighBiased(RelativeEpsilon) |
| a := populateStream(s) |
| verifyHighPercsWithRelativeEpsilon(t, a, s) |
| } |
| |
| // BrokenTestTargetedMerge is broken, see Merge doc comment. |
| func BrokenTestTargetedMerge(t *testing.T) { |
| rand.Seed(42) |
| s1 := NewTargeted(Targets) |
| s2 := NewTargeted(Targets) |
| a := populateStream(s1) |
| a = append(a, populateStream(s2)...) |
| s1.Merge(s2.Samples()) |
| verifyPercsWithAbsoluteEpsilon(t, a, s1) |
| } |
| |
| // BrokenTestLowBiasedMerge is broken, see Merge doc comment. |
| func BrokenTestLowBiasedMerge(t *testing.T) { |
| rand.Seed(42) |
| s1 := NewLowBiased(RelativeEpsilon) |
| s2 := NewLowBiased(RelativeEpsilon) |
| a := populateStream(s1) |
| a = append(a, populateStream(s2)...) |
| s1.Merge(s2.Samples()) |
| verifyLowPercsWithRelativeEpsilon(t, a, s2) |
| } |
| |
| // BrokenTestHighBiasedMerge is broken, see Merge doc comment. |
| func BrokenTestHighBiasedMerge(t *testing.T) { |
| rand.Seed(42) |
| s1 := NewHighBiased(RelativeEpsilon) |
| s2 := NewHighBiased(RelativeEpsilon) |
| a := populateStream(s1) |
| a = append(a, populateStream(s2)...) |
| s1.Merge(s2.Samples()) |
| verifyHighPercsWithRelativeEpsilon(t, a, s2) |
| } |
| |
| func TestUncompressed(t *testing.T) { |
| q := NewTargeted(Targets) |
| for i := 100; i > 0; i-- { |
| q.Insert(float64(i)) |
| } |
| if g := q.Count(); g != 100 { |
| t.Errorf("want count 100, got %d", g) |
| } |
| // Before compression, Query should have 100% accuracy. |
| for quantile := range Targets { |
| w := quantile * 100 |
| if g := q.Query(quantile); g != w { |
| t.Errorf("want %f, got %f", w, g) |
| } |
| } |
| } |
| |
| func TestUncompressedSamples(t *testing.T) { |
| q := NewTargeted(map[float64]float64{0.99: 0.001}) |
| for i := 1; i <= 100; i++ { |
| q.Insert(float64(i)) |
| } |
| if g := q.Samples().Len(); g != 100 { |
| t.Errorf("want count 100, got %d", g) |
| } |
| } |
| |
| func TestUncompressedOne(t *testing.T) { |
| q := NewTargeted(map[float64]float64{0.99: 0.01}) |
| q.Insert(3.14) |
| if g := q.Query(0.90); g != 3.14 { |
| t.Error("want PI, got", g) |
| } |
| } |
| |
| func TestDefaults(t *testing.T) { |
| if g := NewTargeted(map[float64]float64{0.99: 0.001}).Query(0.99); g != 0 { |
| t.Errorf("want 0, got %f", g) |
| } |
| } |