Bigoish: Test the empirical computational complexity of Rust algorithms

Summary

§Bigoish: Test the empirical computational complexity of Rust algorithms Your functions or datastructure methods implement an algorithm; how do you know if they’re scaling as expected? For example, imagine you’ve implemented a new sorting algorithm. Decent sorting is typically O(nlogn), but how about your implementation? Maybe there’s a bug somewhere that makes it worse. With bigoish, pronounced “big-o-ish”, you can write tests that assert that a particular function has a particular empirical computational complexity. More accurately, you can assert that an expected complexity model you provide is empirically the best fit for measured runtime, when compared to the fits of a specific set of common complexity models. Real big-O, in contrast, is a mathematically-proven upper bound. Here’s an example, asserting that Rust’s built-in sort() fits n*log(n) best: use bigoish::{N, Log, assert_best_fit, growing_inputs}; fn sort(mut v: Vec<i64>) -> Vec<i64> { v.sort(); v } fn make_vec(n: usize) -> Vec<i64> { use fastrand; std::iter::repeat_with(|| fastrand::i64(..)).take(n).collect() } assert_best_fit( N * Log(N), sort, [ (10, make_vec(10)), (100, make_vec(100)), (1000, make_vec(1000)), (10_000, make_vec(10_000)), (100_000, make_vec(100_000)) ] ); assert_best_fit( N * Log(N), sort, growing_inputs(10, make_vec, 25), ); If you were to erroneously assert that sort() uses model N: ⓘassert_best_fit(N, sort, growing_inputs(10, make_vec, 25)); You would then get a panic that looks like this: §Improving your chances of a correct fit Sometimes assert_best_fit will misidentify your function’s likely complexity, claiming that, for example, n*log(n) is the best fit for your function despite it clearly being linear. Or, it may fail intermittently. To reduce the chances of this happening, you should: Use a sufficient number of inputs. Using 20 inputs is better than using 4 inputs. Make sure your inputs span a number of orders of magnitude. For example, if your function takes a Vec, testing w...