Javascript – How does one unit test an algorithm

algorithmsjavascriptunit testing

I was recently working on a JS slideshow which rotates images using a weighted average algorithm. Thankfully, timgilbert has written a weighted list script which implements the exact algorithm I needed. However in his documentation he's noted under todos: "unit tests!".

I'd like to know is how one goes about unit testing an algorithm. In the case of a weighted average how would you create a proof that the averages are accurate when there is the element of randomness?

Code samples of similar would be very helpful to my understanding.

Best Answer

There a couple of technique you can use here:

1) Replace the random number generator with one that produces canned values, and check that the expected values are gotten

   old_random = Math.random;
   Math.random = function() { return 0.5; };
   assert_equals(random_pick(), expected_random_pick);

2) Run the algorithm a whole lots of times, and sum up the results

weights = {0:.1, 2:.5, 6:0.4}
totals = {}
count = 10000;
for(x = 0; x < count; x++)
{
    totals[random_pick(weights)] += 1 / count;
}
assert(totals[0] - weights[0] < 0.1)
assert(totals[2] - weights[2] < 0.1)
assert(totals[6] - weights[6] < 0.1)

The idea here is that if you run the algorithm enough times the law of large numbers will make the totals similar the theoretically expected ones. Then you check that.

Related Solutions

How to Unit Test a Heuristic Algorithm

For a heuristic algorithm which is supposed to not return the ideal but a "good enough" solution, you would have various test-cases and check

is the solution actually valid? You certainly want to make sure your route-finding algorithm doesn't return paths which are impossible or which don't actually lead from start to finish. You might not be able to prove that the solution is ideal, but you should at least be able to verify that the return value actually is a solution.
is the solution "good enough"? You should have some requirements which define how much worse the algorithm may be than the ideal solution. You should have test cases where the ideal solution is known (or at least a solution which is considered good enough to be used as a comparison standard) and confirm that the solution provided by the algorithm is not more than x% worse.
Is the algorithm fast enough? You often use a heuristic approach when you presume that they make up for their lack of precision by being much faster. To verify this you should measure their runtime and make sure they are indeed faster than an algorithm which gets the exact solution. Runtime measurements are always a bit fuzzy, so exceeding the expected runtime should be a warning, not an error (when your unit testing framework allows to differ between warnings and errors).

Javascript – How to write good javascript unit test descriptions

Note that if you're perfectly happy with the style of descriptions you used to write in Python, there is no reason to change that. Put the name of the tested block within the describe, and put your description in it. If it's clear for you, it doesn't matter what the designers of the test framework had in mind.

If you're for some reason unhappy with porting your style to JavaScript, then stick with it('should do this or that'), and just below it, include the complete description:

describe('the ruler', () => {
    describe('after a double-click', () => {
        it('should reflect the cursor position instead of assuming a (0, 0)', () => {
            /**
             * The edge case documented in CAP-621 happens when a user, instead of simply
             * clicking once to position the first side of the ruler, and then click
             * another time somewhere else to fix the ruler on the page, double-clicks on
             * the page. The previous behavior was that the ruler was drawn from the cursor
             * to the (0, 0) of the page. Instead, a double-click should be treated as if
             * it was a simple click, letting the user to position the other side of the
             * ruler with another click or double-click.
             */
            ...
        });
    });
});

When reading a test, for instance in the context where a change in the code broke it, either you'll understand its purpose just by looking at its name, or you'll read the long comment. This style may even be preferable to having only the long description: if the test is recent or if it concerns a part you were working on recently, chances are, you won't need the whole description, and having a short name would save you time.

Best Answer

Related Solutions

How to Unit Test a Heuristic Algorithm

Javascript – How to write good javascript unit test descriptions

Related Topic