Clojure中的竹內數（性能）

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

正如有人所說，刪除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是時代的函數遞歸調用本身數量的純功能性的方式。但在這種情況下，我認爲這會導致功能體內各種痛苦的扭曲，並不值得。

這裏使用​​，而慣用的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))) 

請注意，我已經從一個全局變量到正對輔助函數的參數移動櫃檯的定義，以確保可變狀態只能在本地使用該功能。