JVMは最後の再帰を最適化しているかどうか
1841 ワード
JVMは、最後の再帰を最適化していますか?
いくつかのブログを見て、ないと言って、JDK 8の下でテストをしました.
fiboniccは普通の再帰で、遅いです.
fibonicc 2はテール再帰実装であり、fibonicc 2(5000,1,1)は通常の再帰よりも1092785ナノ秒かかります.
fibonicc 3はサイクル実装であり、fibonicc 3(5000)は419347ナノ秒かかり、テール再帰よりも速い.
fibonicc 4はfobonicc 2の時間複雑度と一致する非テール調であり,1132819時間かかり,テール再帰との時間差は多くないようである.
いくつかのブログを見て、ないと言って、JDK 8の下でテストをしました.
package fibonicc;
public class Test {
//1 1 2 3 5 8
private static int fibonicc(int n) {
if(n<=1) {
return 1;
}
return fibonicc(n-1)+fibonicc(n-2);
}
//n n=1
private static int fibonicc2(int n,int last,int total) {
if(n==1) {
return total;
}
return fibonicc2(n-1,total,last+total);
}
//
private static int fibonicc3(int n) {
if(n<=1) {
return 1;
}
int last = 1;
int current = 1;
int i=2;
int tmp = current;
while(i++<=n) {
tmp = current;
current = last+current;
last = tmp;
}
return current;
}
private static int fibonicc4(int n,int last,int total) {
if(n==1) {
return total;
}
int result = fibonicc4(n-1,total,last+total);
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// System.out.println(fibonicc(50));
long start = (System.nanoTime());
System.out.println(fibonicc2(5000,1,1));
System.out.println(System.nanoTime()-start);
start = (System.nanoTime());
System.out.println(fibonicc3(5000));
System.out.println(System.nanoTime()-start);
start = (System.nanoTime());
System.out.println(fibonicc4(5000,1,1));
System.out.println(System.nanoTime()-start);
}
}
fiboniccは普通の再帰で、遅いです.
fibonicc 2はテール再帰実装であり、fibonicc 2(5000,1,1)は通常の再帰よりも1092785ナノ秒かかります.
fibonicc 3はサイクル実装であり、fibonicc 3(5000)は419347ナノ秒かかり、テール再帰よりも速い.
fibonicc 4はfobonicc 2の時間複雑度と一致する非テール調であり,1132819時間かかり,テール再帰との時間差は多くないようである.