Проект Euler # 14 и памятка в Clojure - PullRequest
Новая
       12

Проект Euler # 14 и памятка в Clojure

9 голосов
/ 01 июня 2010

Как неофит клоюрийский, рекомендовал мне , чтобы я прошел через Project Euler как способ изучения языка. Это определенно отличный способ улучшить свои навыки и обрести уверенность. Я только что закончил свой ответ на задачу № 14 . Он работает нормально, но для того, чтобы он работал эффективно, мне пришлось реализовать некоторые памятки. Я не мог использовать готовую функцию memoize из-за структуры моего кода, и я думаю, что в любом случае это был хороший опыт, чтобы свернуть свой собственный код. Мой вопрос заключается в том, есть ли хороший способ инкапсулировать мой кэш в самой функции, или мне нужно определить внешний кэш, как я это сделал. Кроме того, любые советы, чтобы сделать мой код более идиоматическим будет приветствоваться. 

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

Ответы [ 3 ]

3 голосов
/ 01 июня 2010

Так как вы хотите, чтобы кеш распределялся между всеми вызовами chain-length, вы должны написать chain-length как (let [mem (atom {})] (defn chain-length ...)), чтобы он был виден только для chain-length.

В этом случае, поскольку самая длинная цепочка достаточно мала, вы можете определить chain-length, используя наивный рекурсивный метод, и использовать для этого встроенную функцию Clojure memoize.

2 голосов
/ 01 июня 2010

Вот идиоматическая (?) Версия с использованием простого старого 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. Они часто делают то, что вы хотите, а иногда делают это лучше / быстрее, так как они используют преимущества последовательностей.

(inc x) похоже на (+ 1 x), но inc примерно в два раза быстрее.

1 голос
/ 01 июня 2010

Вы можете захватить окружающую среду в ближайшем будущем: 

(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 и может использоваться для хранения значений.

...