Fibonacci 数列

[erlang]

看到这个比较有趣的Fibonacci数列对比: http://fengmk2.github.com/blog/2011/fibonacci/nodejs-python-php-ruby-lua.html

我想知道 Erlang 与他们比起来怎么样,于是测了一下:

参考:http://en.literateprograms.org/Fibonacci_numbers_(Erlang)

第3种(Fast tail recursive fibonacci)和第2(Tail recursive fibonacci)种方式结果如下,有趣的是,第2种好像比第3种略好:

$ time ./a.erl 40 3

real    0m0.131s
user    0m0.115s
sys 0m0.015s

$ time ./a.erl 40 2

real    0m0.128s
user    0m0.114s
sys 0m0.014s

第1种(The fibonacci function),也就是教科书上那最经典的例子,在我机器上运行了18分钟还没完成。分别把N改为30和35,结果为

$ time ./a.erl 30 1

real    0m21.611s
user    0m21.576s
sys 0m0.033s

$ time ./a.erl 35 1

real    3m55.764s
user    3m55.561s
sys 0m0.199s

难道第1种方法就这么糟?仔细看了一下算法,发现潜在的有好多重复的计算,于是,改了一下代码,把中间的计算结果都 "cache" 一下,最后结果如下:

time ./a.erl 40 4

real    0m0.134s
user    0m0.118s
sys 0m0.016s 

比起所谓的“Fast”算法也不差嘛。

为了与其它语言有个比较,我的机器与作者的不一样,因此试了一下C语言的,使用 -O2, gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)。

$ time ./a.out 
102334155

real    0m0.069s
user    0m0.067s
sys 0m0.001s

比作者的机器快3倍,因此 Erlang 的结果 0.115 * 3 = 0.345,大致比 node.js 略差,比其它脚本语言都好。当然,上面是用 escript 做的,编译成 beam 应该更好一点。完整的脚本如下:

!/usr/bin/env escript

%% http://en.literateprograms.org/Fibonacci_numbers_(Erlang)

fibo1(0) -> 0 ; fibo1(1) -> 1 ; fibo1(N) when N > 1 -> fibo1(N-1) + fibo1(N-2) .

fibo2_tr( 0, Result, _Next) -> Result ; %% last recursion output

fibo2_tr( Iter, Result, Next) when Iter > 0 -> fibo2_tr( Iter -1, Next, Result + Next) .

fibo2(N) -> fibo2_tr( N, 0, 1).

fibo3(N) -> {Fib, _} = fibo3(N, {1, 1}, {0, 1}), Fib.

fibo3(0, _, Pair) -> Pair; fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 -> SquareFib1 = Fib1Fib1, fibo3(N div 2, {2Fib1Fib2 - SquareFib1, SquareFib1 + Fib2Fib2}, Pair); fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) -> fibo3(N-1, Pair, {FibA1FibB2 + FibB1(FibA2 - FibA1), FibA1FibB1 + FibA2FibB2}).

%% cached improvement of fibo1/1

fibo4(0) -> 0; fibo4(1) -> 1; fibo4(N) -> N2 = case get(N-2) of undefined -> X = fibo4(N-2), put(N-2, X), X; X -> X end,

N1 = case get(N-1) of
    undefined ->
        Y = fibo4(N-1),
        put(N-1, Y),
        Y;
    Y -> Y
end,

% io:format("~p~n", [N2 + N1]),
N2 + N1.

main([N, "1"]) -> fibo1(list_to_integer(N)); main([N, "2"]) -> fibo2(list_to_integer(N)); main([N, "3"]) -> fibo3(list_to_integer(N)); main([N, "4"]) -> fibo4(list_to_integer(N)).

最后,来个金字塔:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155

七歌
微信扫一扫