Proyecto Euler # 14 y memorización en Clojure

Question

Como clojurian neófito, fue recommended to me que pasé por los problemas Project Euler como una forma de aprender el idioma. Definitivamente es una gran manera de mejorar tus habilidades y ganar confianza. Acabo de terminar mi respuesta al problem #14. Funciona bien, pero para que funcione de manera eficiente tuve que implementar algunas memorias. No pude usar la función preempaquetada memoize debido a la forma en que estaba estructurado mi código, y creo que fue una buena experiencia para mí. Mi pregunta es si hay una buena manera de encapsular mi caché dentro de la función en sí, o si tengo que definir un caché externo como lo he hecho. Además, cualquier consejo para hacer que mi código sea más idiomático sería apreciado.

(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

Desde desea que el caché sea compartida entre todas las invocaciones de chain-length, podría escribir chain-length como (let [mem (atom {})] (defn chain-length ...)) de modo que sólo sería visible a chain-length.

En este caso, puesto que la cadena más larga es suficientemente pequeña, se podría definir chain-length utilizando el método recursivo ingenuo y utiliza la función incorporada de Clojure memoize en eso.

Answer 2

Puede capturar el ambiente circundante en un 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 

que vea el Funciton MUL2 sólo se le llama una vez.

Así que la 'caché' es capturada por el clojure y se puede usar para almacenar los valores.

Answer 3

Aquí hay una versión idiomática (?) Que usa el simple antiguo 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)]))) 

Si usted tiene una necesidad de utilizar recur, considere map o reduce primero. A menudo hacen lo que quieren, y algunas veces lo hacen mejor/más rápido, ya que aprovechan los aspectos fragmentados.

(inc x) es como (+ 1 x), pero inc es aproximadamente el doble de rápido.