项目欧拉＃14和在Clojure memoization

作为新手clojurian，它是recommended to me，我通过Project Euler问题作为学习语言的一种方式。它绝对是一种提高技能和获得信心的好方法。我刚刚完成了我对problem #14的回答。它工作正常，但为了让它高效运行，我不得不实施一些记忆。我无法使用预先包装好的memoize函数，因为我的代码的结构是这样的，我认为这是一个很好的体验，可以推出自己的代码。我的问题是，如果有一种很好的方法来将我的缓存封装在函数本身中，或者我必须像我这样定义一个外部缓存。此外，任何提示，使我的代码更习惯性将不胜感激。项目欧拉＃14和在Clojure memoization

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

来源

2010-06-01 dbyrne

只是想感谢你让我看到项目欧拉。我也在努力学习clojure。 – 2011-03-07 21:23:31

非常小的一点，但（inc c）可能比（+ 1 c）更具惯用性。 – 2011-07-20 17:43:54

既然你想成为的chain-length所有的调用共享缓存，你会写chain-length作为(let [mem (atom {})] (defn chain-length ...))这样它只会是可见的chain-length。

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

来源

2010-06-01 18:23:29 Brian

谢谢！现在你已经解释了它，这似乎很明显。使用幼稚递归和记忆的想法让我想起了这个想法，但我认为这将是一个更好的学习体验，并且更具“可扩展性”来启动。 – dbyrne 2010-06-01 18:29:48

您可以在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捕获，可以用来存储值。

来源

2010-06-01 18:51:17

这实质上是内置memoize函数工作正确的方式吗？我不认为这会适用于我现在编写我的函数的方式，因为递归调用将始终具有不同的参数，并且永远不会返回缓存的值。 – dbyrne 2010-06-01 19:05:45

这不是一个真正的问题，因为只有一个参数需要使用。如果x已知，则可以将缓存计数添加到状态参数中。 – 2010-06-01 21:29:51

这是一个使用普通老式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约快两倍。

来源

2010-06-01 19:32:59

我试过你的版本，但（最长链2 1000000）导致StackOverflowError。 100万来自欧拉工程＃14。 – 2010-06-01 19:51:18

尝试'（最长链1 1000000）'，它应该工作。它必须首先缓存1的值。 – 2010-06-01 20:09:27

同样的错误。如果解决这个问题，我会感到惊讶，因为在（连锁长度为2）的情况下，它在cond中调用（连锁长度为1），并且这个缓存也会被缓存。它在你的机器上工作，我认为？我尝试了两种Clojure版本1.1和1.2。 – 2010-06-01 20:32:48

项目欧拉＃14和在Clojure memoization

回答

相关问题