Dự án Euler # 14 và ghi nhớ trong Clojure

Question

Là một thuật ngữ tân tiến, đó là recommended to me mà tôi xem xét các vấn đề về Project Euler như một cách để học ngôn ngữ. Nó chắc chắn là một cách tuyệt vời để cải thiện kỹ năng của bạn và đạt được sự tự tin. Tôi vừa hoàn thành câu trả lời của mình cho problem #14. Nó hoạt động tốt, nhưng để có được nó chạy hiệu quả tôi đã phải thực hiện một số memoization. Tôi không thể sử dụng chức năng được đóng gói sẵn memoize vì cách mã của tôi được cấu trúc và tôi nghĩ đó là một trải nghiệm tốt để cuộn theo cách của riêng tôi. Câu hỏi của tôi là nếu có một cách tốt để đóng gói bộ nhớ cache của tôi trong chính hàm đó, hoặc nếu tôi phải định nghĩa một bộ đệm ẩn bên ngoài như tôi đã làm. Ngoài ra, bất kỳ lời khuyên nào để làm cho mã của tôi thành ngữ hơn sẽ được đánh giá cao.

(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

Vì bạn muốn bộ nhớ cache được chia sẻ giữa tất cả các lời gọi của chain-length, bạn sẽ viết chain-length như (let [mem (atom {})] (defn chain-length ...)) để nó sẽ chỉ được hiển thị cho chain-length.

Trong trường hợp này, vì chuỗi dài nhất đủ nhỏ, bạn có thể xác định chain-length sử dụng phương pháp đệ quy ngây thơ và sử dụng hàm dựng sẵn của Clojure memoize trên đó.

Answer 2

Bạn có thể nắm bắt được môi trường xung quanh trong một 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 

Bạn thấy funciton mul2 chỉ được gọi một lần.

Vì vậy, 'bộ nhớ cache' được chụp bởi clojure và có thể được sử dụng để lưu trữ các giá trị.

Answer 3

Đây là phiên bản thành ngữ (?) Sử dụng đồng bằng cũ 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)]))) 

Nếu bạn có một sự thôi thúc để sử dụng recur, hãy xem xét map hoặc reduce đầu tiên. Họ thường làm những gì bạn muốn, và đôi khi làm nó tốt hơn/nhanh hơn, vì họ tận dụng lợi thế của seqs chunked.

(inc x) giống như (+ 1 x), nhưng inc nhanh gấp hai lần.