Realm

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}
121