31

ネタバレ注意、これはプロジェクトオイラーの問題5です。

私はClojureを学習して問題5を解決しようとしていますが、数桁遅くなっています（Javaでは1515ミリ秒、Clojureでは169932ミリ秒）。型のヒント、チェックされていない数学演算、インライン関数をすべて無駄に使ってみました。

Clojureコードが非常に遅いのはなぜですか？

Clojureコード：

(set! *unchecked-math* true)
(defn divides? [^long number ^long divisor] (zero? (mod number divisor)))

(defn has-all-divisors [divisors ^long num]
  (if (every? (fn [i] (divides? num i)) divisors) num false))

(time (prn (some (fn [^long i] (has-all-divisors (range 2 20) i)) (iterate inc 1))))

Javaコード：

public class Problem5 {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    int i = 1;
    while(!hasAllDivisors(i, 2, 20)) {
      i++;
    }
    long end = System.currentTimeMillis();
    System.out.println(i);
    System.out.println("Elapsed time " + (end - start));
  }

  public static boolean hasAllDivisors(int num, int startDivisor, int stopDivisor) {
    for(int divisor=startDivisor; divisor<=stopDivisor; divisor++) {
      if(!divides(num, divisor)) return false;
    }
    return true;
  }

  public static boolean divides(int num, int divisor) {
    return num % divisor == 0;
  }
}
4

3 に答える 3

56

いくつかのパフォーマンスの問題：

  • 呼び出しは、の(range 2 20)増分ごとに番号の新しい怠惰なリストを作成していますi。これは高価であり、多くの不要なGCを引き起こしています。
  • あなたは関数呼び出しを通過することによって多くのボクシングをしています。でも、(iterate inc 1)すべての増分でボクシング/アンボクシングを行っています。
  • 除数のシーケンスをトラバースしています。これは、まっすぐな反復ループよりも低速です
  • mod現在、Clojureでは実際にはあまり最適化されていない関数です。あなたは使用する方がはるかに良いですrem

letステートメントを使用して範囲を1回だけ定義することにより、最初の問題を解決できます。

(time (let [rng (range 2 20)]
  (prn (some (fn [^long i] (has-all-divisors rng i)) (iterate inc 1)))))
=> "Elapsed time: 48863.801522 msecs"

loop/recurで2番目の問題を解決できます。

(time (let [rng (range 2 20)
           f (fn [^long i] (has-all-divisors rng i))]
       (prn (loop [i 1] 
              (if (f i)
                i
                (recur (inc i)))))))
=> "Elapsed time: 32757.594957 msecs"

3番目の問題は、可能な除数に対して反復ループを使用することで解決できます。

(defn has-all-divisors [^long num]
  (loop [d (long 2)]
    (if (zero? (mod num d))
      (if (>= d 20) true (recur (inc d)))
      false)))

 (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))
 => "Elapsed time: 13369.525651 msecs"

あなたはを使用して最終的な問題を解決することができますrem

(defn has-all-divisors [^long num]
  (loop [d (long 2)]
    (if (== 0 (rem num d))
      (if (>= d 20) true (recur (inc d)))
      false)))

 (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))
=> "Elapsed time: 2423.195407 msecs"

ご覧のとおり、Javaバージョンと競合しています。

一般に、少しの努力で、通常、ClojureをJavaとほぼ同じ速度で作成できます。主なトリックは通常次のとおりです。

  • 怠惰な機能機能は避けてください。それらは素晴らしいですが、低レベルの計算集約型コードでは問題になる可能性のあるオーバーヘッドが追加されます。
  • プリミティブ/チェックされていない数学を使用する
  • シーケンスではなくループ/繰り返しを使用する
  • Javaオブジェクトを反映していないことを確認します（つまり(set! *warn-on-reflection* true)、見つかったすべての警告を排除します）
于 2013-01-02T02:23:51.580 に答える
1

1500ミリ秒のパフォーマンスを再現できませんでした。Clojureコードは、uberjarにコンパイルした後、実際にはJavaバージョンの2倍の速度であるように見えます。

Now timing Java version
    232792560
"Elapsed time: 4385.205 msecs"

Now timing Clojure version
    232792560
"Elapsed time: 2511.916 msecs"

javaクラスをresources/HasAllDivisors.javaに配置しました

public class HasAllDivisors {

    public static long findMinimumWithAllDivisors() {
        long i = 1;
        while(!hasAllDivisors(i,2,20)) i++;
        return i;
    }

    public static boolean hasAllDivisors(long num, int startDivisor, int stopDivisor) {
        for(int divisor = startDivisor; divisor <= stopDivisor; divisor++) {
            if(num % divisor > 0) return false;
        }
        return true;
    }

    public static void main(String[] args){
        long start = System.currentTimeMillis();
        long i = findMinimumWithAllDivisors();
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println("Elapsed time " + (end - start));
    }

}

そしてClojureで

(time (prn (HasAllDivisors/findMinimumWithAllDivisors)))

(println "Now timing Clojure version")
(time
    (prn
        (loop [i (long 1)]
            (if (has-all-divisors i)
                i
                (recur (inc i))))))

コマンドラインでも、Javaクラスは高速を再現していません。

$ time java HasAllDivisors
  232792560
Elapsed time 4398

real   0m4.563s
user   0m4.597s
sys    0m0.029s
于 2013-04-12T20:36:29.713 に答える
0

これは古い質問ですが、私は同じようなことに遭遇しています。Clojureは単純なループではJavaよりもはるかに悪いというOPの声明は真実のようです。このスレッドでは、OPのコードから始めて、パフォーマンスの向上を追加するプロセスを実行しました。最後に、Javaコードは約300ミリ秒で実行され、最適化されたClojureコードは3000ミリ秒で実行されます。leinを使用してuberjarを作成すると、Clojureコードが2500ミリ秒になります。

与えられたコードが吐き出す答えを知っているので、私はそれを使用して、Clojureコードがmod/rem計算を行わずに単に回数ループするようにしました。それは単にループを通過します。

(def target 232792560)

(defn has-all-divisors [divisors ^long num]
    (loop [d (long 2)]
        (if (< d 20) (recur (inc d)))))

(time (let [rng (range 2 20)
            f (fn [^long i] (has-all-divisors (range 2 20) i)) ]
    (prn (loop [i 1] 
            (if (< i target)
                (do (f i) (recur (inc i))))))))

結果として得られる時間は、計算を行うのとほぼ同じ、つまり3000ミリ秒です。そのため、Clojureがその多くのループを単純にウォークスルーするのに、これほど長い時間がかかります。

于 2018-09-05T01:25:22.420 に答える