# How does one unit test an algorithm

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.

-

## migrated from stackoverflow.comJun 9 '12 at 15:18

This question came from our site for professional and enthusiast programmers.

Unit tests don't prove general cases. They merely assert that certain (hopefully well chosen) cases meet a few expectations. And that's good enough for most things.

Find some examples, manually calculate and verify the results, and when deemed correct, put them under assertion.

Make sure to choose your examples well. In case of "testing division" it doesn't make much sense to test 8/4, 4/2 and 6/3. It'd be much better to only test 8/4, but to also include 8/3 (= 2, or 2.66?), 8/(-2), 8/0, 0/8, 0/0, 2/8,... include corner cases.

-
Are you saying that it's futile to test final result of an algorithm such as the one described? –  Asa Baylus Jun 12 '12 at 0:52
@AsaBaylus I don't understand what you mean with "final result of an algorithm"? –  stmax Jun 12 '12 at 10:14
Im referring the returned or calculated value/output. –  Asa Baylus Jun 13 '12 at 10:21

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.

-
2) is fine if you want to do your tests once or twice. However, I would not recommend it for an automatic test suite where this test is run probably several thousand times (it may fail, and then you don't know if it has failed because there was a bug or just because it hit the low probability case). –  Doc Brown Jun 10 '12 at 13:04
@DocBrown, If you take enough samples, hitting the low probability case should be rare enough that you won't ever actually hit. But then it'll probably be slow. I typically have a collection of slow tests that I run separately less often for that kind of case. –  Winston Ewert Jun 10 '12 at 15:25
I like the idea of simply making Math.random produce predictable values as you've described in #1 –  Asa Baylus Jun 12 '12 at 0:55

It's all about expected results. If you know the numbers should return within a certain range, test for that.

-

I would just take the example and make what assertions I could. Of course, I would make this more than one test, not just a giant one. I'm going to write this mostly in pseudocode assuming that the utility methods have obvious implementations.

``````var data = [['a', 10],
['b',  1],
['c',  1],
['d',  5],
['e',  3]];

var wl = new WeightedList(data);

// wl.peek() returns items at random from the list, and does not modify the list.
var result = wl.peek();   // Ex: ['a']
assertContains(keySet(wl), result);
assertLength(1, result);
var result = wl.peek(3);  // Ex: ['a', 'c', 'd']
assertContainsAll(keySet(wl), result);
assertLength(3, result);

// wl.pop() returns random items from the list and removes the items it found
var result = wl.pop(2);  // Ex: ['a', 'd'], after which wl consists of [ ['b',  1], ['c',  1], ['e',  3] ]
assertIntersectionIsEmpty(result, keySet(wl));
assertLength(2, result);

// wl.push() adds new data into the set
// note that despite the terms push and pop, the weighted list has no natural order
wl.push('f', 6);     // wl is now [ ['b',  1], ['c',  1], ['e',  3], ['f',  6] ]
assertLength(4, wl);

// wl.addWeight() will increase the weight of a list item (or decrease it if the user passes a negative number)
wl.addWeight('b', 4);   // wl is now [ ['b',  5], ['c',  1], ['e',  3], ['f',  6] ]
// I doubt you can assert much here but no exception

// wl.shuffle() will return the entire list in random order.
result = wl.shuffle();           // Ex: ['b', 'f', 'c', 'e']
assertLength(4, result);
assertContainsAll(keySet(wl), result);
``````

Also, if the weights are not drastically different, you can repeat some of the operations many times and assert that you got all the values inside the WeightedList at some point. You just have to make sure that you repeat it enough that there is a very high probability they will appear. I would suggest a quick very high estimate of how many times you expect to run the test (say 100 times a day for a decade). Make the probability of failure one in that many runs. All you need to make sure is that the probability of this code failing due to bad luck with the random values is on the same order as the probability of failure due to a bug. Then you will not greatly increase your failure rate.

-