项目Euler#14和Clojure中的memoization

Question

作为一个新手clojurian,我建议我将项目Euler问题作为学习语言的一种方式.它绝对是提高技能和获得信心的好方法.我刚刚完成了问题#14的答案.它工作正常,但为了让它有效运行,我必须实现一些memoization.memoize由于我的代码的结构方式,我无法使用预先打包的功能,而且我认为无论如何都是一个很好的经验.我的问题是,是否有一种很好的方法将我的缓存封装在函数本身中,或者如果我必须像我所做的那样定义一个外部缓存.此外,任何使我的代码更惯用的提示将不胜感激.

(use 'clojure.test)

(def mem (atom {}))

(with-test
  (defn chain-length      
    ([x] (chain-length x x 0))     
    ([start-val x c]
      (if-let [e (last(find @mem x))]
        (let [ret (+ c e)]
          (swap! mem assoc start-val ret)
          ret)   
        (if (<= x 1)               
          (let [ret (+ c 1)]
            (swap! mem assoc start-val ret)
            ret)                  
          (if (even? x)            
            (recur start-val (/ x 2) (+ c 1))
            (recur start-val (+ 1 (* x 3)) (+ c 1)))))))
  (is (= 10 (chain-length 13))))

(with-test
  (defn longest-chain
    ([] (longest-chain 2 0 0))
    ([c max start-num]
      (if (>= c 1000000)
        start-num
        (let [l (chain-length c)]
          (if (> l max)
            (recur (+ 1 c) l c)
            (recur (+ 1 c) max start-num))))))
  (is (= 837799 (longest-chain))))

Answer 1

由于您希望缓存在 的所有调用之间共享chain-length，因此您可以chain-length这样编写(let [mem (atom {})] (defn chain-length ...))，以便它仅对 可见chain-length。

在这种情况下，由于最长的链足够小，您可以chain-length使用简单的递归方法进行定义，并使用 Clojure 的内置memoize函数。