下面的Clojure程序有什么问题？Fibonacci记忆版

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)
  )
)

产出(fibonacci 5)

评价5

评价4

评价3

3项评价改为2项

4项评价改为3项

评价3

3项评价改为2项

评价5至5

5

3被评估两次，而在回忆录版本中，应该只评估一次。

Answer 1

您的程序的问题是形式：

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

在第一行中使用的fibVal将在递归调用编写新版本之前计算为其当前值。当这个fibVal表达式最后计算时，不管它们对def变量做了什么，都会被遗忘，因为在调用它们之前，它就变成了fibVal，并将它们的返回值与x相关联。

def是用于vor顶级声明的，而不是用于在递归过程中变异全局vars。

而且，您的递归实现不是迭代的，因此它会在足够高的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中查找nth Fibonacci的惯用方法，因为这需要在设计延迟序列的单个线程上生成整个序列，直到n个数列。它们提供隐式缓存，并针对所需的usecase进行优化。

对于一个惯用的Fibonacci实现，请参考许多懒散斐波纳契实现中的一个，如果有必要，请参考学习懒散序列。

Answer 2

除了顶级表单之外，在任何情况下使用def都不是线程安全的，也不能保证在您使用它的过程中工作。对于存储这样变化的状态，您很可能希望使用一个可变的状态选项，如原子、参考或代理。

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