Projekt Euler # 14 und Memoisierung in Clojure

Question

Als Neophyt Clojurian, war es recommended to me, dass ich durch die Project Euler Probleme als eine Möglichkeit, die Sprache zu lernen gehen. Es ist definitiv ein guter Weg, um Ihre Fähigkeiten zu verbessern und Selbstvertrauen zu gewinnen. Ich habe gerade meine Antwort auf problem #14 beendet. Es funktioniert gut, aber um es effizient laufen zu lassen, musste ich einige Memoization implementieren. Ich konnte die vordefinierte memoize Funktion nicht verwenden, weil mein Code strukturiert war, und ich denke, es war eine gute Erfahrung, meine eigenen sowieso zu rollen. Meine Frage ist, ob es eine gute Möglichkeit gibt, meinen Cache innerhalb der Funktion selbst einzukapseln, oder ob ich einen externen Cache definieren muss, wie ich es getan habe. Außerdem würden alle Tipps, die meinen Code idiomatischer machen, geschätzt.

(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

Da Sie die Cache wollen zwischen allen Beschwörungen chain-length geteilt werden, würden Sie chain-length als (let [mem (atom {})] (defn chain-length ...)) so schreiben, dass es nur zu chain-length sichtbar wäre.

In diesem Fall, da die längste Kette ausreichend klein ist, können Sie chain-length mit der naiven rekursiven Methode definieren und Clojures eingebaute memoize Funktion verwenden.

Answer 2

Sie können die Umgebung in einem clojure erfassen:

(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 

Sie sehen die MUL2 funciton nur einmal aufgerufen wird.

Der 'Cache' wird also vom Clojure erfasst und kann zum Speichern der Werte verwendet werden.

Answer 3

Hier ist eine idiomatische (?) Version mit einfachen alten 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)]))) 

Wenn Sie das Bedürfnis haben recur zu verwenden, sollten Sie map oder reduce zuerst. Sie tun oft, was Sie wollen, und manchmal tun sie es besser/schneller, da sie Chunked Seqs nutzen.

(inc x) ist wie (+ 1 x), aber inc ist etwa doppelt so schnell.