March 29, 2016
Unit Tests For Algorithm Time ComplexityJust a quick example from a pairing session I just finished, where we've been TDD-ing simple sorting algorithms while exploring how we can refactor our JUnit tests to buy us higher test assurance with less code.
After TDD-ing an implementation of Quicksort, the question came up "All the sorting algorithms produce the exact same outputs. How do we test-drive for efficiency?"
Although it's too rarely explored, there's no reason at all why we can't write non-functional failing tests, too.
Bubblesort, for example, has worst-case performance O(N2), so sorting a million items could involve 1,000,000,000,000 swaps. Quicksort is much faster, with time complexity O(N log N).
There are different ways we could test-drive O(N log N) performance in our design. For example, we could extend the Quicksort class to create a new class - which would part of our test code - that overrides the swap() method and counts each swap so we can assert a maximum number in our test.
I like this approach because we haven't touched our original Quicksort implementation - it's proper Open-Closed. It's also pretty simple, as you can see.
It's also repeatable - the number of swaps should never go over N log N - so we don't end up with potentially fragile tests, like we can when we assert a maximum timeout instead (because sometimes our machines just get too busy!)
Note too that I put this test in its own fixture, instead of adding it to the existing QuicksortTests fixture, so I can easily run them separately. Typically, I would package different kinds of tests separately for this reason. It takes ~150ms to run, which doesn't sound much, but hundreds of tests like these could really jam up your functional regression testing.
Just a quick thought, if you fancied trying it.
As you were!
Posted 2 years, 3 months ago on March 29, 2016