以下 Clojure 程序有什么问题？斐波那契的记忆版本

Question

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

3 被评估了两次，而在记忆版本中，它应该只被评估一次。

Answer 1

在顶级表单之外的任何地方使用 def 都不是线程安全的，并且不能保证在您使用它时正常工作。为了存储这样变化的状态，您很可能希望使用可变状态选项之一，例如 atoms、refs 或 agents。

在这种情况下，原子将是一个不错的选择。

Answer 2

您的程序的问题是以下形式：

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

您在第一行中使用的 fibVal 在递归调用写入它的新版本之前被计算为其当前值。当这个 def 表达式最终求值时，无论他们对 fibVal var 做了什么，都会被遗忘，因为在用 return 的总和调用它们之前，它就变成了 fibVal关联到 x 的值。

def 用于顶级声明，而不是用于在递归过程中改变全局变量。

此外，您的递归实现不是迭代的，因此它会在足够高的 n 时炸毁堆栈。

这里是一个带记忆的有状态迭代实现的例子：

(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 个 Fibonacci 的惯用方法，因为这需要在设计惰性序列的单个线程上生成直到第 n 个数字的整个序列。它们隐式提供缓存并针对所需用例进行了优化。

对于惯用的斐波那契实现，请参考众多 lazy Fibonacci implementations and if necessary learn about lazy sequences.

之一

以下 Clojure 程序有什么问题？斐波那契的记忆版本

What is wrong with the following Clojure program ? Memoized version of Fibonacci

clojure