sketch_count_sketch_test.nx source
↩ module page · 113 lines · 3891 B
1// sketch_count_sketch_test.nx -- CountSketch (unbiased frequency) verification.
2
3import "syscalls.nx"
4import "sketch_count_sketch.nx"
5import "sketch_types.nx"
6
7func iabs(x: i64) -> i64 {
8 if x < 0 { return -x }
9 return x
10}
11
12func main() -> i64 {
13 // ---- alloc ----
14 let cs: *CountSketch = nx_cs_alloc(5, 1024, 42)
15 if cs == (0 as *CountSketch) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 // Reject non-power-of-2 width.
17 if nx_cs_alloc(5, 1000, 1) != (0 as *CountSketch) {
18 return __syscall(93, 6, 0, 0, 0, 0, 0)
19 }
20 // Reject d too small.
21 if nx_cs_alloc(2, 1024, 1) != (0 as *CountSketch) {
22 return __syscall(93, 7, 0, 0, 0, 0, 0)
23 }
24
25 // ---- empty: estimate = 0 ----
26 if nx_cs_estimate(cs, 123) != 0 {
27 return __syscall(93, 10, 0, 0, 0, 0, 0)
28 }
29
30 // ---- single insert: exact recall for sparse input ----
31 nx_cs_add(cs, 100, 50)
32 let est100: i64 = nx_cs_estimate(cs, 100)
33 if est100 != 50 { // sparse stream -> no collisions -> exact
34 return __syscall(93, 20, 0, 0, 0, 0, 0)
35 }
36
37 // ---- unbiased property: many inserts, average error ~ 0 ----
38 // Insert keys 1..1000 each with count 1. Then query key 500.
39 // Expected: estimate near 1 (within bounded error). Critically,
40 // bias should be small (CMS would tend to OVERESTIMATE; CountSketch
41 // gives UNBIASED).
42 let cs2: *CountSketch = nx_cs_alloc(7, 4096, 7)
43 var i: i64 = 1
44 while i <= 1000 {
45 nx_cs_add(cs2, i, 1)
46 i = i + 1
47 }
48 let est500: i64 = nx_cs_estimate(cs2, 500)
49 // True count = 1. Error bound: total/sqrt(w) = 1000/sqrt(4096) = 1000/64 = 15.6.
50 if iabs(est500 - 1) > 16 {
51 return __syscall(93, 30, 0, 0, 0, 0, 0)
52 }
53
54 // Unknown key (not inserted): expected estimate near 0.
55 let est_unknown: i64 = nx_cs_estimate(cs2, 9999)
56 if iabs(est_unknown) > 16 {
57 return __syscall(93, 31, 0, 0, 0, 0, 0)
58 }
59
60 // ---- heavy hitter: dominant key recovered ----
61 nx_cs_add(cs2, 42, 5000) // huge weight to key 42
62 let est42: i64 = nx_cs_estimate(cs2, 42)
63 // True count = 5000. Bound now total/sqrt(w) = 6000/64 = ~94.
64 if iabs(est42 - 5000) > 200 {
65 return __syscall(93, 40, 0, 0, 0, 0, 0)
66 }
67
68 // ---- typed envelope ----
69 let q: *ApproxI64 = nx_cs_query(cs2, 42)
70 if q.envelope_kind != NX_ENV_ABS {
71 return __syscall(93, 50, 0, 0, 0, 0, 0)
72 }
73 // param_a = total/isqrt(w) = 6000/64 = 93.
74 if iabs(q.param_a - 93) > 5 {
75 return __syscall(93, 51, 0, 0, 0, 0, 0)
76 }
77 // d=7 -> conf_ppb = 316_400_000 confidence, so envelope = 1e9 - that.
78 if iabs(q.conf_ppb - 683600000) > 1000 {
79 return __syscall(93, 52, 0, 0, 0, 0, 0)
80 }
81
82 // ---- merge ----
83 let m_a: *CountSketch = nx_cs_alloc(5, 1024, 99)
84 let m_b: *CountSketch = nx_cs_alloc(5, 1024, 99)
85 nx_cs_add(m_a, 7, 100)
86 nx_cs_add(m_b, 7, 200)
87 let merged: *CountSketch = nx_cs_merge(m_a, m_b)
88 if merged == (0 as *CountSketch) {
89 return __syscall(93, 60, 0, 0, 0, 0, 0)
90 }
91 let est7: i64 = nx_cs_estimate(merged, 7)
92 if iabs(est7 - 300) > 10 {
93 return __syscall(93, 61, 0, 0, 0, 0, 0)
94 }
95 // Mismatched w -> NULL.
96 let m_c: *CountSketch = nx_cs_alloc(5, 2048, 99)
97 if nx_cs_merge(m_a, m_c) != (0 as *CountSketch) {
98 return __syscall(93, 62, 0, 0, 0, 0, 0)
99 }
100
101 // ---- decrement ----
102 // CountSketch supports NEGATIVE counts (unlike CMS). Add then
103 // subtract should net to ~0.
104 let cs3: *CountSketch = nx_cs_alloc(5, 1024, 1)
105 nx_cs_add(cs3, 555, 100)
106 nx_cs_add(cs3, 555, -100)
107 let est555: i64 = nx_cs_estimate(cs3, 555)
108 if iabs(est555) > 10 {
109 return __syscall(93, 70, 0, 0, 0, 0, 0)
110 }
111
112 return 0
113}