欧拉项目 #14 和 Clojure 中的记忆化

Question

作为一名 clojurian 新手，建议我浏览Project Euler 问题作为学习语言的一种方式。这绝对是提高技能和获得信心的好方法。我刚刚完成了对问题#14的回答。它工作得很好，但为了让它有效地运行，我必须实现一些记忆。由于我的代码结构方式，我无法使用预先打包的 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

这是使用普通旧 memoize 的惯用（？）版本。

(def chain-length
     (memoize
      (fn [n]
        (cond
         (== n 1)  1
         (even? n) (inc (chain-length (/ n 2)))
         :else     (inc (chain-length (inc (* 3 n))))))))

(defn longest-chain [start end]
  (reduce (fn [x y]
            (if (> (second x) (second y)) x y))
          (for [n (range start (inc end))]
            [n (chain-length n)])))

如果您急于使用recur，请首先考虑map或reduce。他们经常做你想做的事，有时做得更好/更快，因为他们利用了分块的 seqs。

(inc x) 类似于 (+ 1 x)，但 inc 的速度大约是 (+ 1 x) 的两倍。

Answer 2

您可以在 clojure 中捕获周围环境：

(defn my-memoize [f] 
  (let [cache (atom {})] 
    (fn [x] 
      (let [cy (get @cache x)] 
        (if (nil? cy) 
          (let [fx (f x)] 
          (reset! cache (assoc @cache x fx)) fx) cy)))))


(defn mul2 [x] (do (print "Hello") (* 2 x)))
(def mmul2 (my-memoize mul2))  
user=> (mmul2 2)
Hello4
user=>  (mmul2 2) 
4

您会看到 mul2 函数仅被调用一次。

因此“缓存”被 clojure 捕获并可用于存储值。

Answer 3

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

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