countminsketch.gno
5.44 Kb · 200 lines
1// Package countminsketch estimates element frequencies in sublinear space, as
2// a pure, reusable package.
3//
4// An exact frequency map costs one entry per distinct element, which on chain
5// means unbounded storage driven by whatever users feed it. A Count-Min Sketch
6// trades exactness for a FIXED footprint: d rows of w counters, sized once and
7// never grown, regardless of how many distinct elements arrive.
8//
9// The error is one-sided and that is the whole contract: Estimate NEVER
10// UNDERCOUNTS. Collisions can only add other elements' counts to a row, so the
11// true frequency is always <= the estimate. Taking the minimum across d
12// independent rows makes an overestimate require a collision in every row at
13// 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 probability
18// 1 - (1/2)^depth.
19//
20// Hashing is FNV-1a with a per-row seed, computed in pure gno — deterministic
21// across every node, which a map-address-derived hash would not be.
22//
23// A live demo of this package is at
24// [r/moul/x/daily/countminsketchdemo](/r/moul/x/daily/countminsketchdemo/v0).
25package countminsketch
26
27import "errors"
28
29const (
30 // MinWidth/MaxWidth bound each row.
31 MinWidth = 4
32 MaxWidth = 8192
33 // MinDepth/MaxDepth bound the number of rows.
34 MinDepth = 1
35 MaxDepth = 16
36)
37
38var (
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)
43
44// Sketch is a Count-Min Sketch over string elements.
45type Sketch struct {
46 width int
47 depth int
48 rows [][]int64 // depth rows of width counters
49 total int64 // sum of every increment applied
50 adds int64 // number of Add/AddN calls applied
51}
52
53// New returns a sketch with the given dimensions.
54func New(width, depth int) (*Sketch, error) {
55 if width < MinWidth || width > MaxWidth {
56 return nil, ErrBadWidth
57 }
58 if depth < MinDepth || depth > MaxDepth {
59 return nil, ErrBadDepth
60 }
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}, nil
66}
67
68// NewDefault returns a sketch sized for general use: 256 x 4.
69func NewDefault() *Sketch {
70 s, _ := New(256, 4)
71 return s
72}
73
74// Width returns the number of counters per row.
75func (s *Sketch) Width() int { return s.width }
76
77// Depth returns the number of rows.
78func (s *Sketch) Depth() int { return s.depth }
79
80// Counters returns the total number of counters — the fixed storage cost.
81func (s *Sketch) Counters() int { return s.width * s.depth }
82
83// Total returns the sum of every increment applied.
84func (s *Sketch) Total() int64 { return s.total }
85
86// Distinct is deliberately absent: a Count-Min Sketch cannot answer it. Use a
87// HyperLogLog for cardinality.
88
89// Add records one occurrence of e.
90func (s *Sketch) Add(e string) { s.AddN(e, 1) }
91
92// 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 ErrBadCount
96 }
97 for r := 0; r < s.depth; r++ {
98 s.rows[r][s.index(e, r)] += n
99 }
100 s.total += n
101 s.adds++
102 return nil
103}
104
105// Estimate returns an UPPER BOUND on how often e was added. It never
106// undercounts; it may overcount when every row collided.
107func (s *Sketch) Estimate(e string) int64 {
108 var min int64 = -1
109 for r := 0; r < s.depth; r++ {
110 v := s.rows[r][s.index(e, r)]
111 if min < 0 || v < min {
112 min = v
113 }
114 }
115 if min < 0 {
116 return 0
117 }
118 return min
119}
120
121// MightHave reports whether e may have been added. A false result is
122// definitive: it was never added.
123func (s *Sketch) MightHave(e string) bool { return s.Estimate(e) > 0 }
124
125// 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 ErrBadWidth
130 }
131 if s.depth != other.depth {
132 return ErrBadDepth
133 }
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.total
140 s.adds += other.adds
141 return nil
142}
143
144// 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] = 0
149 }
150 }
151 s.total = 0
152 s.adds = 0
153}
154
155// 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.total
162 cp.adds = s.adds
163 return cp
164}
165
166// 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 nil
170 }
171 out := make([]int64, s.width)
172 copy(out, s.rows[r])
173 return out
174}
175
176// Index returns the column e maps to in row r — exported so a demo can show
177// where collisions happen.
178func (s *Sketch) Index(e string, r int) int {
179 if r < 0 || r >= s.depth {
180 return -1
181 }
182 return s.index(e, r)
183}
184
185// 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 := offset64
192 // Seed the row so each row hashes independently.
193 h ^= uint64(row + 1)
194 h *= prime64
195 for i := 0; i < len(e); i++ {
196 h ^= uint64(e[i])
197 h *= prime64
198 }
199 return int(h % uint64(s.width))
200}
