Clojure 中的 Takeuchi 数字（性能）

Question

在计算Takeuchi numbers时，我们需要算出函数调用自身的次数。我很快想到：

(def number (atom 0))

(defn tak [x y z]
  (if (<= x y)
    y
    (do 
      (dosync (swap! number inc))
      (tak (tak (dec x) y z)
           (tak (dec y) z x)
           (tak (dec z) x y)))))

(defn takeuchi_number [n]
  (dosync (reset! number 0))
  (tak n 0 (inc n))
  @number)

(time (takeuchi_number 10))
; 1029803
; "Elapsed time: 11155.012266 msecs"

但是性能真的很差。如何在 Clojure 中让它变得非常快？

Answer 1

一个纯函数式的实现方法是让你的 tak 函数到 return 一对 [result count]，其中 result 是 [= 的实际结果11=] 计算和 count 是函数递归调用自身的次数。但在这种情况下，我认为这会导致函数主体出现各种痛苦的扭曲，不值得这样做。

此处 atom 的用法虽然是 Clojure 惯用的，但会带来不必要的开销；它的真正目标是将独立更新同步到线程之间的共享状态。基本上，您想要的是一个可变对象，您可以将其传递给同一线程中的递归函数调用，而无需同步。数组应该足以满足该目的：

(defn tak [x y z ^longs counter]
  (if (<= x y)
    y
    (do 
      (aset counter 0 (inc (aget counter 0)))
      (tak (tak (dec x) y z counter)
           (tak (dec y) z x counter)
           (tak (dec z) x y counter)
           counter))))

(defn takeuchi_number [n]
  (let [counter (long-array [0])]
    (tak n 0 (inc n) counter)
    (aget counter 0)))

请注意，我已将计数器定义从全局常量移至辅助函数的参数，以确保可变状态仅在该函数中局部使用。

Answer 2

正如有人所说，删除 dosync 似乎可以将事情改善 10 倍，但这并不是全部。一旦 JVM 对您的代码进行了热点处理，它的速度就会进一步提高 10 倍。这就是为什么您应该使用 criterium 或类似工具来测试真实世界的速度...

(def number (atom 0))

(defn tak [x y z]
  (if (<= x y)
    y
    (do 
      (swap! number inc)
      (tak (tak (dec x) y z)
           (tak (dec y) z x)
           (tak (dec z) x y)))))

(defn takeuchi_number [n]
  (reset! number 0)
  (tak n 0 (inc n))
  @number)

;=> (time (takeuchi_number 10))
; "Elapsed time: 450.028 msecs"
; 1029803
;=> (time (takeuchi_number 10))
; "Elapsed time: 42.008 msecs"
; 1029803

原始的 dosync 在我的机器上大约是 5 秒，所以我们已经以 10 为基数提高了两个数量级！这是我们能做的最好的吗？让我们重构为纯函数并远离计数器。

(defn tak [c x y z]
  (if (<= x y)
    [c y]
    (let [[a- x-] (tak 0 (dec x) y z)
          [b- y-] (tak 0 (dec y) z x)
          [c- z-] (tak 0 (dec z) x y)]
      (recur (+' 1 a- b- c- c) x- y- z-))))

(defn takeuchi_number [n]
   (tak 0 n 0 (inc n)))

;=> (time (takeuchi_number 10))
; "Elapsed time: 330.741 msecs"
; [1029803 11]
;=> (time (takeuchi_number 10))
; "Elapsed time: 137.829 msecs"
; [1029803 11]
;=> (time (takeuchi_number 10))
; "Elapsed time: 136.866 msecs"
; [1029803 11]

不太好。将状态保存在向量中并四处传递的成本可能是一种开销。然而，现在我们已经重构到纯净，让我们利用我们的良好行为！

=> (def tak (memoize tak))
#'euler.tak/tak
=> (time (takeuchi_number 10))
"Elapsed time: 1.401 msecs"
[1029803 11]

一个健康的快3000倍左右。适合我。

Clojure 中的 Takeuchi 数字（性能）

Takeuchi numbers in Clojure (performance)

algorithm

performance

clojure