2
\$\begingroup\$

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?)

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

Embrace Python's simplicity! This is a dynamic language, we care less about inheritance and complex data models and focus more on the actual problem. Of course, it has its drawbacks, but that's how it works.

The answer your question: no, in Python, we wouldn't derive classes and so on but just write the code you wrote. It's still possible to define an abstract base class A with specific methods and extend it with a few implementations, but really think about the benefits before doing this.

Note about the code: PEP 8 is a standard style guide important in the Python word: space between operators and no camelCase in variable names are the two that come to mind while reading your code.

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks: I don't need python's help to compute the (worst case) complexity of my algorithm, that's my job ;) I am more interested in timing python implementations on specific instances, timeit seems to be adequate. And I will read PEP8! \$\endgroup\$ – Jeremy May 22 '13 at 13:36
  • \$\begingroup\$ I was thinking about checking it, not computing it. :) \$\endgroup\$ – Quentin Pradet May 22 '13 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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