Progetto Eulero # 14 e memoizzazione in Clojure

Question

Come clojuriano neofita, è stato recommended to me che ho passato i problemi Project Euler come un modo per imparare la lingua. È sicuramente un ottimo modo per migliorare le tue abilità e acquisire sicurezza. Ho appena finito la mia risposta allo problem #14. Funziona bene, ma per farlo funzionare in modo efficiente ho dovuto implementare alcune memoization. Non ho potuto utilizzare la funzione memoize preconfezionata a causa del modo in cui il mio codice era strutturato, e penso che sia stata una buona esperienza girare il mio comunque. La mia domanda è se c'è un buon modo per incapsulare la mia cache all'interno della funzione stessa, o se devo definire una cache esterna come ho fatto io. Inoltre, qualsiasi suggerimento per rendere il mio codice più idiomatico sarebbe apprezzato.

(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

Dal momento che si desidera la cache per essere condiviso tra tutte le chiamate di chain-length, si dovrebbe scrivere chain-length come (let [mem (atom {})] (defn chain-length ...)) modo che sarebbe solo essere visibile a chain-length.

In questo caso, poiché la catena lunga è sufficientemente piccolo, si potrebbe definire chain-length utilizzando il metodo ricorsivo naif e utilizzando funzione built memoize di Clojure su questo.

Answer 2

È possibile catturare l'ambiente circostante in 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 

si vede il funciton mul2 viene chiamato una sola volta.

Quindi la "cache" viene catturata dal clojure e può essere utilizzata per memorizzare i valori.

Answer 3

Ecco una versione idiomatica (?) Che utilizza semplicemente il vecchio 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)]))) 

Se avete il bisogno di usare recur, considerare map o reduce prima. Spesso fanno ciò che vuoi, e talvolta lo fanno meglio/più velocemente, dal momento che approfittano dei seq chunked.

(inc x) è come (+ 1 x), ma inc è circa il doppio più veloce.