5

scala と関数型プログラミングを学習する演習として、任意の場所でパスカル数を計算する次の非末尾再帰的定義を実装しました。プログラム自体がパスカルの三角形の定義として機能します。絵的には以下のようになります

      1
    1  1
   1  2  1
  1 3   3 1
 1 4  6  4 1
1 5 10 10 5 1
...

def pascal(c: Int, r: Int): Int =
  if (c == 0 || c == r) 1 else pascal(c - 1, r - 1) + pascal(c, r - 1)

ただし、Mac OS X 10.6.8 (2.53 GHz Intel Core 2 Duo) で実行しようとすると、 20 分pascal(25,50)経ってもまだ実行が完了していません。

erlang と比較するために、R15B02 をインストールし、次のように同等のプログラムを作成しました。

-module(pascal).
-export([calc_pascal/2]).

calc_pascal(0,_) -> 1;
calc_pascal(C,R) when C==R -> 1;
calc_pascal(C,R) when C<R  -> calc_pascal(C-1,R-1) + calc_pascal(C-1,R).

pascal:calc_pascal(25,50)〜4秒で終了します。

このような大きなパフォーマンスの違いの理由は何でしょうか? jvm は、再帰プログラムの erlang ランタイムほど高度ではありませんか?

4

2 に答える 2

13

あなたがErlangバージョンで犯したのと同じ間違いをScalaプログラムで私が犯した場合、それは非常に高速に実行されます. これが原因かも？

于 2012-09-23T13:10:46.407 に答える
3

パスカルの数のパフォーマンス（ミリ秒）

c,r     Scala   Erlang
10,20   21      22
11,22   6       72
12,24   16      272
13,26   71      1034
14,28   299     3982
15,30   802     16124
16,32   3885    60420
于 2012-09-23T14:49:59.217 に答える