|
锁定老帖子 主题：[探讨]通过实例再讨论TDD
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2004-07-31
我觉得TDD不应该考虑的那么深入，只要保证对外的行为一致就好了，换言之就是针对接口编写测试
在这个前提下，要求我们面向接口编程，这样的程序才是易测试的 |
| 返回顶楼 | |
|
发表时间：2004-07-31
庄表伟 写道 如果我们要考虑效率，会如何写代码呢？ 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;
}
try:
public int fib(int n);
{
final double sqrt5 = Math.sqrt(5);;
double value = (1/sqrt5);*(Math.pow(((1+sqrt5);/2);, n); - Math.pow(((1-sqrt5);/2);, n););;
return (int);value;
}
|
| 返回顶楼 | |
|
发表时间：2004-08-01
to:Arbow
你的帖子让我昨天困惑了一整天。我在考虑一个问题： 这个公式是怎么推导出来的。 后来我发现了： 假设有一个公式可以表示这个序列 f(n+2)=f(n+1)+f(n); 我们猜测 f(n)=a^n 那么：a^n+a^(n+1)=a^(n+2) 因此：1+a=a^2 因此可以求出 a=(1+sqrt(5))/2 或者 (1-sqrt(5))/2 因为f(0)=0 所以仅仅用f(n)=a^n是不够的。 所以我们可以用f(n)=a^n-b^n来表示这个函数。 然后我们就可以试探出 a=(1+sqrt(5))/2 b=(1-sqrt(5))/2 在乘上一个系数1/sqrt(5)就一切OK了。 这一步推出来之后，我真的很佩服自己的！ 但是，我进一步来思考效率问题，这样的算法，效率真的快吗？ 我在机器上做试验，发现由于多次计算n次方的原因，这样的n次方，相当于计算n次乘法，而原来的循环计算，最多计算n次加法。 因此，这个算法，对于计算机来说，并非最有效率的算法。 然后，我又加大数据，在n＝47的时候，这个算法，出现了误差，因为double的精度是有限的，当然，int型也是有限了。当我用BigInteger的时候，在n＝72的时候，再次出现误差，当然，我们还可以用BigDecimal来代替double，这样，它的效率就会进一步下降。 因此，这既不是一个最简洁易懂的算法，也不是一个最高效的算法，甚至不是一个最准确的算法。只能说，它是一个最“数学”的算法。 |
| 返回顶楼 | |
|
发表时间：2004-08-01
对，这是最数学的算法。说实话，我也不喜欢这样的算法，因为似乎看起来不易理解。
这个公式不是我推导，而是google的，在之前我也知道有这样一个计算公式可以方便的计算出Fibonacci的某一确定值。很抱歉让你困惑了一天，我应该注释一下的： /**
* 使用 Fibonacci 数列计算公式计算指定位的值
*@see http://zhjyx.hfjy.net.cn/Resource/Book/Edu/SZJY/TS007047/0009_ts007047.htm
*/
public int fib(int n);
{
final double sqrt5 = Math.sqrt(5);;
double value = (1/sqrt5);*(Math.pow(((1+sqrt5);/2);, n); - Math.pow(((1-sqrt5);/2);, n););;
return (int);value;
}
对上面的代码重构一下，改改变量名称，不必加太多注释，如果你想知道这个算法怎样来的，看看 @see那里就知道了（这是从Potian那里学回来的） 另外对于你所说的N次方效率不如累加效率高，我不太苟同，到底是在一个O(n)的循环中累加效率高，还是O(1)的Math.pow()效率高，我得做一下测试。 对于n比较小（50以下），两者都很快，但是当n很大的时候，就要用大整数来计算了（Java中是BigDecimal，BigInteger），这些大整数不能直接＋，只能用add()这样的方法来进行数值计算，我不相信多次这样的add()调用会比N次方的效率高多少。 总之我先试验一下才能确定，就这样讨论效率问题是没有任何意义的。 |
| 返回顶楼 | |
|
发表时间：2004-08-01
你也可以试一试，我是自己测试过了的。
但是把具体代码呀，高精度时间呀之类的东西帖出来，也确实比较麻烦。所以我就简单说说了。 关键在于一个问题，Math.pow()支持两个double参数，至于BigDecimal的pow，好像得自己写。 因此效率的差别，就变成n次BigInteger.add()和n次BigDecimal.multiply()的差别。 |
| 返回顶楼 | |
|
发表时间：2004-08-01
我的天，这个数学是怎么学的?
Fibonacci 数列的通项公式，可是高中数学题阿。拿张纸用等比数列推推就出来了么。 乘方，求幂，在计算机里都是要靠级数展开来做。n超过一定得量，就可能会比循环慢。 biginter,和bignumber的运算，和long int也是不同的，他们的运算都是用FFT来实现的，也就是快速傅立叶变换做的。 例如如果要计算Biginter的乘法，那么就要这样做。 1.对被乘数进行FFT变换，每个复数表示4位10进制数 2.对乘数进行FFT变换，每个复数表示4位10进制数 3.计算内积并除以n(长度) 4. 对积进行逆变换。 如果是浮点数，那就更加麻烦需要用到FNT，快速数论变换。 另外我觉得这种程序，如果讨论到biginter这种地步了，也就没有意义了。因为影响FFT 的主要是蝶形运算。这就需要用到非常好的矩阵算法库。而影响 FNT 算法最重要是的模乘法(a * b % p)的速度如何， 你的模乘法是如何实现的，我看到过的最快的模乘法(a * b % p)是这样的。 mov eax, a mov edx, b mul edx div p 所以java这种语言讨论小数目的就好了，用到bigint的还是算了吧。 FT，这问题已经跑的很远了。若要深入，自己去看<TAOCP>的半数值算法。 回到TDD的问题上来，你们觉得这种是先有鸡还是先有蛋的讨论有意义么？ |
| 返回顶楼 | |
|
发表时间：2004-08-01
斐波那契数列通项公式推导方法
Fn+1=Fn+Fn-1 两边加kFn Fn+1+kFn=(k+1)Fn+Fn-1 当k!=1时 Fn+1+kFn=(k+1)(Fn+1/(k+1)Fn-1) 令 Yn=Fn+1+kFn 若 当k=1/k+1，且F1=F2=1时 因为 Fn+1+kFn=1/k(Fn+kFn-1) => Yn=1/kYn-1 所以 Yn为q=1/k=1(1/k+1)=k+1的等比数列 那么当F1=F2=1时 Y1=F2+kF1=1+k*1=k+1=q 根据等比数列的通项公式 Yn=Y1q^(n-1)=q^n=(k+1)^n 因为k=1/k+1=>k^2+k-1=0 解为 k1=(-1+sqrt(5))/2 k2=(-1-sqrt(5))/2 将k1,k2代入 Yn=(k+1)^n ，和Yn=Fn+1+kFn 得到 Fn+1+(-1+sqrt(5))/2Fn=((1+sqrt(5))/2)^2 Fn+1+(-1+sqrt(5))/2Fn=((1-sqrt(5))/2)^2 两式相减得 sqrt(5)Fn=((1+sqrt(5))/2)^2-((1-sqrt(5))/2)^2 Fn=(((1+sqrt(5))/2)^2-((1-sqrt(5))/2)^2)/sqrt(5) |
| 返回顶楼 | |
|
发表时间：2004-08-01
Java 的BigDecimal 对这些计算的效率确实低下，我承认你的做法是最有效的。
|
| 返回顶楼 | |
|
发表时间：2004-08-01
我觉得这个TDD应该这么写
public void Rescurvie_Fibonacci();
{
.......
}
public void Improved_Fibonacci();
{
.......
}
public void test_Is_RescurvieFibonacci_Correct();{
int cases[][]={{0,0},{1,1},{2,1}};
for(int i=0;i<cases.length;i++);{
assertEquals(cases[i][1],Rescurvie_Fibonacci(cases[i][0]););;
}
public void test_Is_ImprovedFibonacci_Correct();{
int cases[][]={{0,0},{1,1},{2,1}};
for(int i=0;i<cases.length;i++);{
assertEquals(cases[i][1],Improved_Fibonacci(cases[i][0]););;
}
public void test_Is_Algorithm_Improved();
{
//Initial Data
long difference=1500;
long time=System.currentTimeMillis();;
Rescurvie_Fibonacci();;
long rescu_sec=System.currentTimeMillis();-time;
time=System.currentTimeMillis();;
Improved_Fibonacci();;
long impriove_sec=System.currentTimeMillis();-time;
long result=rescu_sec-impriove_sec;
assert(result>=difference);;
}
第一个测试程序只是验证运算的正确性，而修改算法以后需要验证的是运算速度是否提高。对于后一种需求，我们既可以简单的判断是否修改后的运算速度小于递归程序？也可以设立一个标准离差，说如果比递归快1500毫秒，那么这个修改算法就通过测试，否则不行。一旦当你有这样一个testcase的时候，它就能像Beck的例子那样不断的去驱动你重构你的算法。 TDD是用来描述需求的，不同的需求必然要不同的测试方案。所以这贴的关键失误就在于，需求变了，但是TDD没有跟着改变，所以这个TDD失败的案例只不过是刻舟求剑,愚人买鞋, 南辕北辙.....(还有什么成语来着?  )。如果是先从需求出发设计TDD，那么你就不会出现这样的问题。
|
| 返回顶楼 | |
|
发表时间：2004-08-01
thatway 写道 Readonly 写道 btw, 几天前正好看到, 关于拓扑递归的一篇有趣文章, 里面有提到理论上任何递归算法都可以转变成循环算法, 有人知道哪里有这个理论的说明吗?
大学时，老师也提过这个论点。他说递归清晰易写，但性能低；循环难写，但性能高。没说明出处。 这个问题，我都贴过好几次关于这个话题的文章阿。可就是没人看阿  
最清楚的解释请看这里。 http://forum.iteye.com/viewtopic.php?t=6383。 这是一个非常复杂的数学问题，牵涉到Turing-Church命题: Turing命题 可计算的函数集等于图灵机可计算的函数集。 Church命题 可计算的函数集等于递归函数集。 因此，Church命题与Turing命题等价，当然也和Turing Machine等价。 这个命题在计算机科学中是相当重要的基石，其地位等同于平面几何的公里。 不过，Church命题提出的时候，人们只是发现了像Fibonacci 这样的原始递归函数(primitive rescuvie)，但是后来在40年代Ackermann发现有一种递归函数不是原始递归函，但是这种递归函数并没有证明是与Turing命题等价的，如果一旦不等价，那么我们现在计算机科学可能就是另外一副样子。不过幸好后来别人证明这两者是等价的。 另外，recursion 性能低下是针对c/java这样的过程化语言说的，因为这些语言不一定能对付得了Tail recursion 。在Scheme,Haskell这样的语言里面，所有的循环都用recursion 替代，因为他们采用了Tai recursion .一旦使用了Tail recursion ，那么循环和递归的性能是一样的。学过编译原理的应该知道Tail recursion ，可以直接用goto实现，也就等价的我们通常的循环写法。几乎所有哪怕是弱智的函数式语言编译器都可以很简单的看到尾递归而且能将它们优化成goto其实也就是Asm中的Jmp。 例如Fib的普通递归是这样写的
int fib(int n);{
if(n==0); return 0;
if(n==1); return 1;
return fib(n-1);+fib(n-2);;
}
Tail recursion 是这么写的
int fib(int n);{
if(n==0); return 0;
return Tail_Recursion _Fib(n,1,0);
}
int Tail_Recursion _Fib(int n,int f1,int f2);
{
if(n==1);
return f1;
return Tail_Recursion_Fib(n-1,f1+f2,f1);;
}
什么是Tail Recursion ?通俗的形象的说就是最后一次递归调用的函数是函数本身(u:=T)，而普通递归前面还需要加上一个函数(u::=WT)。如果你的Java编译器能够帮你消除Tail recursion 的话，那么前面那个函数的运算速度，是随着n的指数级数增长，而后面那个是n的线性级数增长.用Shceme的话，其效率一定是和循环相当，如果用Java么你就祈祷你的Java编译器和Jvm或者JIT能帮取消Tail Recursion 吧 。我听说有些Java编译器和JVM或者JIT的确是这么做的,可惜也只是听说而已。没有试过。
至于什么是Tail recursion 真正的含义，以及怎么去把普通递归转为Tail rescuvie。 我的老天这就不是一句两句能说清楚了。要说清楚这个事情，得学习Chomsky文法，递归文法，左右递归，递归消除，扯出来比裹脚布还长。还是找本编译原理好好的回回炉吧，Tail recursion 是计算机科学中相当重要的技术。学好了相当有用的 |
| 返回顶楼 | |
