1use crate::strata::StrataPartition;
27
28const LAMBDA_LOG_LIKELIHOOD: f64 = 0.0;
30const LAMBDA_MODIFIED: f64 = -1.0;
32
33pub(crate) struct ContingencyTable {
35 rows: usize,
36 cols: usize,
37 counts: Vec<f64>,
38}
39
40impl ContingencyTable {
41 fn zeros(rows: usize, cols: usize) -> Self {
43 Self {
44 rows,
45 cols,
46 counts: vec![0.0; rows * cols],
47 }
48 }
49
50 #[inline]
51 fn add(&mut self, r: usize, c: usize) {
52 self.counts[r * self.cols + c] += 1.0;
53 }
54
55 fn reset(&mut self) {
57 self.counts.fill(0.0);
58 }
59
60 fn rows(&self) -> impl Iterator<Item = &[f64]> {
62 self.counts.chunks_exact(self.cols)
63 }
64}
65
66type TableStat = (f64, usize);
68
69#[inline]
76fn power_divergence_term(observed: f64, expected: f64, lambda: f64) -> f64 {
77 if lambda == LAMBDA_LOG_LIKELIHOOD {
78 if observed == 0.0 {
80 0.0
81 } else {
82 2.0 * observed * (observed / expected).ln()
83 }
84 } else if lambda == LAMBDA_MODIFIED {
85 if observed == 0.0 {
87 f64::INFINITY
88 } else {
89 2.0 * expected * (expected / observed).ln()
90 }
91 } else {
92 let bracket = observed.powf(lambda + 1.0) / expected.powf(lambda) - observed;
95 (2.0 / (lambda * (lambda + 1.0))) * bracket
96 }
97}
98
99fn power_divergence_table(table: &ContingencyTable, lambda: f64, yates: bool) -> Option<TableStat> {
107 let mut row_sums = vec![0.0; table.rows];
109 let mut col_sums = vec![0.0; table.cols];
110 for (row, row_sum) in table.rows().zip(row_sums.iter_mut()) {
111 for (&v, col_sum) in row.iter().zip(col_sums.iter_mut()) {
112 *row_sum += v;
113 *col_sum += v;
114 }
115 }
116 let total: f64 = row_sums.iter().sum();
117 if total == 0.0 {
118 return None;
119 }
120
121 let active_rows = row_sums.iter().filter(|&&s| s > 0.0).count();
123 let active_cols = col_sums.iter().filter(|&&s| s > 0.0).count();
124 if active_rows < 2 || active_cols < 2 {
125 return None;
126 }
127
128 let dof = (active_rows - 1) * (active_cols - 1);
129 let use_yates = yates && dof == 1;
131
132 let mut statistic = 0.0;
133 for (row, &row_sum) in table.rows().zip(row_sums.iter()) {
134 if row_sum == 0.0 {
135 continue;
136 }
137 for (&observed, &col_sum) in row.iter().zip(col_sums.iter()) {
138 if col_sum == 0.0 {
139 continue;
140 }
141 let expected = row_sum * col_sum / total;
142 let corrected = if use_yates {
144 observed - (observed - expected).clamp(-0.5, 0.5)
146 } else {
147 observed
148 };
149 statistic += power_divergence_term(corrected, expected, lambda);
150 }
151 }
152
153 Some((statistic, dof))
154}
155
156pub(crate) struct DiscreteOutcome {
158 pub statistic: f64,
159 pub dof: usize,
160}
161
162pub(crate) fn power_divergence_unconditional(
166 x_codes: &[usize],
167 y_codes: &[usize],
168 kx: usize,
169 ky: usize,
170 lambda: f64,
171 yates: bool,
172) -> DiscreteOutcome {
173 let mut table = ContingencyTable::zeros(kx, ky);
174 for (&xc, &yc) in x_codes.iter().zip(y_codes) {
175 table.add(xc, yc);
176 }
177 let (statistic, dof) = power_divergence_table(&table, lambda, yates).unwrap_or((0.0, 0));
178 DiscreteOutcome { statistic, dof }
179}
180
181pub(crate) fn power_divergence_conditional(
186 x_codes: &[usize],
187 y_codes: &[usize],
188 kx: usize,
189 ky: usize,
190 partition: &StrataPartition,
191 lambda: f64,
192 yates: bool,
193) -> DiscreteOutcome {
194 let mut table = ContingencyTable::zeros(kx, ky);
195 let mut statistic = 0.0;
196 let mut dof = 0;
197 for s in 0..partition.n_strata() {
198 table.reset();
199 let lo = partition.starts[s] as usize;
200 let hi = partition.starts[s + 1] as usize;
201 for &row in &partition.rows[lo..hi] {
202 table.add(x_codes[row as usize], y_codes[row as usize]);
203 }
204 if let Some((stat, table_dof)) = power_divergence_table(&table, lambda, yates) {
205 statistic += stat;
206 dof += table_dof;
207 }
208 }
209 DiscreteOutcome { statistic, dof }
210}
211
212#[cfg(test)]
213mod tests {
214 use super::*;
215 use crate::strata::build_strata_partition;
216
217 const LAMBDA_PEARSON: f64 = 1.0;
218 const LAMBDA_CRESSIE_READ: f64 = 2.0 / 3.0;
219 const LAMBDA_FREEMAN_TUKEY: f64 = -0.5;
220
221 fn table(rows: usize, cols: usize, counts: &[f64]) -> ContingencyTable {
222 ContingencyTable {
223 rows,
224 cols,
225 counts: counts.to_vec(),
226 }
227 }
228
229 #[test]
230 fn yates_2x2_matches_scipy_pearson() {
231 let x = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
234 let y = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
235 let out = power_divergence_unconditional(&x, &y, 2, 2, LAMBDA_PEARSON, true);
236 assert!((out.statistic - 16.2).abs() < 1e-9, "got {}", out.statistic);
237 assert_eq!(out.dof, 1);
238 }
239
240 #[test]
241 fn yates_can_be_disabled() {
242 let x = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
244 let y = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
245 let out = power_divergence_unconditional(&x, &y, 2, 2, LAMBDA_PEARSON, false);
246 assert!((out.statistic - 20.0).abs() < 1e-9, "got {}", out.statistic);
247 assert_eq!(out.dof, 1);
248 }
249
250 #[test]
251 fn independent_table_zero_statistic() {
252 let x = vec![0, 0, 1, 1];
254 let y = vec![0, 1, 0, 1];
255 let out = power_divergence_unconditional(&x, &y, 2, 2, LAMBDA_PEARSON, true);
256 assert!(out.statistic.abs() < 1e-12);
257 assert_eq!(out.dof, 1);
258 }
259
260 #[test]
261 fn single_category_degenerate() {
262 let x = vec![0, 0, 0, 0];
263 let y = vec![0, 1, 0, 1];
264 let out = power_divergence_unconditional(&x, &y, 1, 2, LAMBDA_PEARSON, true);
265 assert_eq!(out.dof, 0);
266 assert!(out.statistic.abs() < 1e-12);
267 }
268
269 #[test]
270 fn modified_likelihood_zero_cell_is_infinite() {
271 let t = table(3, 3, &[5.0, 5.0, 0.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0]);
274 let (stat, dof) = power_divergence_table(&t, LAMBDA_MODIFIED, true).unwrap();
275 assert!(stat.is_infinite() && stat > 0.0, "got {stat}");
276 assert_eq!(dof, 4);
277 }
278
279 #[test]
280 fn zero_cell_finite_for_lambda_gt_minus_one() {
281 let t = table(3, 3, &[5.0, 5.0, 0.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0]);
283 for lambda in [
284 LAMBDA_PEARSON,
285 LAMBDA_LOG_LIKELIHOOD,
286 LAMBDA_CRESSIE_READ,
287 LAMBDA_FREEMAN_TUKEY,
288 ] {
289 let (stat, _) = power_divergence_table(&t, lambda, true).unwrap();
290 assert!(stat.is_finite(), "lambda {lambda} gave {stat}");
291 }
292 }
293
294 fn lcg_codes(seed: &mut u64, n: usize, card: usize) -> Vec<usize> {
296 (0..n)
297 .map(|_| {
298 *seed = seed
299 .wrapping_mul(6_364_136_223_846_793_005)
300 .wrapping_add(1_442_695_040_888_963_407);
301 ((*seed >> 33) as usize) % card
302 })
303 .collect()
304 }
305
306 fn naive_conditional(
309 x: &[usize],
310 y: &[usize],
311 kx: usize,
312 ky: usize,
313 z: &[(&[usize], usize)],
314 lambda: f64,
315 yates: bool,
316 ) -> DiscreteOutcome {
317 let n = x.len();
318 let mut strata: std::collections::HashMap<Vec<usize>, Vec<usize>> =
319 std::collections::HashMap::new();
320 for i in 0..n {
321 let key: Vec<usize> = z.iter().map(|(codes, _)| codes[i]).collect();
322 strata.entry(key).or_default().push(i);
323 }
324 let mut statistic = 0.0;
325 let mut dof = 0;
326 for idx in strata.values() {
327 let mut table = ContingencyTable::zeros(kx, ky);
328 for &i in idx {
329 table.add(x[i], y[i]);
330 }
331 if let Some((stat, table_dof)) = power_divergence_table(&table, lambda, yates) {
332 statistic += stat;
333 dof += table_dof;
334 }
335 }
336 DiscreteOutcome { statistic, dof }
337 }
338
339 fn assert_outcomes_match(fast: &DiscreteOutcome, slow: &DiscreteOutcome, label: &str) {
340 assert_eq!(fast.dof, slow.dof, "dof {label}");
341 let scale = fast.statistic.abs().max(slow.statistic.abs()).max(1.0);
342 assert!(
343 (fast.statistic - slow.statistic).abs() <= 1e-9 * scale
344 || (fast.statistic.is_infinite() && slow.statistic.is_infinite()),
345 "stat {label}: {} vs {}",
346 fast.statistic,
347 slow.statistic
348 );
349 }
350
351 #[test]
352 fn conditional_matches_naive_grouping() {
353 let mut seed = 0x00C0_FFEE_u64;
354 for (n, kx, ky, z_cards) in [
355 (200, 2, 2, vec![2]),
356 (500, 3, 4, vec![2, 3]),
357 (350, 2, 3, vec![3, 2, 4]),
358 (64, 4, 4, vec![5]),
359 (30, 2, 2, vec![100, 100]), ] {
361 let x = lcg_codes(&mut seed, n, kx);
362 let y = lcg_codes(&mut seed, n, ky);
363 let z: Vec<(Vec<usize>, usize)> = z_cards
364 .iter()
365 .map(|&c| (lcg_codes(&mut seed, n, c), c))
366 .collect();
367 let z_ref: Vec<(&[usize], usize)> = z.iter().map(|(v, c)| (v.as_slice(), *c)).collect();
368 let partition = build_strata_partition(&z_ref, n);
369 for lambda in [1.0, 0.0, -1.0, 2.0 / 3.0, -0.5] {
370 let fast = power_divergence_conditional(&x, &y, kx, ky, &partition, lambda, true);
371 let slow = naive_conditional(&x, &y, kx, ky, &z_ref, lambda, true);
372 assert_outcomes_match(&fast, &slow, &format!("λ={lambda} n={n}"));
373 }
374 }
375 }
376
377 #[test]
378 fn overflow_path_matches_naive() {
379 let n = 8;
382 let x: Vec<usize> = (0..n).map(|i| i % 2).collect();
383 let y: Vec<usize> = (0..n).map(|i| (i / 2) % 2).collect();
384 let z_cols: Vec<Vec<usize>> = (0..64)
385 .map(|c| (0..n).map(|i| (i >> (c % 3)) % 2).collect())
386 .collect();
387 let z_ref: Vec<(&[usize], usize)> = z_cols.iter().map(|v| (v.as_slice(), 2)).collect();
388 let partition = build_strata_partition(&z_ref, n);
389 let fast = power_divergence_conditional(&x, &y, 2, 2, &partition, 1.0, true);
390 let slow = naive_conditional(&x, &y, 2, 2, &z_ref, 1.0, true);
391 assert_outcomes_match(&fast, &slow, "overflow");
392 }
393}