22

私が遭遇したプログラミングの問題の 1 つは、大きな数 (10^5 までの数) の階乗の計算に関係しています。このような単純なHaskellコードを見てきました

factorial :: (Eq x, Num x) => x -> x
factorial 0 = 1
factorial a = a * factorial (a - 1)

これは巨大な数を暗黙的に処理し、コードに関与するキャッシュがなくても何らかの形で高速に実行されます。

Javaを使用して問題を解決しようとしたとき、BigIntegerを使用して膨大な数を保持し、階乗の反復バージョンも使用する必要がありました

public static BigInteger factorialIterative(int n)
{
        if(n == 0 || n == 1) return BigInteger.valueOf(1);
        BigInteger f = BigInteger.valueOf(1);
        for(int i = 1 ; i <= n ;i++)
            f = f.multiply(BigInteger.valueOf(i));
        return f;
}

上記のコードは、プログラムの設定された実行時間制限を超えました。factorial のキャッシュされた再帰バージョンも試しました

public static BigInteger factorial(int n)
{
     if(cache[n] != null) 
         return cache[n];
     else if(n == 0) 
         return new BigInteger("1");
     else {
         cache[n] = n* factorial(n - 1);
         return cache[n]; 
     }
}

これにより、メモリ不足エラーが発生しました（おそらく再帰が原因です）。

私の質問は、Haskell のような関数型プログラミング言語が、巨大な数が関係するこの種の問題を処理するのに優れているのはなぜですか? （明らかなキャッシュはありませんが）。Java コードを Haskell コードと同じくらい速く実行する方法はありますか?

4

5 に答える 5

10

最初に、速度の違いの理由ではないことは明らかですが、質問といくつかの回答で言及されている2つの要因を指摘したいと思います。

キャッシュ/メモ化なし

質問はキャッシングに言及しており、回答のいくつかはメモ化に言及しています。しかし階乗関数は、異なる引数で再帰的に自分自身を呼び出すため、メモ化の恩恵を受けません。したがって、すでにいっぱいになっているキャッシュ内のエントリにヒットすることは決してなく、キャッシュ全体は不要です。多分人々はここでフィボナッチ関数を考えていたのでしょうか?

記録として、Haskell はいずれにしても自動メモ化を提供しません。

他の巧妙な最適化はありません

Java と Haskell プログラムはどちらも、私にはすでにかなり最適に見えます。どちらのプログラムも、それぞれの言語で選択した反復メカニズムを使用します。Java はループを使用し、Haskell は再帰を使用します。どちらのプログラムも、大きな整数演算に標準型を使用します。

どちらかといえば、Haskell バージョンは末尾再帰ではないため遅くなるはずですが、Java バージョンは Java で利用可能な最速のループ構造であるループを使用します。

コンパイラがこれらのプログラムに対して行うことができる巧妙な高レベルの最適化の余地はあまりありません。観察された速度の違いは、大きな整数がどのように実装されているかについての低レベルの詳細が原因であると思われます。

では、なぜ Haskell バージョンの方が速いのでしょうか?

Haskell コンパイラには、組み込みの適切な整数サポートがあります。Java 実装と big integer クラスの場合は、そうではないようです。私は「BigIntegerが遅い」とグーグルで検索しましたが、結果は、質問が本当にあるべきであることを示唆しています:なぜJavaのBigIntegerはとても遅いのですか? より高速な他の大きな整数クラスがあるようです。私は Java の専門家ではないので、この質問の変種について詳しくはお答えできません。

于 2013-07-11T08:12:17.473 に答える
4

この違いは、テールコールの最適化や最適化とはまったく関係がないと思います。私が考える理由は、最適化は、せいぜい、反復的な Java バージョンのようなものしか達成できないからです。

本当の理由は、Java BigInteger が Haskell のものと比べて遅いということです。

これを確立するために、2 つの実験を提案します。

  1. 同じアルゴリズムを使用しますが、long を使用します。(結果は数値が大きいほどゴミになりますが、それでも計算は行われます。) ここで、Java のバージョンは Haskell と同等である必要があります。

  2. Java バージョンでより高速な大整数ライブラリを使用します。それに応じてパフォーマンスが向上するはずです。そこには GMP のラッパーがあり、ここのような Java の大きな整数の改善もあります。大きな数の乗算で可能な何倍ものパフォーマンスの改善が物語っています。

于 2013-07-11T08:10:24.137 に答える