Clojure中的竹内数字(表演)

Question

在计算竹内数时，我们需要计算出函数调用自身的次数。我很快想出了：

(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"

但表现真的很差。如何在克洛朱尔中让它变得极快？

Answer 1

正如有人所说，删除 dosync 似乎可以将事情改善 10 倍，但这并不是故事的全部。一旦 JVM 发现了你的代码，它就会再快 10 倍。这就是为什么你应该使用标准或类似的东西来测试现实世界的速度......

(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 倍左右。为我工作。

Answer 2

实现

这一点的一种纯函数方式是让tak函数返回一对[result count]，其中result是tak计算的实际结果，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)))

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