| 1 | package analytics |
| 2 | |
| 3 | import ( |
| 4 | "hash/fnv" |
| 5 | "math" |
| 6 | "strconv" |
| 7 | "testing" |
| 8 | ) |
| 9 | |
| 10 | func h64(s string) uint64 { f := fnv.New64a(); f.Write([]byte(s)); return f.Sum64() } |
| 11 | |
| 12 | func TestHLLEstimatesWithinThreeSigma(t *testing.T) { |
| 13 | for _, n := range []int{1000, 10000, 100000} { |
| 14 | var h HLL |
| 15 | for i := 0; i < n; i++ { |
| 16 | h.Add(h64("v" + itoa(i))) |
| 17 | } |
| 18 | got := h.Count() |
| 19 | sigma := 1.04 / math.Sqrt(hllRegisters) * float64(n) |
| 20 | if math.Abs(got-float64(n)) > 3*sigma { |
| 21 | t.Errorf("n=%d: estimate %.0f off by more than 3σ (%.0f)", n, got, 3*sigma) |
| 22 | } |
| 23 | } |
| 24 | } |
| 25 | |
| 26 | func TestHLLMergeIsUnionAndIdempotent(t *testing.T) { |
| 27 | var a, b HLL |
| 28 | for i := 0; i < 5000; i++ { |
| 29 | a.Add(h64("a" + itoa(i))) |
| 30 | b.Add(h64("b" + itoa(i))) |
| 31 | } |
| 32 | var ab HLL |
| 33 | ab.Merge(&a) |
| 34 | ab.Merge(&b) |
| 35 | ab.Merge(&b) // idempotent |
| 36 | if got := ab.Count(); math.Abs(got-10000) > 3*(1.04/math.Sqrt(hllRegisters))*10000 { |
| 37 | t.Fatalf("union estimate %.0f", got) |
| 38 | } |
| 39 | var ba HLL |
| 40 | ba.Merge(&b) |
| 41 | ba.Merge(&a) |
| 42 | if ab.reg != ba.reg { |
| 43 | t.Fatal("merge must be commutative") |
| 44 | } |
| 45 | } |
| 46 | |
| 47 | func TestHLLEncodeRoundTripAndVersion(t *testing.T) { |
| 48 | var h HLL |
| 49 | h.Add(h64("x")) |
| 50 | enc := h.Encode() |
| 51 | if enc[:2] != "AQ" { // base64 of a leading 0x01 byte |
| 52 | t.Fatalf("version prefix missing: %q", enc[:4]) |
| 53 | } |
| 54 | d, err := DecodeHLL(enc) |
| 55 | if err != nil || d.reg != h.reg { |
| 56 | t.Fatalf("round trip: %v", err) |
| 57 | } |
| 58 | if e, err := DecodeHLL(""); err != nil || !e.Empty() { |
| 59 | t.Fatal("empty string must decode to an empty sketch") |
| 60 | } |
| 61 | if _, err := DecodeHLL("AgAA"); err == nil { |
| 62 | t.Fatal("unknown version must error") |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | // itoa is the brief's crude helper, replaced with strconv.Itoa: the |
| 67 | // original digit-reversed encoding broke TestTopKExactBelowCapAndBoundedAbove's |
| 68 | // key lookups (itoa(99) produced "990000", not "99") and had weaker |
| 69 | // diversity in leading digits than strconv's ordinary decimal, which |
| 70 | // stressed the HLL register-index entropy (see hll.go's mix64 note). |
| 71 | func itoa(i int) string { return strconv.Itoa(i) } |
| 72 | |
amadan