以下Clojure程序有什麼問題？斐波那契

的Memoized版本

(def fibVal {1 1 2 1}) 

(defn fibonacci [x]    
    (if (false? (get fibVal x false)) 
    (do 
     (println (str "Evaluating " x)) 
     (def fibVal (assoc fibVal x (+ (fibonacci(- x 1)) (fibonacci(- x 2))))) 
     (println (str x " Evaluated to " (fibVal x))) 
     (fibVal x)         
    ) 
    (get fibVal x) 
) 
)

輸出爲（斐波納契5）
評價5
評價4
評價3
3評價爲2
4評價爲3
評價3
3評價爲2
5評價爲5

3評價兩次，而在memoiz ed版本，它應該只被評估一次。以下Clojure程序有什麼問題？斐波那契

來源

2015-05-27 Vibhor Kanojia

與你的程序的問題是形式：

(def fibVal (assoc fibVal 
       x (+ (fibonacci (- x 1)) 
        (fibonacci (- x 2)))))

的fibVal您使用在第一線進行評估，以它的當前值的遞歸調用寫它的新版本之前。無論他們對fibVal變量做什麼，在這個def表達式最終計算時都會被遺忘，因爲在調用它們的返回值之和後，它將變爲fibVal，並將它們的返回值的總和寫入x。

def旨在VOR頂級聲明，而不是在遞歸過程中變異的全局變量。另外，你的遞歸實現不是迭代的，所以它會在足夠高的層次上打擊棧。

這裏是一個有狀態的迭代實現與記憶化的例子：

(def fib-cache (atom [0 1])) 

(defn- calc-nth-fib 
    [fibs n] 
    (reduce (fn [fibs n] 
      (assoc fibs n 
        (apply + (take 2 (rseq fibs))))) 
      fibs 
      (range (count fibs) (inc n)))) 

(defn fibonacci [x] 
    (or (get @fib-cache x) 
     (-> fib-cache 
      (swap! calc-nth-fib x) 
      (nth x))))

注意這個例子並不代表發現Clojure中的第n個斐波那契數的慣用方式，需要一個生成整個序列起來到設計了延遲序列的單個線程上的第n個數字。它們隱式提供緩存並針對所需的用例進行了優化。

對於一個地道的斐波那契實現請參考許多lazy Fibonacci implementations之一，並在必要時learn about lazy sequences.

來源

2015-05-27 20:41:30

謝謝:)這是我的第三方案，Clojure的，所以我不知道多少。是否可以通過任何方式在運行時更新_fibVal_？我按順序讀取_do_進程指令，爲什麼它不在這裏發生？我的意思是，即使def不是線程安全的，它也會在返回值之前執行。 –

你是對的。線程安全不在這裏。請注意，'def'是一種特殊的形式，因此它的評估規則和順序是評估者的一個未公開的實現細節，與正常形式不同，所以您不應該依賴它。但是我發現在這種情況下問題確實存在，並且已經相應地更新了答案。 –

使用def除了最高級別表單之外的任何內容都不是線程安全的，並且不能保證您正在使用它。爲了存儲像這樣變化的狀態，你很可能想使用其中一個可變狀態選項，如原子，參考或代理。

在這種情況下，原子將是一個不錯的選擇。

來源

2015-05-27 20:34:11

以下Clojure程序有什麼問題？斐波那契

回答

相關問題