gno.land/r/moul/x/daily/countminsketchdemo/v0⧉

1// Package countminsketchdemo is a small gnoweb demo of the frequency sketch2// provided by the3// [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 is7// deterministic — which is precisely what the library is for.8package countminsketchdemo910import (11	"strconv"12	"strings"1314	"gno.land/p/moul/x/daily/countminsketch/v0"15)1617// stream is the workload: a few heavy hitters and a long tail.18var stream = buildStream()1920func buildStream() []string {21	var out []string22	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-offs32		out = append(out, "user"+strconv.Itoa(i))33	}34	return out35}3637// Render renders the demo for gnoweb.38func Render(path string) string {39	var b strings.Builder40	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")4344	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")4748	big, _ := countminsketch.New(1024, 4)49	fill(big)5051	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")5960	tiny, _ := countminsketch.New(8, 2)61	fill(tiny)6263	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")7677	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")9596	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}105106func fill(s *countminsketch.Sketch) {107	for _, e := range stream {108		s.Add(e)109	}110}111112func trueCount(k string) int {113	n := 0114	for _, e := range stream {115		if e == k {116			n++117		}118	}119	return n120}121