# Generic test serie for various solutions to the same algorithmic problem

I am learning how to use the module unittest for test-driven development. Below is a simple yet practical example of an issue I will have many times: one single problem (e.g. an Abstract Data Type (ADT) describing a Data Type and an Operator on it), and various Data Structures (DS) implementing this ADT; in this case the problem of computing the number of elements smaller than an element x in a sorted array A (i.e. its "insertion rank"), and two solutions: binary search and Fibonacci search. This codes "does the job" in that I can define the tests in one single place for all solutions, and the list of solutions in another one, but it does not seem elegant?

import unittest

class InsertionRankTest(unittest.TestCase):
def generic_test(self,algorithm):
self.assertEqual(algorithm([1],0),0)
self.assertEqual(algorithm([1],1),0)
self.assertEqual(algorithm([1],2),1)
self.assertEqual(algorithm([0, 10, 20, 30, 40, 50, 60, 70, 80, 90],0),0)
self.assertEqual(algorithm([0, 10, 20, 30, 40, 50, 60, 70, 80, 90],40),4)
self.assertEqual(algorithm([0, 10, 20, 30, 40, 50, 60, 70, 80, 90],45),5)
self.assertEqual(algorithm([0, 10, 20, 30, 40, 50, 60, 70, 80, 90],100),10)

def test_all_inertionRankAlgorithms(self):
self.generic_test(binarySearchForInsertionRank)
self.generic_test(fibonacciSearch)

def binarySearchForInsertionRank(A,x):
"""Computes the insertion rank r of x in A in time logarithmic in
len(A).

"""
assert(A!=None)
if len(A)==0:
return 0
else:
m = len(A)//2
if x <= A[m]:
return binarySearchForInsertionRank(A[:m],x)
else:
return m+1+binarySearchForInsertionRank(A[m+1:],x)

def fibonacciSearch(A,x):
"""Computes the insertion rank r of x in A in time logarithmic in
r.

"""
assert(A!=None)
if len(A)==0:
return 0
l = 0
r = 1
while r < len(A) and A[r] < x:
r += l
l = r-l # i.e., former value of r
return l + binarySearchForInsertionRank(A[l:min(r,len(A))],x)

def main():
unittest.main(exit=False)
if __name__ == '__main__':
main()


Does one define a class for the ADT, a class for the tests, derives the class for the ADT for each DS, and derives the test classes again? (As a bonus question: can the same tools be used to measure and compare the performance (as measured by either the number of comparisons or the running time)? What is the best way to measure the performance of each solution on each test case?)

• (I corrected the bonus question, please make sure I understood you correctly!) – Quentin Pradet May 22 '13 at 6:13
• Thanks, seems I had pasted by mistake a sentence inside another. All corrected now :) – Jeremy May 23 '13 at 9:07

Finally, performance is another concern than unit testing (except if you find a reliable way to test for the complexity of your algorithms). I recommend the timeit module. It doesn't say how to test for complexity, but it's a good start to measure time spent in a method.