v0 source pure
Package countminsketch estimates element frequencies in sublinear space, as a pure, reusable package.
View source
gno.land/p/moul/x/daily/countminsketch/v0
Count–Min Sketch: frequency estimates in fixed space — New, NewDefault,
Add, AddN, Estimate, MightHave, Merge, Reset, Clone, Row,
Index, Total, Counters.
1import "gno.land/p/moul/x/daily/countminsketch/v0"
2
3s := countminsketch.NewDefault() // 256 x 4 = 1024 counters, forever
4for _, e := range stream { s.Add(e) }
5s.Estimate("alice") // an UPPER BOUND on how often "alice" appeared
6s.MightHave("bob") // false is definitive: never added
An exact frequency map costs one entry per distinct element — unbounded storage driven by whatever users feed it, which on chain is a liability. A sketch is sized once and never grows.
The error is one-sided, and that is the whole contract: Estimate never
undercounts. Collisions can only add other elements' counts to a row, so the
true frequency is always ≤ the estimate. Taking the minimum across depth
independently-seeded rows makes an overestimate require a collision in every row
at once. Treat the result as "at most this often", never "exactly this
often". The guarantee is tested against a deliberately tiny sketch where
collisions are certain.
Sizing: width controls the error, depth controls the odds of hitting it —
roughly, the overestimate stays within total/width with probability
1 - (1/2)^depth.
Hashing is FNV-1a with a per-row seed, computed in pure gno, so the counters are
identical on every node. Distinct() is deliberately absent — a Count–Min Sketch
cannot answer cardinality; use a HyperLogLog.
Live demo: r/moul/x/daily/countminsketchdemo
· render it at /r/moul/x/daily/countminsketchdemo/v0.
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.
Package countminsketch estimates element frequencies in sublinear space, as a pure, reusable package.
An exact frequency map costs one entry per distinct element, which on chain means unbounded storage driven by whatever users feed it. A Count-Min Sketch trades exactness for a FIXED footprint: d rows of w counters, sized once and never grown, regardless of how many distinct elements arrive.
The error is one-sided and that is the whole contract: Estimate NEVER UNDERCOUNTS. Collisions can only add other elements' counts to a row, so the true frequency is always <= the estimate. Taking the minimum across d independent rows makes an overestimate require a collision in every row at once. Callers must treat the result as an upper bound — "at most this often", never "exactly this often".
Sizing: width controls the error, depth controls the odds of hitting it. Roughly, the overestimate stays within total/width with probability 1 - (1/2)^depth.
Hashing is FNV-1a with a per-row seed, computed in pure gno — deterministic across every node, which a map-address-derived hash would not be.
A live demo of this package is at r/moul/x/daily/countminsketchdemo(/r/moul/x/daily/countminsketchdemo/v0).
1
1
2
1
type Sketch
structSketch is a Count-Min Sketch over string elements.
Methods on Sketch
func Add
method on SketchAdd records one occurrence of e.
func AddN
method on SketchAddN records n occurrences of e. A non-positive n is ignored.
func Clone
method on SketchClone returns an independent copy.
func Counters
method on SketchCounters returns the total number of counters — the fixed storage cost.
func Depth
method on SketchDepth returns the number of rows.
func Estimate
method on SketchEstimate returns an UPPER BOUND on how often e was added. It never undercounts; it may overcount when every row collided.
func Index
method on SketchIndex returns the column e maps to in row r — exported so a demo can show where collisions happen.
func Merge
method on SketchMerge adds another sketch into this one. Both must have identical dimensions; merging is what makes sketches useful across shards or time windows.
func MightHave
method on SketchMightHave reports whether e may have been added. A false result is definitive: it was never added.
func Reset
method on SketchReset zeroes every counter, keeping the dimensions.
func Row
method on SketchRow returns a copy of row r, for rendering and inspection.
func Total
method on SketchTotal returns the sum of every increment applied.
func Width
method on SketchWidth returns the number of counters per row.
1
- errors stdlib