|Welcome to the Monastery|
Re: Why and how to re-use code to make better applications and you a better programmer. (discussion)by Sherlock (Deacon)
|on Jun 29, 2001 at 19:02 UTC||Need Help??|
This is almost exactly the process I use when I'm attempting to come up with an algorithm for something. Start with something concrete, then move to something abstract and test it against your concrete example that you started with.
There is one point that Carl seems to allude to, but never really seems to put his finger on that I'd like to address; Once you believe you have created an abstract case that is functional, you need to test that case against not only the concrete cases you've already generated, but also against any other cases you can think of - especially extreme cases.
Let me set up this quick example (probably more related to C++, but this is something I recently did, so it's fresh in my mind). I needed to write a simple function to add an element to a home-rolled linked-list type structure. To accomplish this, I first created a test list and a test element and simply inserted it into the list to make sure that it worked. I then inserted another element into the list in another position to see what had changed. This would be equivalent to Carl's steps 1 & 2, I believe. Next, I wrote a general solution (a function) that would insert an element for me and I used that function to insert the two elements that I had already inserted in the previous two steps. (Carl's steps 3 & 4) Once that was working, I was reasonably sure that I now had a working solution.
What I still had left to do was to test my solution against all possible situations. I'm sure you all know what an impossible task that is. The goal here is to partition your inputs into "domains." The idea behind these domains is to test as much of your function domain as possible in as few test cases as possible (Classic laziness). The goal is to have a number of "domains" of input in which, if you select a set of inputs from one of your domains, most of the other inputs that you could have selected from that domain will either fail or succeed, just as the one you selected. Again, let me refer to my example.
My inputs really only consisted of one thing - the position at which I wanted to insert the element into the list. The "domains" I came up with consisted of: front of the list (index == 0), whithin the list (index > 0 && index < numItems - 1), end of list (index == numItems - 1). I tested my solution three times (this is in addition to against the concrete examples I had already utilized), once from each domain. So, simply put, I tested my solution by inserting an element into the front, middle, and end of the list - as dictated by my domains.
Separating your inputs into domains is seldom such a trivial process as it was in this case. The more inputs you add, the more test cases you'll have to utilize (just another benefit to small, concise functions). This step is somewhat of an art and it takes practice to master (I surely haven't done it yet), but I feel that this is one of the most important steps in making reusable code.
So what I'm really getting at is that I'd like to ammend Carl's step 5 to include greater testing of the algorithm. I think he treated that just a little too lightly. He seemed to hint at it, "There may be a few remaining things to fix in the general solutions - a sample size of two is, after all, unlikely to be representative of most problem populations..." but I think this step needs to be stressed a little more.
That's just my opinion, though. This is, however, and excellent formalization of the steps taken to create an algorithm. Thanks.
Addendum: While previewing this post, I noticed a flaw in my domain partitions. Can you see it? You can view the source to see a further explanation.
Skepticism is the source of knowledge as much as knowledge is the source of skepticism.