31

剧透警告，这是 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;
  }
}
4

3 回答 3

56

一些性能问题：

  • 该(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)并消除您发现的所有警告）
于 2013-01-02T02:23:51.580 回答
1

我无法重现 1500 毫秒的性能。Clojure 代码在编译为 uberjar 后实际上似乎是 Java 版本的两倍。

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

我知道这是一个老问题，但我一直在遇到类似的事情。看起来，来自 OP 的声明是，Clojure 在简单循环上比 Java 差得多，这是真的。我在这个线程中完成了这个过程，从 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 回答