Bigoish: Test the empirical computational complexity of Rust algorithms
35 points by itamarst
35 points by itamarst
I don't even know exactly what I would use this for yet, but I love it so much conceptually that I'm actively trying to figure out what to use it for. Might be useful for my ebook/audiobook alignment algorithm, though I'd have to port it to Typescript.
The failure output is particularly great. I've been rethinking test output since this post on snapshot testing. I ended up rewriting Storyteller's alignment test to produce a snapshot that rendered each ebook line alongside the aligned line of audio so that it was as easy as possible to review both the validity of the output and how it changes.
There's https://napi.rs/, as an alternative to rewrite.
True! I guess it just depends on what API the crate exposes. If it exposes the underlying evaluation methods then napi.rs + a thin Node test runner wrapper would be enough!
I wonder what list of possible runtime complexities it uses to test against. I haven't found docs saying.
Like there's an example where you assert O(N) and it tells you O(N log N) is a better fit, so it picked O(N log N) as an alternative hypothesis to test out of the infinitely many alternatives. And surely it didn't compare against O(N log log log N), as that would be indistinguishable.
In this section, there is a list of builtin models: "constant, n, n², n³, √n, log(n), nlog(n), log(log(n))." The user's provided model can be any cost function whatsoever, I gather.
Yeah, maybe that list should be somewhere more visible?
I'm open to suggestions on any additional ones worth adding.
As one data point, the place I looked for it was https://docs.rs/bigoish/latest/bigoish/fn.assert_best_fit.html
It would also be really cool if you could customize this list! It's an excellent default, but there is no one size fits all answer. For example, if you're testing a cubic time algorithm like (say) Early parsing, it would be nice to be able to put O(N^4) as an alternative.