1// Package countminsketch estimates element frequencies in sublinear space, as2// a pure, reusable package.3//4// An exact frequency map costs one entry per distinct element, which on chain5// means unbounded storage driven by whatever users feed it. A Count-Min Sketch6// trades exactness for a FIXED footprint: d rows of w counters, sized once and7// never grown, regardless of how many distinct elements arrive.8//9// The error is one-sided and that is the whole contract: Estimate NEVER10// UNDERCOUNTS. Collisions can only add other elements' counts to a row, so the11// true frequency is always <= the estimate. Taking the minimum across d12// independent rows makes an overestimate require a collision in every row at13// once. Callers must treat the result as an upper bound — "at most this often",14// never "exactly this often".15//16// Sizing: width controls the error, depth controls the odds of hitting it.17// Roughly, the overestimate stays within total/width with probability18// 1 - (1/2)^depth.19//20// Hashing is FNV-1a with a per-row seed, computed in pure gno — deterministic21// across every node, which a map-address-derived hash would not be.22//23// A live demo of this package is at24// [r/moul/x/daily/countminsketchdemo](/r/moul/x/daily/countminsketchdemo/v0).25package countminsketch2627import "errors"2829const (30 // MinWidth/MaxWidth bound each row.31 MinWidth = 432 MaxWidth = 819233 // MinDepth/MaxDepth bound the number of rows.34 MinDepth = 135 MaxDepth = 1636)3738var (39 ErrBadWidth = errors.New("countminsketch: width out of range")40 ErrBadDepth = errors.New("countminsketch: depth out of range")41 ErrBadCount = errors.New("countminsketch: count must be positive")42)4344// Sketch is a Count-Min Sketch over string elements.45type Sketch struct {46 width int47 depth int48 rows [][]int64 // depth rows of width counters49 total int64 // sum of every increment applied50 adds int64 // number of Add/AddN calls applied51}5253// New returns a sketch with the given dimensions.54func New(width, depth int) (*Sketch, error) {55 if width < MinWidth || width > MaxWidth {56 return nil, ErrBadWidth57 }58 if depth < MinDepth || depth > MaxDepth {59 return nil, ErrBadDepth60 }61 rows := make([][]int64, depth)62 for i := range rows {63 rows[i] = make([]int64, width)64 }65 return &Sketch{width: width, depth: depth, rows: rows}, nil66}6768// NewDefault returns a sketch sized for general use: 256 x 4.69func NewDefault() *Sketch {70 s, _ := New(256, 4)71 return s72}7374// Width returns the number of counters per row.75func (s *Sketch) Width() int { return s.width }7677// Depth returns the number of rows.78func (s *Sketch) Depth() int { return s.depth }7980// Counters returns the total number of counters — the fixed storage cost.81func (s *Sketch) Counters() int { return s.width * s.depth }8283// Total returns the sum of every increment applied.84func (s *Sketch) Total() int64 { return s.total }8586// Distinct is deliberately absent: a Count-Min Sketch cannot answer it. Use a87// HyperLogLog for cardinality.8889// Add records one occurrence of e.90func (s *Sketch) Add(e string) { s.AddN(e, 1) }9192// AddN records n occurrences of e. A non-positive n is ignored.93func (s *Sketch) AddN(e string, n int64) error {94 if n <= 0 {95 return ErrBadCount96 }97 for r := 0; r < s.depth; r++ {98 s.rows[r][s.index(e, r)] += n99 }100 s.total += n101 s.adds++102 return nil103}104105// Estimate returns an UPPER BOUND on how often e was added. It never106// undercounts; it may overcount when every row collided.107func (s *Sketch) Estimate(e string) int64 {108 var min int64 = -1109 for r := 0; r < s.depth; r++ {110 v := s.rows[r][s.index(e, r)]111 if min < 0 || v < min {112 min = v113 }114 }115 if min < 0 {116 return 0117 }118 return min119}120121// MightHave reports whether e may have been added. A false result is122// definitive: it was never added.123func (s *Sketch) MightHave(e string) bool { return s.Estimate(e) > 0 }124125// Merge adds another sketch into this one. Both must have identical dimensions;126// merging is what makes sketches useful across shards or time windows.127func (s *Sketch) Merge(other *Sketch) error {128 if s.width != other.width {129 return ErrBadWidth130 }131 if s.depth != other.depth {132 return ErrBadDepth133 }134 for r := 0; r < s.depth; r++ {135 for c := 0; c < s.width; c++ {136 s.rows[r][c] += other.rows[r][c]137 }138 }139 s.total += other.total140 s.adds += other.adds141 return nil142}143144// Reset zeroes every counter, keeping the dimensions.145func (s *Sketch) Reset() {146 for r := range s.rows {147 for c := range s.rows[r] {148 s.rows[r][c] = 0149 }150 }151 s.total = 0152 s.adds = 0153}154155// Clone returns an independent copy.156func (s *Sketch) Clone() *Sketch {157 cp, _ := New(s.width, s.depth)158 for r := range s.rows {159 copy(cp.rows[r], s.rows[r])160 }161 cp.total = s.total162 cp.adds = s.adds163 return cp164}165166// Row returns a copy of row r, for rendering and inspection.167func (s *Sketch) Row(r int) []int64 {168 if r < 0 || r >= s.depth {169 return nil170 }171 out := make([]int64, s.width)172 copy(out, s.rows[r])173 return out174}175176// Index returns the column e maps to in row r — exported so a demo can show177// where collisions happen.178func (s *Sketch) Index(e string, r int) int {179 if r < 0 || r >= s.depth {180 return -1181 }182 return s.index(e, r)183}184185// index hashes e for row r with FNV-1a, seeded per row.186func (s *Sketch) index(e string, row int) int {187 const (188 offset64 = uint64(14695981039346656037)189 prime64 = uint64(1099511628211)190 )191 h := offset64192 // Seed the row so each row hashes independently.193 h ^= uint64(row + 1)194 h *= prime64195 for i := 0; i < len(e); i++ {196 h ^= uint64(e[i])197 h *= prime64198 }199 return int(h % uint64(s.width))200}201Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.