diff options
Diffstat (limited to '')
| -rw-r--r-- | third_party/rust/smawk/tests/agreement.rs | 104 | ||||
| -rw-r--r-- | third_party/rust/smawk/tests/complexity.rs | 83 | ||||
| -rw-r--r-- | third_party/rust/smawk/tests/monge.rs | 83 | ||||
| -rw-r--r-- | third_party/rust/smawk/tests/random_monge/mod.rs | 83 | ||||
| -rw-r--r-- | third_party/rust/smawk/tests/version-numbers.rs | 9 |
5 files changed, 362 insertions, 0 deletions
diff --git a/third_party/rust/smawk/tests/agreement.rs b/third_party/rust/smawk/tests/agreement.rs new file mode 100644 index 0000000000..2e0343a59a --- /dev/null +++ b/third_party/rust/smawk/tests/agreement.rs @@ -0,0 +1,104 @@ +#![cfg(feature = "ndarray")] + +use ndarray::{s, Array2}; +use rand::SeedableRng; +use rand_chacha::ChaCha20Rng; +use smawk::{brute_force, online_column_minima, recursive}; + +mod random_monge; +use random_monge::random_monge_matrix; + +/// Check that the brute force, recursive, and SMAWK functions +/// give identical results on a large number of randomly generated +/// Monge matrices. +#[test] +fn column_minima_agree() { + let sizes = vec![1, 2, 3, 4, 5, 10, 15, 20, 30]; + let mut rng = ChaCha20Rng::seed_from_u64(0); + for _ in 0..4 { + for m in sizes.clone().iter() { + for n in sizes.clone().iter() { + let matrix: Array2<i32> = random_monge_matrix(*m, *n, &mut rng); + + // Compute and test row minima. + let brute_force = brute_force::row_minima(&matrix); + let recursive = recursive::row_minima(&matrix); + let smawk = smawk::row_minima(&matrix); + assert_eq!( + brute_force, recursive, + "recursive and brute force differs on:\n{:?}", + matrix + ); + assert_eq!( + brute_force, smawk, + "SMAWK and brute force differs on:\n{:?}", + matrix + ); + + // Do the same for the column minima. + let brute_force = brute_force::column_minima(&matrix); + let recursive = recursive::column_minima(&matrix); + let smawk = smawk::column_minima(&matrix); + assert_eq!( + brute_force, recursive, + "recursive and brute force differs on:\n{:?}", + matrix + ); + assert_eq!( + brute_force, smawk, + "SMAWK and brute force differs on:\n{:?}", + matrix + ); + } + } + } +} + +/// Check that the brute force and online SMAWK functions give +/// identical results on a large number of randomly generated +/// Monge matrices. +#[test] +fn online_agree() { + let sizes = vec![1, 2, 3, 4, 5, 10, 15, 20, 30, 50]; + let mut rng = ChaCha20Rng::seed_from_u64(0); + for _ in 0..5 { + for &size in &sizes { + // Random totally monotone square matrix of the + // desired size. + let mut matrix: Array2<i32> = random_monge_matrix(size, size, &mut rng); + + // Adjust matrix so the column minima are above the + // diagonal. The brute_force::column_minima will still + // work just fine on such a mangled Monge matrix. + let max = *matrix.iter().max().unwrap_or(&0); + for idx in 0..(size as isize) { + // Using the maximum value of the matrix instead + // of i32::max_value() makes for prettier matrices + // in case we want to print them. + matrix.slice_mut(s![idx..idx + 1, ..idx + 1]).fill(max); + } + + // The online algorithm always returns the initial + // value for the left-most column -- without + // inspecting the column at all. So we fill the + // left-most column with this value to have the brute + // force algorithm do the same. + let initial = 42; + matrix.slice_mut(s![0.., ..1]).fill(initial); + + // Brute-force computation of column minima, returned + // in the same form as online_column_minima. + let brute_force = brute_force::column_minima(&matrix) + .iter() + .enumerate() + .map(|(j, &i)| (i, matrix[[i, j]])) + .collect::<Vec<_>>(); + let online = online_column_minima(initial, size, |_, i, j| matrix[[i, j]]); + assert_eq!( + brute_force, online, + "brute force and online differ on:\n{:3?}", + matrix + ); + } + } +} diff --git a/third_party/rust/smawk/tests/complexity.rs b/third_party/rust/smawk/tests/complexity.rs new file mode 100644 index 0000000000..c9881eaeac --- /dev/null +++ b/third_party/rust/smawk/tests/complexity.rs @@ -0,0 +1,83 @@ +#![cfg(feature = "ndarray")] + +use ndarray::{Array1, Array2}; +use rand::SeedableRng; +use rand_chacha::ChaCha20Rng; +use smawk::online_column_minima; + +mod random_monge; +use random_monge::random_monge_matrix; + +#[derive(Debug)] +struct LinRegression { + alpha: f64, + beta: f64, + r_squared: f64, +} + +/// Square an expression. Works equally well for floats and matrices. +macro_rules! squared { + ($x:expr) => { + $x * $x + }; +} + +/// Compute the mean of a 1-dimensional array. +macro_rules! mean { + ($a:expr) => { + $a.mean().expect("Mean of empty array") + }; +} + +/// Compute a simple linear regression from the list of values. +/// +/// See <https://en.wikipedia.org/wiki/Simple_linear_regression>. +fn linear_regression(values: &[(usize, i32)]) -> LinRegression { + let xs = values.iter().map(|&(x, _)| x as f64).collect::<Array1<_>>(); + let ys = values.iter().map(|&(_, y)| y as f64).collect::<Array1<_>>(); + + let xs_mean = mean!(&xs); + let ys_mean = mean!(&ys); + let xs_ys_mean = mean!(&xs * &ys); + + let cov_xs_ys = ((&xs - xs_mean) * (&ys - ys_mean)).sum(); + let var_xs = squared!(&xs - xs_mean).sum(); + + let beta = cov_xs_ys / var_xs; + let alpha = ys_mean - beta * xs_mean; + let r_squared = squared!(xs_ys_mean - xs_mean * ys_mean) + / ((mean!(&xs * &xs) - squared!(xs_mean)) * (mean!(&ys * &ys) - squared!(ys_mean))); + + LinRegression { + alpha: alpha, + beta: beta, + r_squared: r_squared, + } +} + +/// Check that the number of matrix accesses in `online_column_minima` +/// grows as O(*n*) for *n* ✕ *n* matrix. +#[test] +fn online_linear_complexity() { + let mut rng = ChaCha20Rng::seed_from_u64(0); + let mut data = vec![]; + + for &size in &[1, 2, 3, 4, 5, 10, 15, 20, 30, 40, 50, 60, 70, 80, 90, 100] { + let matrix: Array2<i32> = random_monge_matrix(size, size, &mut rng); + let count = std::cell::RefCell::new(0); + online_column_minima(0, size, |_, i, j| { + *count.borrow_mut() += 1; + matrix[[i, j]] + }); + data.push((size, count.into_inner())); + } + + let lin_reg = linear_regression(&data); + assert!( + lin_reg.r_squared > 0.95, + "r² = {:.4} is lower than expected for a linear fit\nData points: {:?}\n{:?}", + lin_reg.r_squared, + data, + lin_reg + ); +} diff --git a/third_party/rust/smawk/tests/monge.rs b/third_party/rust/smawk/tests/monge.rs new file mode 100644 index 0000000000..67058a75a5 --- /dev/null +++ b/third_party/rust/smawk/tests/monge.rs @@ -0,0 +1,83 @@ +#![cfg(feature = "ndarray")] + +use ndarray::{arr2, Array, Array2}; +use rand::SeedableRng; +use rand_chacha::ChaCha20Rng; +use smawk::monge::is_monge; + +mod random_monge; +use random_monge::{random_monge_matrix, MongePrim}; + +#[test] +fn random_monge() { + let mut rng = ChaCha20Rng::seed_from_u64(0); + let matrix: Array2<u8> = random_monge_matrix(5, 5, &mut rng); + + assert!(is_monge(&matrix)); + assert_eq!( + matrix, + arr2(&[ + [2, 3, 4, 4, 5], + [5, 5, 6, 6, 7], + [3, 3, 4, 4, 5], + [5, 2, 3, 3, 4], + [5, 2, 3, 3, 4] + ]) + ); +} + +#[test] +fn monge_constant_rows() { + let mut rng = ChaCha20Rng::seed_from_u64(0); + let matrix: Array2<u8> = MongePrim::ConstantRows.to_matrix(5, 4, &mut rng); + assert!(is_monge(&matrix)); + for row in matrix.rows() { + let elem = row[0]; + assert_eq!(row, Array::from_elem(matrix.ncols(), elem)); + } +} + +#[test] +fn monge_constant_cols() { + let mut rng = ChaCha20Rng::seed_from_u64(0); + let matrix: Array2<u8> = MongePrim::ConstantCols.to_matrix(5, 4, &mut rng); + assert!(is_monge(&matrix)); + for column in matrix.columns() { + let elem = column[0]; + assert_eq!(column, Array::from_elem(matrix.nrows(), elem)); + } +} + +#[test] +fn monge_upper_right_ones() { + let mut rng = ChaCha20Rng::seed_from_u64(1); + let matrix: Array2<u8> = MongePrim::UpperRightOnes.to_matrix(5, 4, &mut rng); + assert!(is_monge(&matrix)); + assert_eq!( + matrix, + arr2(&[ + [0, 0, 1, 1], + [0, 0, 1, 1], + [0, 0, 1, 1], + [0, 0, 0, 0], + [0, 0, 0, 0] + ]) + ); +} + +#[test] +fn monge_lower_left_ones() { + let mut rng = ChaCha20Rng::seed_from_u64(1); + let matrix: Array2<u8> = MongePrim::LowerLeftOnes.to_matrix(5, 4, &mut rng); + assert!(is_monge(&matrix)); + assert_eq!( + matrix, + arr2(&[ + [0, 0, 0, 0], + [0, 0, 0, 0], + [1, 1, 0, 0], + [1, 1, 0, 0], + [1, 1, 0, 0] + ]) + ); +} diff --git a/third_party/rust/smawk/tests/random_monge/mod.rs b/third_party/rust/smawk/tests/random_monge/mod.rs new file mode 100644 index 0000000000..50a932fbeb --- /dev/null +++ b/third_party/rust/smawk/tests/random_monge/mod.rs @@ -0,0 +1,83 @@ +//! Test functionality for generating random Monge matrices. + +// The code is put here so we can reuse it in different integration +// tests, without Cargo finding it when `cargo test` is run. See the +// section on "Submodules in Integration Tests" in +// https://doc.rust-lang.org/book/ch11-03-test-organization.html + +use ndarray::{s, Array2}; +use num_traits::PrimInt; +use rand::distributions::{Distribution, Standard}; +use rand::Rng; + +/// A Monge matrix can be decomposed into one of these primitive +/// building blocks. +#[derive(Copy, Clone)] +pub enum MongePrim { + ConstantRows, + ConstantCols, + UpperRightOnes, + LowerLeftOnes, +} + +impl MongePrim { + /// Generate a Monge matrix from a primitive. + pub fn to_matrix<T: PrimInt, R: Rng>(&self, m: usize, n: usize, rng: &mut R) -> Array2<T> + where + Standard: Distribution<T>, + { + let mut matrix = Array2::from_elem((m, n), T::zero()); + // Avoid panic in UpperRightOnes and LowerLeftOnes below. + if m == 0 || n == 0 { + return matrix; + } + + match *self { + MongePrim::ConstantRows => { + for mut row in matrix.rows_mut() { + if rng.gen::<bool>() { + row.fill(T::one()) + } + } + } + MongePrim::ConstantCols => { + for mut col in matrix.columns_mut() { + if rng.gen::<bool>() { + col.fill(T::one()) + } + } + } + MongePrim::UpperRightOnes => { + let i = rng.gen_range(0..(m + 1) as isize); + let j = rng.gen_range(0..(n + 1) as isize); + matrix.slice_mut(s![..i, -j..]).fill(T::one()); + } + MongePrim::LowerLeftOnes => { + let i = rng.gen_range(0..(m + 1) as isize); + let j = rng.gen_range(0..(n + 1) as isize); + matrix.slice_mut(s![-i.., ..j]).fill(T::one()); + } + } + + matrix + } +} + +/// Generate a random Monge matrix. +pub fn random_monge_matrix<R: Rng, T: PrimInt>(m: usize, n: usize, rng: &mut R) -> Array2<T> +where + Standard: Distribution<T>, +{ + let monge_primitives = [ + MongePrim::ConstantRows, + MongePrim::ConstantCols, + MongePrim::LowerLeftOnes, + MongePrim::UpperRightOnes, + ]; + let mut matrix = Array2::from_elem((m, n), T::zero()); + for _ in 0..(m + n) { + let monge = monge_primitives[rng.gen_range(0..monge_primitives.len())]; + matrix = matrix + monge.to_matrix(m, n, rng); + } + matrix +} diff --git a/third_party/rust/smawk/tests/version-numbers.rs b/third_party/rust/smawk/tests/version-numbers.rs new file mode 100644 index 0000000000..288592d02f --- /dev/null +++ b/third_party/rust/smawk/tests/version-numbers.rs @@ -0,0 +1,9 @@ +#[test] +fn test_readme_deps() { + version_sync::assert_markdown_deps_updated!("README.md"); +} + +#[test] +fn test_html_root_url() { + version_sync::assert_html_root_url_updated!("src/lib.rs"); +} |