我在Clojure工作
Project Euler problem 14.我有一个很好的通用算法,我得到了正确的结果,但我很难理解为什么我的函数与Java中的等效函数相比(我相信)是如此之慢.这是我的Clojure函数,用于从给定的起始编号获取Collatz链的长度：
(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;
}
(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代码的性能？
解决方法
您正在使用盒装数学,因此数字会不断被装箱和取消装箱.尝试类似的东西：
(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))))))
