簡單循環與Java的Clojure性能真的很差

Question

擾流警報，這是Project Euler的問題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; 
    } 
} 

Answer 1

一些性能問題：

• 的(range 2 20)呼叫爲i每個增量創造數的新懶列表。這很昂貴，並導致大量不必要的GC。
• 你正在通過函數調用進行大量的裝箱。即使是(iterate inc 1)正在做每一個增量的拳擊/拆箱。
• 您正在遍歷一系列除數。這比直接迭代循環更慢
• mod目前在Clojure中實際上並不是一個非常優化的函數。您是多使用rem

更好您可以通過使用let語句來定義的範圍內只有一次解決了第一個問題：

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

可以解決循環/易復發的第二個問題：

(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" 

您可以通過使用迭代循環在可能的除數解決第三個問題：

(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)和消除你會發現所有的警告）

Answer 2

我沒有能夠重現1500毫秒的性能。在編譯成uberjar之後，Clojure代碼看起來實際上是Java版本的兩倍。

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

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

我把java類資源/ 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