79680739F9F00C…AFB4CFFA60F8

Arguments · 9

1. #1countminsketch
2. #2README.md
3. #3# `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`. ```go import "gno.land/p/moul/x/daily/countminsketch/v0" s := countminsketch.NewDefault() // 256 x 4 = 1024 counters, forever for _, e := range stream { s.Add(e) } s.Estimate("alice") // an UPPER BOUND on how often "alice" appeared s.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`](https://github.com/moul/gno-contracts/tree/main/r/moul/x/daily/countminsketchdemo/v0) · render it at [`/r/moul/x/daily/countminsketchdemo/v0`](https://gno.land/r/moul/x/daily/countminsketchdemo/v0). <!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) --> --- Part of **[moul/gno-contracts](https://github.com/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](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md). <!-- END GNOCONTRACTS FOOTER -->
4. #4countminsketch.gno
5. #5// 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). package countminsketch import "errors" const ( // MinWidth/MaxWidth bound each row. MinWidth = 4 MaxWidth = 8192 // MinDepth/MaxDepth bound the number of rows. MinDepth = 1 MaxDepth = 16 ) var ( ErrBadWidth = errors.New("countminsketch: width out of range") ErrBadDepth = errors.New("countminsketch: depth out of range") ErrBadCount = errors.New("countminsketch: count must be positive") ) // Sketch is a Count-Min Sketch over string elements. type Sketch struct { width int depth int rows [][]int64 // depth rows of width counters total int64 // sum of every increment applied adds int64 // number of Add/AddN calls applied } // New returns a sketch with the given dimensions. func New(width, depth int) (*Sketch, error) { if width < MinWidth || width > MaxWidth { return nil, ErrBadWidth } if depth < MinDepth || depth > MaxDepth { return nil, ErrBadDepth } rows := make([][]int64, depth) for i := range rows { rows[i] = make([]int64, width) } return &Sketch{width: width, depth: depth, rows: rows}, nil } // NewDefault returns a sketch sized for general use: 256 x 4. func NewDefault() *Sketch { s, _ := New(256, 4) return s } // Width returns the number of counters per row. func (s *Sketch) Width() int { return s.width } // Depth returns the number of rows. func (s *Sketch) Depth() int { return s.depth } // Counters returns the total number of counters — the fixed storage cost. func (s *Sketch) Counters() int { return s.width * s.depth } // Total returns the sum of every increment applied. func (s *Sketch) Total() int64 { return s.total } // Distinct is deliberately absent: a Count-Min Sketch cannot answer it. Use a // HyperLogLog for cardinality. // Add records one occurrence of e. func (s *Sketch) Add(e string) { s.AddN(e, 1) } // AddN records n occurrences of e. A non-positive n is ignored. func (s *Sketch) AddN(e string, n int64) error { if n <= 0 { return ErrBadCount } for r := 0; r < s.depth; r++ { s.rows[r][s.index(e, r)] += n } s.total += n s.adds++ return nil } // Estimate returns an UPPER BOUND on how often e was added. It never // undercounts; it may overcount when every row collided. func (s *Sketch) Estimate(e string) int64 { var min int64 = -1 for r := 0; r < s.depth; r++ { v := s.rows[r][s.index(e, r)] if min < 0 || v < min { min = v } } if min < 0 { return 0 } return min } // MightHave reports whether e may have been added. A false result is // definitive: it was never added. func (s *Sketch) MightHave(e string) bool { return s.Estimate(e) > 0 } // Merge adds another sketch into this one. Both must have identical dimensions; // merging is what makes sketches useful across shards or time windows. func (s *Sketch) Merge(other *Sketch) error { if s.width != other.width { return ErrBadWidth } if s.depth != other.depth { return ErrBadDepth } for r := 0; r < s.depth; r++ { for c := 0; c < s.width; c++ { s.rows[r][c] += other.rows[r][c] } } s.total += other.total s.adds += other.adds return nil } // Reset zeroes every counter, keeping the dimensions. func (s *Sketch) Reset() { for r := range s.rows { for c := range s.rows[r] { s.rows[r][c] = 0 } } s.total = 0 s.adds = 0 } // Clone returns an independent copy. func (s *Sketch) Clone() *Sketch { cp, _ := New(s.width, s.depth) for r := range s.rows { copy(cp.rows[r], s.rows[r]) } cp.total = s.total cp.adds = s.adds return cp } // Row returns a copy of row r, for rendering and inspection. func (s *Sketch) Row(r int) []int64 { if r < 0 || r >= s.depth { return nil } out := make([]int64, s.width) copy(out, s.rows[r]) return out } // Index returns the column e maps to in row r — exported so a demo can show // where collisions happen. func (s *Sketch) Index(e string, r int) int { if r < 0 || r >= s.depth { return -1 } return s.index(e, r) } // index hashes e for row r with FNV-1a, seeded per row. func (s *Sketch) index(e string, row int) int { const ( offset64 = uint64(14695981039346656037) prime64 = uint64(1099511628211) ) h := offset64 // Seed the row so each row hashes independently. h ^= uint64(row + 1) h *= prime64 for i := 0; i < len(e); i++ { h ^= uint64(e[i]) h *= prime64 } return int(h % uint64(s.width)) }
6. #6gnomod.toml
7. #7module = "gno.land/p/moul/x/daily/countminsketch/v0" gno = "0.9"
8. #8/gno.MemPackageType
9. #9 MPUserProd