Euler № 14 проекта и memoization в Clojure
Как новичок clojurian, рекомендовалось мне, чтобы я прошел Euler проблемы Проекта как способ выучить язык. Определенно отличный способ улучшить Ваши навыки и завоевать доверие. Я просто закончил свое решение проблемы № 14. Это хорошо работает, но получить его работающий эффективно я должен был реализовать некоторый memoization. Я не мог использовать предварительно упакованный 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 ответа
Так как вы хотите, чтобы кеш использовался для всех вызовов длина цепочки , вы должны записать длину цепочки как (пусть [mem (atom {}) ] (defn chain-length ...)) , чтобы он был виден только для длины цепи .
В этом случае, поскольку самая длинная цепочка достаточно мала, вы можете определить длину цепи , используя наивный рекурсивный метод, и использовать для этого встроенную функцию Clojure memoize .
Вот идиоматическая (?) Версия с использованием простого старого 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 примерно в два раза быстрее.
Вы можете захватить окружающую среду в 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
Вы видите, что функция mul2 вызывается только один раз.
Таким образом, "кэш" захватывается clojure и может быть использован для хранения значений.