[探讨]通过实例再讨论TDD

看起来现在的编译器和JVM都还是支持Tail Recursion 的亚
AMD 2500+ 512M,Sun Java 1.4.2

public class test1 {	
	long fib1(long n);{ 
		if(n==0); return 0; 
		if(n==1); return 1; 
		return fib1(n-1);+fib1(n-2);; 
	} 
	long Tail_Rescuvie_Fib(long n,long f1,long f2); 
	{ 
                 return (n==1);?f1:Tail_Rescuvie_Fib(n-1,f1+f2,f1);;  
	} 
	long fib2(long n);
	{ 
	   return (n==0);?0:Tail_Rescuvie_Fib(n,1,0);;
	} 
	public static void main(String  [] args);
	{
	    test1 t=new test1();;
	    long n=40;
	    long time=System.currentTimeMillis();;
	    long ret=t.fib1(n);;
	   System.out.println("Fib1 used"+(System.currentTimeMillis();-time););;
	   System.out.println("Fib1 result="+ret);;
	   time=System.currentTimeMillis();;
	   ret=t.fib2(n);;
	   System.out.println("Fib2 used"+(System.currentTimeMillis();-time););;
	   System.out.println("Fib2 result="+ret);;
    }
}

结果
Fib1 used3719
Fib1 result=102334155
Fib2 used0
Fib2 result=102334155

这简直不是一个数量级阿。


------------------------
刚才又测试了循环的做法。
但是庄的算法到了50
输出结果为-298632863
而Tail Recursion 却是正常的。
好奇怪阿。
Long溢出了？不会阿。正在查原因
原来是庄的value0,value1,value都用的是int,

Tail Recursion 的效率和循环相当阿
这是n=100时候的结果
Fib2 used0
Fib2 result=3736710778780434371
Fib3 used0
Fib3 result=3736710778780434371

太强了，Tail rescusive，我的编译原理白学了。

对

	long Tail_Rescuvie_Fib(long n,long f1,long f2); 
	{
		return (n==1);?f1:Tail_Rescuvie_Fib(n-1,f1+f2,f1);;
	} 

和

	long fib(long n);
	{ 
		if(n==0); return 0; 
		if(n==1); return 1; 
		return fib(n-1);+fib(n-2);; 
	} 

分别用javap反编译了一下：

long Tail_Rescuvie_Fib(long,long,long);;
  Code:
   0:	lload_1
   1:	lconst_1
   2:	lcmp
   3:	ifne	10
   6:	lload_3
   7:	goto	22
   10:	aload_0
   11:	lload_1
   12:	lconst_1
   13:	lsub
   14:	lload_3
   15:	lload	5
   17:	ladd
   18:	lload_3
   19:	invokevirtual	#2; //Method Tail_Rescuvie_Fib:(JJJ);J
   22:	lreturn

long fib(long);;
  Code:
   0:	lload_1
   1:	lconst_0
   2:	lcmp
   3:	ifne	8
   6:	lconst_0
   7:	lreturn
   8:	lload_1
   9:	lconst_1
   10:	lcmp
   11:	ifne	16
   14:	lconst_1
   15:	lreturn
   16:	aload_0
   17:	lload_1
   18:	lconst_1
   19:	lsub
   20:	invokevirtual	#2; //Method fib:(J);J
   23:	aload_0
   24:	lload_1
   25:	ldc2_w	#3; //long 2l
   28:	lsub
   29:	invokevirtual	#2; //Method fib:(J);J
   32:	ladd
   33:	lreturn

不知道是否已经在此处进行了优化，先研究一下

优化的部分可能是在JIT，而不是在Javac这里。因为对伪代码优化是没有意义的，只有机器指令里面优化才具有实际效果。不过你这段伪代码已经很说明问题了
你看如果把invokevirtual 改成Jump  0，不就是和循环一抹一样了么？

对的，实际优化是在JIT中。
但是由于使用了尾递规，才能让 invokevirtual   #2 这个调用留在末尾，方便了JVM对其进行优化，使其效率达到迭代的水平。

而原始递规算法不能优化，只能进行大量堆栈操作，使两者速度相差几个数量级。

我刚刚又想了一下
那个test_Is_Algorithm_Improved 做这样的修改，那么算法优化的refectoring就和beck的例子差不多了。

public void test_Is_Algorithm_Improved(); 
{ 
hashtale table;
table.put(20,3500);
table.put(30,2500);
table.put(40,1500);

Enumerator e=hashtable.key();
while(e.hasmoreElemet(););
{
  long n= (long);e.nextElement();;
  long difference= table.get(n);;   
  long time=System.currentTimeMillis();; 
  Rescurvie_Fibonacci(n);; 
  long rescu_sec=System.currentTimeMillis();-time; 
  
  time=System.currentTimeMillis();; 
  Improved_Fibonacci(n);; 
  long impriove_sec=System.currentTimeMillis();-time; 
  long result=rescu_sec-impriove_sec; 
  assert(result>=difference);; 
}
} 

当然，table里面的测试数据是假的，并且Fibonacci算法的复杂度也是很平稳的。如果我们假设Fibonacci的原始算法会随着n的增长而变化的话。那么Beck说的步骤性，在这个TDD里面也能够体现出来了。假如说20的时候，Tail rescuvie最快，30的时候，Tail rescuvie不能满足要求了，那么我们回去用通项公式，到了40的时候通项公式又不行了，我们会找到循环算法。
那么你的算法优化就跟着这个Test case一步一步的进行优化。
当然这只是为了说明问题而作的一些假设，Fibonacci算法本身不会出现这样的波动。但是有很多算法的确会这样，比如说sort.我们一直知道quick sort是最快速的算法。但是你可以去看STL中的sort算法，其实是一种复合算法。对于不同的基数，每种算法的效率是不同的，Shell Sort的复杂度是不稳定的，但是平均在n的1.2幂，而quick Sort的话是O(log2(n)*n).因此如果基数小于一个定值的话，quick sort就要比Shell慢。而超过这个基数 quick sort就快，但是大于一定的基数，如果不做分段处理的话那既是是用quick sort也难以得到满意的结果。如果我们把上面的测试程序改成quicksort的算法优化的话，Beck的步骤性就很明显了.例如我们可以规定，在基数为1000,10000,1000000三种不同条件下的数值离差结果，那么我们就可以按照Beck的小步骤refector你的算法代码，为sort提供一个很好的复合算法。

世界上没有绝对的真理，只有对真理的不同解释。问题是这个解释要花费你多大的代价。比如两个极端 XP 和 CMM。有人说道：CMM 现在也敏捷了啊，CMM 和敏捷完全不矛盾，你凭什么说 CMM 落后了？！问题是从 CMM 的观点出发你要迂回多少弯路才能得出与 XP 相同的结论，这中间有无数的岔路和陷阱足以使你事倍功半或者劳而无功，可能只有上帝最后才能走到敏捷的这条路上来（有人又说了，为什么一定要得出与 XP 相同的结论？你的脑子是不是有点问题？这是因为我觉得 XP 的结论是对真理更好的解释。如果这个还需要争论那我可就不奉陪了，我还有一堆事情要忙。你先在 CMM 那些没有营养的书堆里绕上几年再说吧）。这个成本你是否可以接受？如果无法接受，可不可以直接走 XP 这条便捷的小路，虽然看起来比较简陋（也只是看起来而已），似乎除了建造一个勉强可用的狗窝以外没有多大用处。
如同牛顿万有引力定律一样，TDD 是对真理很好的近似。实施 TDD 所遇到的具体困难我更愿意在这个框架内部解决而不是推翻整个框架。我觉得从大的方面看 TDD 是可以自圆其说的，也就是自恰的。算法的优化如果确实是一种需求，是应该先为这个需求写自动测试的，这个就是 TDD。

TDD，遇到的困难，我想大都是遇到了非形式化的问题。  例如GUI，的这些问题，其实已经和TDD没有太大的关系了。TDD着眼解决的是形式化的问题，而GUI这些问题是非形式化的问题。换句江湖黑话说，"美观"不是形式化的定义，因此无法用以Turing-machine为基础的计算机程序加以解决。

   另外今天早上，我又思考了一下Fibonacci和TDD的问题。其实庄所要反驳的东西是存在的，只是方案就在他眼前他却不知道。
我们来看看这样的TDD行不行?
第一步

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);{ 
    int [] fib_table={0，1};
    return fib_table[n]; 
}

第二步

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]););; 
} 

int fib(int n);{ 
    int [] fib_table={0，1};
    return fib_table[n]; 
}

第三步

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]););; 
} 

int fib(int n);{ 
    int [] fib_table={0，1，1};
    return fib_table[n]; 
}

第三步

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);{ 
    int [] fib_table={0，1，1，2};
    return fib_table[n]; 
}

好了，到这里TDD，就彻底失败了。无论你测试的步骤有多小，或者有多大，经过多少次步骤，(你每加一个步骤，设计只不过扩大一下列表而已)。你都不可能refector出fib算法，而且这个算法的运算效率比循环和Tail rescusion还要高，复杂度为O(1)。
  因此庄所讨论的问题，的确是存在的。同样一套TestCase,原则上至少会有两个不同的设计能够完全满足这套TestCase。因此TDD对设计不是决定性的，或者说不具备指导性。一般来说一个先验的猜测和想法，决定了设计的总方向。而TDD只是保持这个设计总方向的不变性，而TDD本身并不提供任何设计总方向上的指导或者提供任何思考的线索。

你这些代码展示的是一种不正确的TDD过程，或者说TDD还没有完成。任何人都知道你的fib方法是有问题的，程序不是这样写的，也不是TDD要达到的“清晰能工作的”代码。

了解Fibonacci算法的人大概直接就可以写很好的testcase，而不了解算法的，只能如例子那样一步一步的进行，直到你发现内部规律，这其中有可能需要跳跃性的思维。如果象Trustno1例子中按部就班的走，走到第四步，你不能发现规律，那就说明你还没有这方面的经验；你还可以继续往下走，走到第6、7步，这时你从{0，1，1，2，3}无意（突然）可能就发现了规律；如果你走到第10步，还不能发现，这时，你就需要停下来仔细的想想，要不是一开始就走错了，要不就暂时放一段时间，冷静一下，这和现实中推导数学公式是差不多的。

这你就恰恰错了，你若是拿别的问题来说，的确是可以这么说。但是对于Fibonacci来说，你就错了。我写的这个算法，其实是一个非常有用的算法。叫查表法。对任何以整数作为参数的算法，查表法是最好，最快的算法，其复杂度为O(1)。这种算法在数值计算中经常使用，因为我们知道我们要让计算机计算的结果总是有限精确的，因此当我们知道需要的精度以后。就能把很多数值预先算好，存放在表中。以获得最快的运算速度。
如果说例如计算快速傅立叶变换，需要大量计算sin，但是sin的计算是用级数展开的，这会让本来就非常复杂的FFT，消耗更多的资源。因此基本上所有的FFT中使用的sin,都是将sin的离散定义域与数组下标做出映射转换，然后查表求值。
这样会将FFT的运算速度提高5-10倍。