tdd with non-trivial algorithms

views:

103

answers:

+1 Q:

tdd with non-trivial algorithms

Hi there,

In these days I'm coding some data structures in Java. Many of them (if not all) offer a very simple interface (add, contains, delete) but under the hood there are non-trivial algorithms.

How can I use the tdd technique in such a situation?

I think that the problem is that tdd (and in general unit testing) is about testing the interfaces and not the implementations. Am I right? How can I deal with this?

If you know any technique to handle this cases please let me know it.

Thank you for your help.

+4 A:

You're correct that TDD is about testing the interfaces, and not the implementation. That said, why do you care to test the actual implementation? The point is that if you sufficiently test the interface, the implementation does not matter.

When you find a bug in the implementation, that means that somewhere it violates the interface that you are exposing to the outside world. You need to track it down to where it violates the interface. That's where you write your test case.

Steven Schlansker 2010-07-27 18:10:04

If I test only the interface in this case I have no help in building my class and writing my methods.In practice I nullify the benefits of tdd. Don't you think?

TheSENDER 2010-07-27 18:30:50

There is nothing stopping you from writing tests for internal implementation methods like `merge()` or `resizeArray()`, but just be aware that when you do this you are making your tests more brittle.

matt b 2010-07-27 18:34:37

Also, if you ensure that your tests are in the same package, you can do this by making things protected - i.e. still hidden from the "real" world.

Steven Schlansker 2010-07-27 18:52:38

I know I can test private methods in several ways but I think that it's not the best thing. It's a solution, but it looks like a bad solution to me.

TheSENDER 2010-07-27 20:41:00

Testing the interface is greatly superior to testing the implementation. Later, when you refactor the implementation, your tests will still be valid.

If you feel that your methods are too complex to adequately unit test, perhaps that is an indication that you need to refactor your code and break it down into several smaller (potentially private) methods which can be tested seperately.

dbyrne 2010-07-27 18:21:42

Agree, except for (potentially private) I would say: public methods on another class used by the original class.

WW 2010-07-29 07:07:16

@WW: This is definitely an option to consider. My opinion is that it depends on how reusable you expect the new method to be. If it has the potential to be useful elsewhere, make it public on another class. If not, make it private. Since the poster's first instinct was to write one long method, I was assuming it wouldn't have much value elsewhere. However, I agree this should be re-evaluated when refactoring.

dbyrne 2010-07-29 12:28:23

To test if a implementation contains some restrictions (i.e: number of comparations, performance, etc.) you can TDD those constraints by using tests.

I found this twitter conversation very insightful: http://twitoaster.com/kentbeck/brunopedroso-i-think-you-could-tdd-quicksort-youd-need-assertions-about-the-of-comparisons-ways-to-incrementally-improve-the-count/

It talks about this idea: TDDing a quick sort. We know that a quicksort is faster than a bubble sort. Both algorithms will give the same output (a sorted collection), but they have different constraints.

So you explicitly add the constraints of your algorithm in your tests (you obviously need to test if your algorithm is doing what you expect it to do).

I agree that in this example you're tdding something that you already know the answer. However, if you must find a complex algorithm, you're probably not going to TDD it all the way. But the tests and constraints tests will help you know if you found the answer or not.

Edison Gustavo Muenz 2010-07-27 18:28:05

It seems to be a good idea. You test the algorithm without caring too much about the details of the implementation. What do you think that's the best way to code it?

TheSENDER 2010-07-27 20:47:55

To be honest, when I have to code these types of algorithms, I usually write the tests to see if it work. If I have a feeling that it can be improved and it needs to be improved, I will profile it, then write tests mostly on performance. I've never implemented an algorithm the way I posted on the link, but it might work. However, I don't believe that revolutionary algorithms can be discovered this way. You need a strong math background, the tests are there just to help, not to make it work.

Edison Gustavo Muenz 2010-07-29 04:05:55

I have found the example TDD/BDD in RSpec book very useful -http://www.pragprog.com/titles/achbd/the-rspec-book this could be some what rails oriented but in the book the author goes from defining the problem, to identifying the simple test cases to complex cases in an intuitive manner. The example in that book is about developing a game and its progress towards towards passing all the tests.

Also this could be useful for you because you are talking about interfaces and the BDD is about testing behavior of the application(in your case algorithm).

satyajit 2010-07-27 18:35:07

If your implementation is complex, then it would be a good idea to break it down in smaller modules. These smaller modules would then have their own interface, which you would unit test. For instance, if you're solving Sudoku by doing a depth-first search, then it would pay to develop separately a depth-first search algorithm, and a Sudoku position enumeration algorithm. I blogged about this a while ago: http://matteo.vaccari.name/blog/archives/416

xpmatteo 2010-07-30 14:54:41

ansaurus

tags:

views:

answers:

tdd with non-trivial algorithms

related questions