diff options
Diffstat (limited to 'vendor/criterion/src/stats/bivariate')
| -rwxr-xr-x | vendor/criterion/src/stats/bivariate/bootstrap.rs | 91 | ||||
| -rwxr-xr-x | vendor/criterion/src/stats/bivariate/mod.rs | 131 | ||||
| -rwxr-xr-x | vendor/criterion/src/stats/bivariate/regression.rs | 53 | ||||
| -rwxr-xr-x | vendor/criterion/src/stats/bivariate/resamples.rs | 61 |
4 files changed, 336 insertions, 0 deletions
diff --git a/vendor/criterion/src/stats/bivariate/bootstrap.rs b/vendor/criterion/src/stats/bivariate/bootstrap.rs new file mode 100755 index 000000000..9eb7fa7b5 --- /dev/null +++ b/vendor/criterion/src/stats/bivariate/bootstrap.rs @@ -0,0 +1,91 @@ +#[cfg(test)] +macro_rules! test { + ($ty:ident) => { + mod $ty { + use quickcheck::TestResult; + use quickcheck::quickcheck; + use approx::relative_eq; + + use crate::stats::bivariate::regression::Slope; + use crate::stats::bivariate::Data; + + quickcheck! { + fn means(size: u8, start: u8, + offset: u8, nresamples: u8) -> TestResult { + let size = size as usize; + let start = start as usize; + let offset = offset as usize; + let nresamples = nresamples as usize; + if let Some(x) = crate::stats::test::vec::<$ty>(size, start) { + let y = crate::stats::test::vec::<$ty>(size + offset, start + offset).unwrap(); + let data = Data::new(&x[start..], &y[start+offset..]); + + let (x_means, y_means) = if nresamples > 0 { + data.bootstrap(nresamples, |d| (d.x().mean(), d.y().mean())) + } else { + return TestResult::discard(); + }; + + let x_min = data.x().min(); + let x_max = data.x().max(); + let y_min = data.y().min(); + let y_max = data.y().max(); + + TestResult::from_bool( + // Computed the correct number of resamples + x_means.len() == nresamples && + y_means.len() == nresamples && + // No uninitialized values + x_means.iter().all(|&x| { + (x > x_min || relative_eq!(x, x_min)) && + (x < x_max || relative_eq!(x, x_max)) + }) && + y_means.iter().all(|&y| { + (y > y_min || relative_eq!(y, y_min)) && + (y < y_max || relative_eq!(y, y_max)) + }) + ) + } else { + TestResult::discard() + } + } + } + + quickcheck! { + fn slope(size: u8, start: u8, + offset: u8, nresamples: u8) -> TestResult { + let size = size as usize; + let start = start as usize; + let offset = offset as usize; + let nresamples = nresamples as usize; + if let Some(x) = crate::stats::test::vec::<$ty>(size, start) { + let y = crate::stats::test::vec::<$ty>(size + offset, start + offset).unwrap(); + let data = Data::new(&x[start..], &y[start+offset..]); + + let slopes = if nresamples > 0 { + data.bootstrap(nresamples, |d| (Slope::fit(&d),)).0 + } else { + return TestResult::discard(); + }; + + TestResult::from_bool( + // Computed the correct number of resamples + slopes.len() == nresamples && + // No uninitialized values + slopes.iter().all(|s| s.0 > 0.) + ) + } else { + TestResult::discard() + } + } + } + + } + }; +} + +#[cfg(test)] +mod test { + test!(f32); + test!(f64); +} diff --git a/vendor/criterion/src/stats/bivariate/mod.rs b/vendor/criterion/src/stats/bivariate/mod.rs new file mode 100755 index 000000000..d1e8df703 --- /dev/null +++ b/vendor/criterion/src/stats/bivariate/mod.rs @@ -0,0 +1,131 @@ +//! Bivariate analysis + +mod bootstrap; +pub mod regression; +mod resamples; + +use crate::stats::bivariate::resamples::Resamples; +use crate::stats::float::Float; +use crate::stats::tuple::{Tuple, TupledDistributionsBuilder}; +use crate::stats::univariate::Sample; +use rayon::iter::{IntoParallelIterator, ParallelIterator}; + +/// Bivariate `(X, Y)` data +/// +/// Invariants: +/// +/// - No `NaN`s in the data +/// - At least two data points in the set +pub struct Data<'a, X, Y>(&'a [X], &'a [Y]); + +impl<'a, X, Y> Copy for Data<'a, X, Y> {} + +#[cfg_attr(feature = "cargo-clippy", allow(clippy::expl_impl_clone_on_copy))] +impl<'a, X, Y> Clone for Data<'a, X, Y> { + fn clone(&self) -> Data<'a, X, Y> { + *self + } +} + +impl<'a, X, Y> Data<'a, X, Y> { + /// Returns the length of the data set + pub fn len(&self) -> usize { + self.0.len() + } + + /// Iterate over the data set + pub fn iter(&self) -> Pairs<'a, X, Y> { + Pairs { + data: *self, + state: 0, + } + } +} + +impl<'a, X, Y> Data<'a, X, Y> +where + X: Float, + Y: Float, +{ + /// Creates a new data set from two existing slices + pub fn new(xs: &'a [X], ys: &'a [Y]) -> Data<'a, X, Y> { + assert!( + xs.len() == ys.len() + && xs.len() > 1 + && xs.iter().all(|x| !x.is_nan()) + && ys.iter().all(|y| !y.is_nan()) + ); + + Data(xs, ys) + } + + // TODO Remove the `T` parameter in favor of `S::Output` + /// Returns the bootstrap distributions of the parameters estimated by the `statistic` + /// + /// - Multi-threaded + /// - Time: `O(nresamples)` + /// - Memory: `O(nresamples)` + pub fn bootstrap<T, S>(&self, nresamples: usize, statistic: S) -> T::Distributions + where + S: Fn(Data<X, Y>) -> T + Sync, + T: Tuple + Send, + T::Distributions: Send, + T::Builder: Send, + { + (0..nresamples) + .into_par_iter() + .map_init( + || Resamples::new(*self), + |resamples, _| statistic(resamples.next()), + ) + .fold( + || T::Builder::new(0), + |mut sub_distributions, sample| { + sub_distributions.push(sample); + sub_distributions + }, + ) + .reduce( + || T::Builder::new(0), + |mut a, mut b| { + a.extend(&mut b); + a + }, + ) + .complete() + } + + /// Returns a view into the `X` data + pub fn x(&self) -> &'a Sample<X> { + Sample::new(self.0) + } + + /// Returns a view into the `Y` data + pub fn y(&self) -> &'a Sample<Y> { + Sample::new(self.1) + } +} + +/// Iterator over `Data` +pub struct Pairs<'a, X: 'a, Y: 'a> { + data: Data<'a, X, Y>, + state: usize, +} + +impl<'a, X, Y> Iterator for Pairs<'a, X, Y> { + type Item = (&'a X, &'a Y); + + fn next(&mut self) -> Option<(&'a X, &'a Y)> { + if self.state < self.data.len() { + let i = self.state; + self.state += 1; + + // This is safe because i will always be < self.data.{0,1}.len() + debug_assert!(i < self.data.0.len()); + debug_assert!(i < self.data.1.len()); + unsafe { Some((self.data.0.get_unchecked(i), self.data.1.get_unchecked(i))) } + } else { + None + } + } +} diff --git a/vendor/criterion/src/stats/bivariate/regression.rs b/vendor/criterion/src/stats/bivariate/regression.rs new file mode 100755 index 000000000..f09443f10 --- /dev/null +++ b/vendor/criterion/src/stats/bivariate/regression.rs @@ -0,0 +1,53 @@ +//! Regression analysis + +use crate::stats::bivariate::Data; +use crate::stats::float::Float; + +/// A straight line that passes through the origin `y = m * x` +#[derive(Clone, Copy)] +pub struct Slope<A>(pub A) +where + A: Float; + +impl<A> Slope<A> +where + A: Float, +{ + /// Fits the data to a straight line that passes through the origin using ordinary least + /// squares + /// + /// - Time: `O(length)` + pub fn fit(data: &Data<'_, A, A>) -> Slope<A> { + let xs = data.0; + let ys = data.1; + + let xy = crate::stats::dot(xs, ys); + let x2 = crate::stats::dot(xs, xs); + + Slope(xy / x2) + } + + /// Computes the goodness of fit (coefficient of determination) for this data set + /// + /// - Time: `O(length)` + pub fn r_squared(&self, data: &Data<'_, A, A>) -> A { + let _0 = A::cast(0); + let _1 = A::cast(1); + let m = self.0; + let xs = data.0; + let ys = data.1; + + let n = A::cast(xs.len()); + let y_bar = crate::stats::sum(ys) / n; + + let mut ss_res = _0; + let mut ss_tot = _0; + + for (&x, &y) in data.iter() { + ss_res = ss_res + (y - m * x).powi(2); + ss_tot = ss_res + (y - y_bar).powi(2); + } + + _1 - ss_res / ss_tot + } +} diff --git a/vendor/criterion/src/stats/bivariate/resamples.rs b/vendor/criterion/src/stats/bivariate/resamples.rs new file mode 100755 index 000000000..e254dc792 --- /dev/null +++ b/vendor/criterion/src/stats/bivariate/resamples.rs @@ -0,0 +1,61 @@ +use crate::stats::bivariate::Data; +use crate::stats::float::Float; +use crate::stats::rand_util::{new_rng, Rng}; + +pub struct Resamples<'a, X, Y> +where + X: 'a + Float, + Y: 'a + Float, +{ + rng: Rng, + data: (&'a [X], &'a [Y]), + stage: Option<(Vec<X>, Vec<Y>)>, +} + +#[cfg_attr(feature = "cargo-clippy", allow(clippy::should_implement_trait))] +impl<'a, X, Y> Resamples<'a, X, Y> +where + X: 'a + Float, + Y: 'a + Float, +{ + pub fn new(data: Data<'a, X, Y>) -> Resamples<'a, X, Y> { + Resamples { + rng: new_rng(), + data: (data.x(), data.y()), + stage: None, + } + } + + pub fn next(&mut self) -> Data<'_, X, Y> { + let n = self.data.0.len(); + + match self.stage { + None => { + let mut stage = (Vec::with_capacity(n), Vec::with_capacity(n)); + + for _ in 0..n { + let i = self.rng.rand_range(0u64..(self.data.0.len() as u64)) as usize; + + stage.0.push(self.data.0[i]); + stage.1.push(self.data.1[i]); + } + + self.stage = Some(stage); + } + Some(ref mut stage) => { + for i in 0..n { + let j = self.rng.rand_range(0u64..(self.data.0.len() as u64)) as usize; + + stage.0[i] = self.data.0[j]; + stage.1[i] = self.data.1[j]; + } + } + } + + if let Some((ref x, ref y)) = self.stage { + Data(x, y) + } else { + unreachable!(); + } + } +} |