sketch_varopt.nx

sketch_varopt.nx -- Weighted reservoir sampling (Efraimidis-Spirakis 2006 / Cohen 2011). Given a stream of (item, weight) arrivals, maintain a reservoir of size k such that the inclusion probability is proportional to weight. Heavy items more likely to be retained than light. COMPLETES THE SAMPLING FAMILY: - Reservoir (Vitter 1985): uniform sampling, equal weights. - VarOpt (here): weighted sampling. ALGORITHM (A-ExpJ variant of A-Res): For each (item, w): generate key = u^(1/w) where u ~ Uniform(0,1). Keep top-k items by key (descending). Higher w concentrates the key near 1; lower w near 0. Inclusion probability is provably proportional to w under reasonable conditions. INTEGER-FIXED-POINT APPROXIMATION (because C anchor lacks f64, but we want the sibling to be Wheeler-comparable against C): - u_31 = LCG draw in (0, 2^31) - approx_log2_u = bitlen(u_31) - 31 // in [-30, 0] - approx_log_key = (approx_log2_u * 1_000_000) / w - key = approx_log_key Higher weight pulls key closer to 0; lower weight pulls more negative. Sort descending by key; top-k by key are retained. PROPERTIES UNDER THE APPROXIMATION: - Heavy items (w >> 1) get keys near 0 (large in descending sort). - Light items (w = 1) get keys uniformly distributed in [-30_000_000, 0], breaking ties uniformly. - Quality degrades for very large weight variance. v2 will swap in a finer-grained log approximation. LOSSLESS-LANGUAGE DISCIPLINE: per-item retain probability declared in the typed envelope as conf_ppb proportional to weight_total / weight_sum_sampled.