|
锁定老帖子 主题：[探讨]通过实例再讨论TDD
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2004-07-30
在《测试驱动开发》(Kent Beck)的附录B，Kent Beck用了两页纸的篇幅，演示了一次完全以测试驱动的方式，开发计算斐波纳契数列。
先简短的抄一下代码，再谈谈我的看法。 第一个测试与第一次的代码 public void testFibonacci();
assertEquals(0,fib(0););;
}
int fib(int n);{
return 0;
}
第二个测试与第二次的代码 public void testFibonacci();
assertEquals(0,fib(0););;
assertEquals(1,fib(1););;
}
int fib(int n);{
if(n==0); return 0;
return 1;
}
对测试代码进行改进，使之更为通用 public void testFibonacci();{
int cases[][]={{0,0},{1,1}};
for(int i=0;i<cases.length;i++);{
assertEquals(cases[i][1],fib(cases[i][0]););;
}
再增加n=2的测试 public void testFibonacci();{
int cases[][]={{0,0},{1,1},{2,1}};
for(int i=0;i<cases.length;i++);{
assertEquals(cases[i][1],fib(cases[i][0]););;
}
不需要修改代码，测试就通过了。 再增加n=3的测试 public void testFibonacci();{
int cases[][]={{0,0},{1,1},{2,1},{3,2}};
for(int i=0;i<cases.length;i++);{
assertEquals(cases[i][1],fib(cases[i][0]););;
}
测试失败，于是修改代码，还是如法炮制 int fib(int n);{
if(n==0); return 0;
if(n<=2); return 1;
return 2;
}
然后，最为神奇的部分在下面的四次修改： 1： int fib(int n);{
if(n==0); return 0;
if(n<=2); return 1;
return 1+1;//注意这里
}
2： int fib(int n);{
if(n==0); return 0;
if(n<=2); return 1;
return fib(n-1);+1;//注意这里
}
3： int fib(int n);{
if(n==0); return 0;
if(n<=2); return 1;
return fib(n-1);+fib(n-2);;//注意这里
}
4： int fib(int n);{
if(n==0); return 0;
if(n==1); return 1;//注意这里
return fib(n-1);+fib(n-1);;
}
这是一个非常棒的过程。我们的讨论也从这里开始。 最后得到的这个函数，是一个递归函数，非常的简洁，但是往往会有效率问题。 （打住，告诉过你多少次了，不要考虑效率！） 不是我要考虑效率，只是这么简单的例子，要寻找别的设计方式，我只能从效率方面来说事。 OK，继续。假设我们要求9的斐波纳契数列的值，那么，fib函数就会去计算fib(8 )+fib(7)。然后我们再展开。 fib(9)=fib(8 )+fib(7) fib(9)=(fib(7)+fib(6))+(fib(6)+fib(5)) 注意，这里fib(6)就要被计算两遍。 fib(9)=((fib(6)+fib(5))+(fib(5)+fib(4)))+((fib(5)+fib(4))+(fib(4)+fib(3))) 注意，这里fib(5)要被计算3遍，fib(4)要被计算3遍。 理解我的意思了吗？这样的算法，存在严重的效率隐患。 如果我们要考虑效率，会如何写代码呢？ public int fib(int n);{
int value0=0;
int value1=0;
int value=0;
for(int i=0;i<=n;i++);{
if(i==1);{
value1=1;
value=1;
} else {
value=value0+value1;
value0=value1;
value1=value;
}
}
return value;
}
这个算法我就不解释了。有人也许会说，你这样不是TDD，你先写了程序！ 不要紧，我可以假装先写了测试代码 public void testFibonacci();{
int cases[][]={{0,0},{1,1},{2,1},{3,2}};
for(int i=0;i<cases.length;i++);{
assertEquals(cases[i][1],fib(cases[i][0]););;
}
然后再把刚才的那个程序写出来，这样有什么问题吗？这样还算是TDD吗？ 我仔细看了书了，Kent Beck说过“步伐”问题。我这样也可以算是TDD的，只是步子大了点。 那么我想说明什么问题呢？ 1、无论先写测试还是先写代码，都需要考虑设计问题 2、在写测试之前考虑设计问题，不是什么罪过 3、考虑设计思路的深入与否，决定了步伐的大小 4、步伐太小的设计考虑，可能会陷入死角，无法再优化下去。从上面的代码可以看到，要想使递归算法变成循环算法，不是重构能够做到的。 最终的结论是： 代码就像你的左脚，测试就像你的右脚。 你可以先迈左脚，再迈右脚。然后一直走下去。 也可以先迈右脚，再迈左脚。然后一直走下去。 只要你不是一直单脚跳着前进，你都会走得很稳，而且没有人看得出区别来。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2004-07-30
庄表伟 写道 那么我想说明什么问题呢？ 1、无论先写测试还是先写代码，都需要考虑设计问题 2、在写测试之前考虑设计问题，不是什么罪过 3、考虑设计思路的深入与否，决定了步伐的大小 4、步伐太小的设计考虑，可能会陷入死角，无法再优化下去。从上面的代码可以看到，要想使递归算法变成循环算法，不是重构能够做到的。 最终的结论是： 代码就像你的左脚，测试就像你的右脚。 你可以先迈左脚，再迈右脚。然后一直走下去。 也可以先迈右脚，再迈左脚。然后一直走下去。 只要你不是一直单脚跳着前进，你都会走得很稳，而且没有人看得出区别来。 这么简单的实例完全不能应付实际开发中的问题，甚至误导！ 在这么简单的实例下得出一大堆结论更觉得很别扭。 当然我说的并不完全反对TDD，我只是想说在下一大堆结论之前希望能看到足够的分析。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
firebody 写道 这么简单的实例完全不能应付实际开发中的问题，甚至误导！
在这么简单的实例下得出一大堆结论更觉得很别扭。 当然我说的并不完全反对TDD，我只是想说在下一大堆结论之前希望能看到足够的分析。 之所以举这个例子，是因为这本书看过的人会多一些。我说起来也方便。如果是举自己开发过程中碰到的情况，前因后果的一大堆，看客们可能早就没有兴致了。 举这个例子，其实还有一个前因，前段时间在讨论TDD的局限性时，就有不少人都认为TDD只能搜寻到局部最优算法。搜寻到的算法的优劣，取决于步长的大小。而对于步子小的人，并不能够“勤能补拙”“小步快跑”。步子小到一定的程度，更优化的结果就永远不可能得到。 最近我在用TDD开发一个框架，深切的体会就是，除了写测试、写代码、重构三种状态之外，还有一种状态，就是系统性的思考，没有这样的思考，就无法有一个整体性的把握。我的很多设计决策，都是在不在电脑面前时思考出来的。我相信，这是对TDD的一个有益的补充，而不是对它的否定。但是因为我用TDD的时间还不长，因此写出自己的想法来，和大家探讨。 BTW，回帖不需要引用全部文章的，这样太浪费版面了。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
引用 这个算法我就不解释了。有人也许会说，你这样不是TDD，你先写了程序！
No, No, No, 这恰恰就是TDD, 因为你在Kent Beck的代码基础上做了改动, 改写了fib(i)的实现, 但是你如何知道改写后的代码能够保持外部行为不变呢? 是最初写的testFibonacci()让你知道了新的循环算法是正确的. 引用 4、步伐太小的设计考虑，可能会陷入死角，无法再优化下去。从上面的代码可以看到，要想使递归算法变成循环算法，不是重构能够做到的。
重构和优化算法是不相干的, 重构目的是为了让人能够更好地读懂代码, 而优化算法目的是为了让机器更好地执行代码. 你的最终的结论很有趣: 引用 代码就像你的左脚，测试就像你的右脚。 你可以先迈左脚，再迈右脚。然后一直走下去。 也可以先迈右脚，再迈左脚。然后一直走下去。 只要你不是一直单脚跳着前进，你都会走得很稳，而且没有人看得出区别来。 但是......, 偶看过一直跳着左脚走路的, 但是还没有看过一直跳着右脚走路的: 测试代码不能帮你自动产生逻辑代码吧??? btw, 几天前正好看到, 关于拓扑递归的一篇有趣文章, 里面有提到理论上任何递归算法都可以转变成循环算法, 有人知道哪里有这个理论的说明吗? 引用 http://www.library.utoronto.ca/see/SEED/Vol4-1/McNeil.htm 3.1 COMPUTATIONAL RECURSION AND ITERATION For some people, recursion — sometimes identified with “reflexivity” — has been freighted with special and almost magical significance in the fields of general system(s) theory, second order cybernetics, and semiotics. For others it means nothing more than recurrence or repetition or cycling or looping. Mathematicians, especially those concerned with computation theory, staked strong claims on a particular concept of “recursion” long ago, so their definition deserves our immediate attention. In the theory of computation as enunciated by Gödel, Church, Turing, von Neumann, et al. (Hofstadter 1979), “recursion” is a repetitive process in which the result of an algorithm is specified in terms of “itself.” Recursion in this mathematical sense stands in a dual or equivalence relation with mathematical iteration which is defined to be a repetitive process in which the result of an algorithm is specified in terms other than itself, typically terms of lower order. A theorem of the theory of computation tells us that for every recursive algorithm there is an iterative algorithm which will produce the same result and vice versa. It is beyond the scope of this article to consider whether this theorem can be generalized to hold for any process of any kind in any realm whatsoever, but the reader is invited to consider the possibility. |
| 返回顶楼 | |
|
发表时间：2004-07-30
Readonly 写道 btw, 几天前正好看到, 关于拓扑递归的一篇有趣文章, 里面有提到理论上任何递归算法都可以转变成循环算法, 有人知道哪里有这个理论的说明吗?
大学时，老师也提过这个论点。他说递归清晰易写，但性能低；循环难写，但性能高。没说明出处。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
to:ReadOnly
1、我也认为自己这样是TDD呀。 2、我要讨论的是设计问题，算法是设计的一部分。而我想说的是，仅仅通过在已有的代码基础上重构，可能无法得到更好的设计。 3、一直跳着右脚走路的人不多，但是如果你先一口气写个十个八个TestCase，然后再开始写自己的代码，看起来是效率高了，但是同样可能出问题。一左一右的意思是：每次只考虑一个问题，然后验证（或者用代码来验证测试，或者用测试来验证代码）。然后再往前走。 4、递归能够转成循环，但是有自动转的算法吗？如果有，我这篇文章算是没写过。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
庄表伟 写道 最终的结论是：
代码就像你的左脚，测试就像你的右脚。 你可以先迈左脚，再迈右脚。然后一直走下去。 也可以先迈右脚，再迈左脚。然后一直走下去。 只要你不是一直单脚跳着前进，你都会走得很稳，而且没有人看得出区别来。 从这个例子中应该得不到这样的结论吧！个人觉得这个比喻也不太好，不能很好的说明代码和测试之间的关系。左脚和右脚相对来说是独立、等价的，而代码和测试则显然不是这样，而且走路和编程则完全是两码事，差别大了去。 为了软件的质量，测试一般来说是必须，因为这个原因，所有才会出现一个先写和后写测试的问题。为什么有TDD，那时因为先写会比后写带来更多的好处。这些好处已经听说的够多了，但仍需要我们从实践中去享受。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
to:后山
比喻永远都会有问题。我还是说我的理由吧： 之所以用左右脚做比喻，就是因为以往我们都是先写代码后写测试，项目一紧，我们就“忘了”写测试。TDD里矫枉过正的指导我们必须先写测试。而我认为，只要一次解决一个问题，哪个先写、哪个后写是没有区别的。 但是，可以先写代码，并不是可以“忘了”写测试的借口。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
聽過所謂的 Greedy Algorightm 嗎? 簡單的說，就是在對環境所知有限的情況下，儘量去求得有限的最佳解，並進一步的了解環境，再以之前的解為基礎，再儘量找最佳解。
這個演算法不一定能求得真正的最佳解，除非問題本身有些特性，找到的才是最佳解。而一般性的問題，如果不能知道所有環境的狀態，是不可能找出最佳解的。 以我來看， TDD 有點這個味道。對我們一般所遇到的問題來看，是不太可能一次看到所有的環境的(環境可想像成未知的變數) ，我們一次一步，在我們所建立的測試環境中想辦法求最佳解 (光這點就不容易了) ，而這個做法想當然耳通常不是真正的最佳解。但，這已經是相對來說比較系統化而且容易進行的方法了。 庄兄說可以加入"系统性的思考"這個狀態，這對問題本身來說當然是有好處的，就像我們寫 parser 時也要偷看下一個 token 才能分析語法一樣。但"偷看"這件事可是問題多多的，而且通常造成的結果是 overdesign 。 如果 TDD 就是結論的話，那就是把 Greedy Algorightm 當做是 Optimal solution ，但在面對一般軟體系統的複雜來看，除非是早就把要寫的東西摸清楚了 ( 早就"偷看"下好幾步了… )，不然 TDD 算是”雖不中，亦不遠矣”的一種願望。當然，偉大的程式一定是會要有"系统性的思考"的，而這也就是偉大和平凡的差別。 ps: 有關遞迴和循序的轉化，在 Knuth 的 concrete math 中有蠻多著墨的。但就算所有遞迴都能轉成循序 (我不確定…@@) ，但實際上手工去轉換幾個就會吐血了 (knuth 書中有許多習題) 。 |
| 返回顶楼 | |
|
发表时间：2004-07-30
to:wctang
我要说的就是你的这个意思。但是又不只是你的这个意思。 系统性的思考，不是偷看，而是努力试图把握整体。 低头拉车，抬头看路。如果脖子伸得再长些，还是有很多好处的。 |
| 返回顶楼 | |
