C/Java/Python/Objective-C多種編程語(yǔ)言實(shí)現(xiàn)遞歸計(jì)算

遞歸下降語(yǔ)法分析器

• 類(lèi)型：源碼相關(guān)大小：34KB語(yǔ)言：中文 評(píng)分：5.0
• 標(biāo)簽：

立即下載

同樣的算法多種編程語(yǔ)言在Mac的OS X上跑會(huì)是個(gè)什么情況呢？

于是寫(xiě)了四種語(yǔ)言的斐波那契數(shù)列實(shí)現(xiàn)：C、Java、Python、Objective-C，而且都采用了效率最差耗時(shí)最長(zhǎng)的遞歸實(shí)現(xiàn)，不使用其他數(shù)據(jù)結(jié)構(gòu)或公式，這樣對(duì)比起來(lái)更容易一些，如果使用迭代方式的話(huà)，執(zhí)行時(shí)間太短很難比較。

第一輪測(cè)試不做任何優(yōu)化，第二輪分別做一些編譯和環(huán)境的調(diào)優(yōu)處理，然后再看一下結(jié)果。代碼如下：

c語(yǔ)言，使用函數(shù)實(shí)現(xiàn)遞歸計(jì)算

#include <stdio.h>

long fib(int n){
    if (n < 2)
        return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    printf( "fib= %ld", fib(40) );
    return 0;
}

Java，使用靜態(tài)方法實(shí)現(xiàn)遞歸計(jì)算

public class fib {

    public static long jfib(int n ){
        if (n < 2)
            return n;
        return jfib(n - 1) + jfib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println( jfib( 40 ) );
    }
}

Python，使用函數(shù)實(shí)現(xiàn)遞歸計(jì)算

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print fib(40) 

Objective-C，使用block實(shí)現(xiàn)遞歸計(jì)算

#import <Foundation/Foundation.h>

int main(int argc, const char * argv[])
{
    @autoreleasepool {
        
        long (^__block fib)(long) = ^(long num){
            if ( num < 2 )
                return num;
            return fib(num-1) + fib(num-2);
        };
        
        NSLog(@"Fib: %ld", fib(40) );
        
    }
    return 0;
}

基本的測(cè)試環(huán)境：

C語(yǔ)言：i686-apple-darwin11-llvm-gcc-4.2

Java：java version "1.6.0_37"，HotSpot(TM) 64-Bit

Python：Python 2.7.2 with GCC 4.2.1

Pypy：PyPy 1.9.0 with GCC 4.2.1

Objective-C：2.0 with LLVM 4.1

使用time命令計(jì)算執(zhí)行時(shí)間，例如time python fib.py

直接編譯運(yùn)行的結(jié)果還是比較讓人吃驚的：

C：1 秒

Java：0.63 秒

Python：45.79 秒

Objective-C：1.3 秒

結(jié)果：Java > C > Objective-C > Python

這個(gè)結(jié)果讓人感到，Java真的不慢，動(dòng)態(tài)語(yǔ)言有點(diǎn)慢。

第二輪測(cè)試，針對(duì)C程序，使用gcc -O進(jìn)行優(yōu)化編譯；針對(duì)Python，使用pypy替換原生的python環(huán)境，針對(duì)Objective-C，設(shè)置優(yōu)化Level為Fastest，結(jié)果如下：

C：0.35 秒

Java：0.63 秒

Python：4.96 秒

Objective-C：1.04 秒

結(jié)果：C > Java > Objective-C > Python

這個(gè)結(jié)果告訴我們，C還是最快的，pypy對(duì)python的優(yōu)化處理還是非常明顯的。 

以上數(shù)據(jù)是在OS X平臺(tái)上的、性能比例放大的測(cè)試結(jié)果，在實(shí)際應(yīng)用中，如果針對(duì)不同場(chǎng)景采用了正確的算法，差距就不會(huì)有這么大，比如我們用迭代方式改寫(xiě)一下python的實(shí)現(xiàn)，如下：

def fib(n):
    if n < 2:
        return n
    a1 = a2 = a3 = 1
    while n>2:
        n -= 1
        a3=a1+a2
        a1=a2
        a2=a3

    return a3

print fib(40)

這時(shí)無(wú)論使用Python編譯執(zhí)行還是Pypy執(zhí)行，基本都是0.02秒左右，沒(méi)有太大差別。以上代碼的執(zhí)行結(jié)果是102334155，有興趣的可以在自己的機(jī)器上試試。

聲明：

1、以上代碼僅供參考娛樂(lè)，實(shí)際應(yīng)用中如果使用斐波那契數(shù)列，絕對(duì)不要使用遞歸調(diào)用的方式，迭代法應(yīng)該是不錯(cuò)的選擇。

2、數(shù)據(jù)量加大可能會(huì)有不同的結(jié)果，有興趣的可以嘗試下。

實(shí)驗(yàn)完成，希望對(duì)大家有參考。