Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Jun 9 '12 at 15:18

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

5 Answers 5

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.

share|improve this answer
    
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

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.

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer

First look at a set of inputs that the algorithm would deal with. Try to find different classifications for the input. For example, if the algorithm was something that computers the sqrt of a number (as an example), think of the kinds of inputs that the algorithm will deal with. One such input classification might be positive numbers, 0, and negative numbers. Then take any input from each of these classes and write a test that uses it.

This is an example of input space partitioning, and can help cover all the logical cases your program may have to deal with.

After this, use a code-coverage analysis tool to find any code (or cases) that aren't tested yet. Then try to formulate inputs that test that particular path in the code. This is an example of black-box testing.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.