Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

render_example_test.gno

2.00 Kb · 65 lines
 1package countminsketchdemo
 2
 3// ExampleRender pins the realm's Render output as a testable example.
 4func ExampleRender() {
 5	print(Render(""))
 6	// Output:
 7	// # Count–Min Sketch
 8	//
 9	// Frequency estimates in fixed space, demoing the [`p/moul/x/daily/countminsketch`](/p/moul/x/daily/countminsketch/v0) library.
10	//
11	// ## The workload
12	//
13	// `195` events over `123` distinct keys: three heavy hitters and a long tail of one-offs.
14	//
15	// ## A generously sized sketch (1024 × 4)
16	//
17	// | key | true | estimate |
18	// |---|---|---|
19	// | `alice` | 40 | 40 |
20	// | `bob` | 25 | 25 |
21	// | `carol` | 10 | 10 |
22	// | `user0` | 1 | 1 |
23	// | `never-seen` | 0 | 0 |
24	//
25	// Exact here, and `never-seen` reads `0` — a **zero estimate is definitive**: that key was never added.
26	//
27	// ## A deliberately tiny one (8 × 2)
28	//
29	// Only `16` counters for `123` distinct keys, so collisions are guaranteed:
30	//
31	// | key | true | estimate | error |
32	// |---|---|---|---|
33	// | `alice` | 40 | 54 | +14 |
34	// | `bob` | 25 | 39 | +14 |
35	// | `carol` | 10 | 24 | +14 |
36	// | `user0` | 1 | 16 | +15 |
37	//
38	// Every error is **positive**. That is the guarantee: the sketch may overcount, never undercount, so an estimate is an upper bound — "at most this often", never "exactly this often".
39	//
40	// ## Where the collisions are
41	//
42	// Row 0 of the tiny sketch, and the column each key lands in:
43	//
44	// | column | counter |
45	// |---|---|
46	// | 0 | 15 |
47	// | 1 | 25 ← `carol` |
48	// | 2 | 16 |
49	// | 3 | 15 |
50	// | 4 | 54 ← `alice` |
51	// | 5 | 16 |
52	// | 6 | 15 |
53	// | 7 | 39 ← `bob` |
54	//
55	// Taking the **minimum** across rows is what limits the damage: an overestimate needs a collision in *every* row at once.
56	//
57	// ## Why bother
58	//
59	// | | exact map | sketch (1024 × 4) |
60	// |---|---|---|
61	// | storage | one entry per distinct key, unbounded | 4096 counters, fixed |
62	// | answer | exact | upper bound |
63	//
64	// On chain the second row is the point: storage driven by user input is a liability, and a sketch sized once cannot be made to grow.
65}