对于简单的循环而言,Clojure的性能与Java相比非常糟糕

Question

Spoiler警报,这是Project Euler的第5个问题.

我正在尝试学习Clojure并解决了问题5,但它慢了几个数量级(Java中为1515 ms,而Clojure中为169932 ms).我甚至尝试使用类型提示,未经检查的数学运算和内联函数都是徒劳的.

为什么我的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"

你可以用loop/recur解决第二个问题:

(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)消除您发现的所有警告)