java - 是什么让这个 Clojure 函数变慢了？

Question

我正在研究 Project Euler problem 14在 Clojure 中。我觉得这是一个很好的通用算法，我得到了正确的结果，但我很难理解为什么我的函数与(我认为是)Java 中的等效函数相比如此慢。这是我的 Clojure 函数，用于从给定的起始数字获取 Collat​​z 链的长度:

(defn collatz-length
  [n]
  (loop [x n acc 1]
    (if (= 1 x)
      acc
      (recur (if (even? x)
               (/ x 2)
               (inc (* 3 x)))
             (inc acc)))))

这是我的 Java 函数来做同样的事情:

public static int collatzLength(long x) {
    int count = 0;
    while (x > 1) {
        if ((x % 2) == 0) {
            x = x / 2;
        } else {
            x = (x * 3) + 1;
        }
        count++;
    }
    return count;
}

为了计算这些函数的性能，我使用了以下 Clojure 代码:

(time (dorun (map collatz-length (range 1 1000000))))

以及以下 Java 代码:

long starttime = System.currentTimeMillis();

int[] nums = new int[1000000];
for (int i = 0; i < 1000000; i++) {
    nums[i] = collatzLength(i+1);
}

System.out.println("Total time (ms) : " + (System.currentTimeMillis() - starttime));

Java 代码在我的机器上运行 304 毫秒，但 Clojure 代码需要 4220 毫秒。是什么导致了这个瓶颈？我该如何提高我的 Clojure 代码的性能？

Answer 1

您使用的是盒装数学，因此数字不断地被装箱和拆箱。尝试类似的东西:

(set! *unchecked-math* true)
(defn collatz-length
  ^long [^long n]
  (loop [x n acc 1]
    (if (= 1 x)
      acc
      (recur (if (zero? (rem x 2))
               (quot x 2)
               (inc (* 3 x)))
             (inc acc)))))
 (time (dorun (loop [i 1] (when (< i 1000000) (collatz-length i) (recur (inc i))))))