sketch_varopt_test.nx source
↩ module page · 111 lines · 3917 B
1// sketch_varopt_test.nx -- Weighted reservoir sampling verification.
2
3import "syscalls.nx"
4import "sketch_varopt.nx"
5import "sketch_types.nx"
6
7func main() -> i64 {
8 // ---- alloc + empty ----
9 let v: *VarOpt = nx_varopt_alloc(64, 42)
10 if v == (0 as *VarOpt) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
11 if v.n_items != 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
12 if v.total_weight != 0 { return __syscall(93, 7, 0, 0, 0, 0, 0) }
13 // Reject K below min.
14 if nx_varopt_alloc(2, 1) != (0 as *VarOpt) {
15 return __syscall(93, 8, 0, 0, 0, 0, 0)
16 }
17
18 // ---- under-cap: every item retained ----
19 var i: i64 = 0
20 while i < 30 {
21 nx_varopt_add(v, i + 1, 1) // item i+1 with weight 1
22 i = i + 1
23 }
24 if v.n_items != 30 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
25 if v.total_seen != 30 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
26 if v.total_weight != 30 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
27 // Sorted-descending invariant.
28 i = 1
29 while i < v.n_items {
30 let prev: *VoptEntry = nx_varopt_entry_at(v, i - 1)
31 let cur: *VoptEntry = nx_varopt_entry_at(v, i)
32 if prev.key < cur.key {
33 return __syscall(93, 23, 0, 0, 0, 0, 0)
34 }
35 i = i + 1
36 }
37
38 // ---- streaming past cap: heavy items survive more often ----
39 // Setup: stream 1000 items. Heavy items (item % 50 == 0) get
40 // weight 1000; rest weight 1. K = 32. Expect heavy items to
41 // dominate the retained sample.
42 let v2: *VarOpt = nx_varopt_alloc(32, 7)
43 i = 1
44 while i <= 1000 {
45 var w: i64 = 1
46 if (i % 50) == 0 { w = 1000 }
47 nx_varopt_add(v2, i, w)
48 i = i + 1
49 }
50 if v2.n_items != 32 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
51 if v2.total_seen != 1000 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
52 // Count how many retained items have weight 1000 (heavy).
53 // Heavy items in stream: 20. Light: 980. With weighted sampling,
54 // heavy should be over-represented vs uniform. Uniform would
55 // give ~32 * 20/1000 = 0.64 heavy items. Weighted should give
56 // many more. We expect at least 5 heavy items in the sample.
57 var heavy_count: i64 = 0
58 i = 0
59 while i < v2.n_items {
60 let e: *VoptEntry = nx_varopt_entry_at(v2, i)
61 if e.weight == 1000 { heavy_count = heavy_count + 1 }
62 i = i + 1
63 }
64 if heavy_count < 5 {
65 return __syscall(93, 32, 0, 0, 0, 0, 0)
66 }
67 // And we shouldn't have ALL slots heavy (would mean total saturation):
68 if heavy_count > 25 {
69 return __syscall(93, 33, 0, 0, 0, 0, 0)
70 }
71
72 // ---- determinism: same seed + sequence -> identical samples ----
73 let v3a: *VarOpt = nx_varopt_alloc(16, 99)
74 let v3b: *VarOpt = nx_varopt_alloc(16, 99)
75 i = 1
76 while i <= 200 {
77 let w: i64 = (i % 5) + 1 // weights 1..5 cycling
78 nx_varopt_add(v3a, i, w)
79 nx_varopt_add(v3b, i, w)
80 i = i + 1
81 }
82 i = 0
83 while i < 16 {
84 let ea: *VoptEntry = nx_varopt_entry_at(v3a, i)
85 let eb: *VoptEntry = nx_varopt_entry_at(v3b, i)
86 if ea.item != eb.item {
87 return __syscall(93, 40, 0, 0, 0, 0, 0)
88 }
89 if ea.weight != eb.weight {
90 return __syscall(93, 41, 0, 0, 0, 0, 0)
91 }
92 if ea.key != eb.key {
93 return __syscall(93, 42, 0, 0, 0, 0, 0)
94 }
95 i = i + 1
96 }
97
98 // ---- envelope ----
99 let q: *ApproxI64 = nx_varopt_query_mean(v2)
100 if q.envelope_kind != NX_ENV_REL_STDDEV {
101 return __syscall(93, 50, 0, 0, 0, 0, 0)
102 }
103 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
104 return __syscall(93, 51, 0, 0, 0, 0, 0)
105 }
106 if q.adv_safety != NX_ADV_HONEST {
107 return __syscall(93, 52, 0, 0, 0, 0, 0)
108 }
109
110 return 0
111}