countminsketchdemo.gno

  1// Package countminsketchdemo is a small gnoweb demo of the frequency sketch
  2// provided by the
  3// [p/moul/x/daily/countminsketch](/p/moul/x/daily/countminsketch/v0) library:
  4// fixed storage, one-sided error, and what a collision looks like.
  5//
  6// It contains no sketch logic of its own. Stateless, so Render is
  7// deterministic — which is precisely what the library is for.
  8package countminsketchdemo
  9
 10import (
 11	"strconv"
 12	"strings"
 13
 14	"gno.land/p/moul/x/daily/countminsketch/v0"
 15)
 16
 17// stream is the workload: a few heavy hitters and a long tail.
 18var stream = buildStream()
 19
 20func buildStream() []string {
 21	var out []string
 22	for i := 0; i < 40; i++ {
 23		out = append(out, "alice")
 24	}
 25	for i := 0; i < 25; i++ {
 26		out = append(out, "bob")
 27	}
 28	for i := 0; i < 10; i++ {
 29		out = append(out, "carol")
 30	}
 31	for i := 0; i < 120; i++ { // the tail: 120 distinct one-offs
 32		out = append(out, "user"+strconv.Itoa(i))
 33	}
 34	return out
 35}
 36
 37// Render renders the demo for gnoweb.
 38func Render(path string) string {
 39	var b strings.Builder
 40	b.WriteString("# Count–Min Sketch\n\n")
 41	b.WriteString("Frequency estimates in fixed space, demoing the ")
 42	b.WriteString("[`p/moul/x/daily/countminsketch`](/p/moul/x/daily/countminsketch/v0) library.\n\n")
 43
 44	b.WriteString("## The workload\n\n")
 45	b.WriteString("`" + strconv.Itoa(len(stream)) + "` events over `123` distinct keys: ")
 46	b.WriteString("three heavy hitters and a long tail of one-offs.\n\n")
 47
 48	big, _ := countminsketch.New(1024, 4)
 49	fill(big)
 50
 51	b.WriteString("## A generously sized sketch (1024 × 4)\n\n")
 52	b.WriteString("| key | true | estimate |\n|---|---|---|\n")
 53	for _, k := range []string{"alice", "bob", "carol", "user0", "never-seen"} {
 54		b.WriteString("| `" + k + "` | " + strconv.Itoa(trueCount(k)) + " | " +
 55			strconv.FormatInt(big.Estimate(k), 10) + " |\n")
 56	}
 57	b.WriteString("\nExact here, and `never-seen` reads `0` — a **zero estimate is ")
 58	b.WriteString("definitive**: that key was never added.\n\n")
 59
 60	tiny, _ := countminsketch.New(8, 2)
 61	fill(tiny)
 62
 63	b.WriteString("## A deliberately tiny one (8 × 2)\n\n")
 64	b.WriteString("Only `" + strconv.Itoa(tiny.Counters()) + "` counters for `123` distinct ")
 65	b.WriteString("keys, so collisions are guaranteed:\n\n")
 66	b.WriteString("| key | true | estimate | error |\n|---|---|---|---|\n")
 67	for _, k := range []string{"alice", "bob", "carol", "user0"} {
 68		est := tiny.Estimate(k)
 69		b.WriteString("| `" + k + "` | " + strconv.Itoa(trueCount(k)) + " | " +
 70			strconv.FormatInt(est, 10) + " | +" +
 71			strconv.FormatInt(est-int64(trueCount(k)), 10) + " |\n")
 72	}
 73	b.WriteString("\nEvery error is **positive**. That is the guarantee: the sketch may ")
 74	b.WriteString("overcount, never undercount, so an estimate is an upper bound — ")
 75	b.WriteString("\"at most this often\", never \"exactly this often\".\n\n")
 76
 77	b.WriteString("## Where the collisions are\n\n")
 78	b.WriteString("Row 0 of the tiny sketch, and the column each key lands in:\n\n")
 79	b.WriteString("| column | counter |\n|---|---|\n")
 80	for c, v := range tiny.Row(0) {
 81		who := []string{}
 82		for _, k := range []string{"alice", "bob", "carol"} {
 83			if tiny.Index(k, 0) == c {
 84				who = append(who, "`"+k+"`")
 85			}
 86		}
 87		line := "| " + strconv.Itoa(c) + " | " + strconv.FormatInt(v, 10)
 88		if len(who) > 0 {
 89			line += " ← " + strings.Join(who, ", ")
 90		}
 91		b.WriteString(line + " |\n")
 92	}
 93	b.WriteString("\nTaking the **minimum** across rows is what limits the damage: an ")
 94	b.WriteString("overestimate needs a collision in *every* row at once.\n\n")
 95
 96	b.WriteString("## Why bother\n\n")
 97	b.WriteString("| | exact map | sketch (1024 × 4) |\n|---|---|---|\n")
 98	b.WriteString("| storage | one entry per distinct key, unbounded | ")
 99	b.WriteString(strconv.Itoa(big.Counters()) + " counters, fixed |\n")
100	b.WriteString("| answer | exact | upper bound |\n")
101	b.WriteString("\nOn chain the second row is the point: storage driven by user input ")
102	b.WriteString("is a liability, and a sketch sized once cannot be made to grow.\n")
103	return b.String()
104}
105
106func fill(s *countminsketch.Sketch) {
107	for _, e := range stream {
108		s.Add(e)
109	}
110}
111
112func trueCount(k string) int {
113	n := 0
114	for _, e := range stream {
115		if e == k {
116			n++
117		}
118	}
119	return n
120}