懶惰序列或重複數學功能函數？

Question

作爲練習，我實現了數學冪函數。一旦使用易復發：

(defn power [a n] 
    (let [multiply (fn [x factor i] 
        (if (zero? i) 
        x 
        (recur (* x factor) factor (dec i))))] 
    (multiply a a (dec n)))) 

user=> (time (dotimes [_ 10000] (power 2 512))) 
"Elapsed time: 1839.406746 msecs" 

一旦懶-SEQ：

(defn power [a n] 
    (letfn [(multiply [a factor] 
      (lazy-seq 
       (cons a (multiply (* a factor) factor))))] 
    (nth (multiply a a) (dec n)))) 

user=> (time (dotimes [_ 10000] (power 2 512))) 
"Elapsed time: 2162.297827 msecs" 

你認爲哪實現更勝一籌？我真的不知道..（我會用復發，因爲它更容易理解。）

我讀lazy-seq是快速的，因爲它使用內部緩存。但是我沒有看到我的示例有任何緩存機會。我可以忽略一些東西嗎

更新
我發佈了樣品的時間。似乎這裏的復發稍快。

定期遞歸不做也不錯：

(defn power [a n] 
    (if (== n 1) 
     a 
     (* a (power a (dec n))))) 

user=> (time (dotimes [_ 10000] (power 2 512))) 
"Elapsed time: 1877.34521 msecs" 

Answer 1

首先，通常的建議是首先選擇the correct algorithm，稍後擔心實現細節（如果您的代碼實際上對性能敏感或可能在上下文中使用）。

然後有審美考慮。 recur對我來說似乎更清潔，只是因爲這是解決問題的完美方式。使用序列在他們以某種方式輸入語義圖片時很有意義，否則，使代碼更易於編寫/理解/創建高性能代碼。這裏沒有什麼是這種情況。

最後，我肯定希望recur總體上更快，如果只是因爲它避免了不必要的分配& GC。初始時間支持這一點。確實沒有機會從這裏的任何類型的緩存中受益，因爲每當power被調用時您都會從頭開始生成您的序列，並且在返回後從不保留它。

Answer 2

你應該做的計時測試，同時運行1米倍，看到了倍。通常非遞歸函數速度更快，但在處理函數式語言時，遞歸是首選方式，因爲它們通常使用尾調用。基於Java Clr的Clojure所以我現在不支持尾部調用，但是如果是這樣的話，它應該和非遞歸調用一樣快。

Answer 3

我在這裏提供了一些我自己的懶惰電源功能，以顯示如何從函數中重用lazy-seq。

每次你用兩個數字撥打my-simple-lazy-power時，它會建立一個懶惰的seq，其中包含一定數量x的冪，並返回它的第n個項。使用這個版本非常昂貴，因爲它爲每個函數調用構造了一個lazy-seq。這可能就是爲什麼我的簡單懶惰能力的基準是如此緩慢。由於懶惰seqs緩存他們的結果，你可能想重新使用它們。這就是my-lazy-power所做的：它爲數字x構造一個lazy-seq，並在它周圍包含一個接受n作爲參數的函數。您可以重新使用後一個函數來訪問緩存的結果。 （只要函數存在，該函數就會保持對lazy-seq的引用，因爲它關閉了lazy-seq，這就是爲什麼他們稱之爲閉包的原因。）

另一種常見的緩存一個函數是使用該函數的memoized版本。基本上memoize記住你傳入的參數的結果，所以下一次你傳入完全相同的參數時，它將返回緩存的結果。看下面的例子。爲了比較，我還定時了你的版本和他們的memoized版本。

(defn my-simple-lazy-power [x n] 
    (let [my-lazy-list 
    ((fn my-lazy [y] 
     (lazy-cat [y] (map #(* % x) (my-lazy y)))) x)] 
    (nth my-lazy-list n))) 

(defn my-lazy-power [x] 
    (let [my-lazy-list 
    ((fn my-lazy [y] 
     (lazy-cat [y] (map #(* % x) (my-lazy y)))) x)] 
    (fn [n] 
     (nth my-lazy-list n)))) 

(defn rec-power [a n] 
    (let [multiply (fn [x factor i] 
        (if (zero? i) 
        x 
        (recur (* x factor) factor (dec i))))] 
    (multiply a a (dec n)))) 

(defn lazy-power [a n] 
    (letfn [(multiply [a factor] 
      (lazy-seq 
      (cons a (multiply (* a factor) factor))))] 
    (nth (multiply a a) (dec n)))) 

(def mem-my-simple-power (memoize my-simple-lazy-power)) 
(def mem-my-power (memoize my-lazy-power)) 
(def mem-rec-power (memoize rec-power)) 
(def mem-laz-power (memoize lazy-power)) 

(time (dotimes [_ 50] (my-simple-lazy-power 2 512))) 
"Elapsed time: 7138.346976 msecs" 
nil 

(time (let [my-pow-2 (my-lazy-power 2)] 
    (dotimes [_ 10000] (my-pow-2 512)))) 
"Elapsed time: 854.717301 msecs" 
nil 

(time (dotimes [_ 10000] (rec-power 2 512))) 
"Elapsed time: 2726.559879 msecs" 
nil 

(time (dotimes [_ 10000] (mem-rec-power 2 512))) 
"Elapsed time: 4.775677 msecs" 
nil 

(time (dotimes [_ 10000] (lazy-power 2 512))) 
"Elapsed time: 3617.100209 msecs" 
nil 

(time (dotimes [_ 10000] (mem-laz-power 2 512))) 
"Elapsed time: 4.95887 msecs" 
nil 

PS：我不得不寫在左右我的版本的懶-seq的定義fn，因爲我們必須不支持遞歸定義，但fn一樣。

PS2：對不起，壓痕，從複製粘貼的Emacs似乎不保護它......

Answer 4

添加到邁克爾Marczyck的答案...

可以摺疊的定義和呼叫multiply功能爲loop：

(defn power [a n] 
    (loop [x a, factor a, i (dec n)] 
    (if (zero? i) 
     x 
     (recur (* x factor) factor (dec i))))) 

...但它不會跑得更快。

由於MM寫道，選擇正確的算法很重要。他提出的一個快速運行約二十倍的例子和你：

(defn power [x n] 
    (loop [acc 1, n n, factor x] 
    (if (zero? n) 
     acc 
     (recur 
     (if (even? n) acc (* acc factor)) 
     (quot n 2) 
     (* factor factor))))) 

你必須提示當前的Clojure使用BigInt，否則你會得到整數溢出：

(time (dotimes [_ 10000] (power 2N 512))) 

您的里程可能變化。