Clojure China

记忆化搜索-关于memoize结合递归

memoize
share
#1

之前做了一个关于动态规划的题目，因为以前都是用C++写代码，所以很自然的用map reduce 模仿for循环的方式来处理，导致非常的繁琐。
昨天突然想到，用记忆化搜索的方式使用递归也可以。
比如 Fibonacci 数列，直接用递归可以这么写：

(defn fib [n]
  (condp = n
    0 1
    1 1
    (+ (fib (dec n)) (fib (- n 2)))))

可是，因为在递归过程中，每次计算fib(n)都会按照递归树执行到底，导致非常慢。
执行时间为：

(time (fib 30))   => "Elapsed time: 8179.04028 msecs"

如果改成记忆化搜索的形式：

(def m-fib
  (memoize (fn [n]
        (condp = n
          0 1
          1 1
          (+ (m-fib (dec n)) (m-fib (- n 2)))))))

​
执行时间为：

(time (m-fib 30)) => "Elapsed time: 1.282557 msecs"

我觉得这个方式不错，类似的递归问题都可以这么写。

#2

不错，就是把每一步的计算结果保存下来以便复用吧？

不过不知道这样使用 memoize 合不合理，比如保存的中间结果很多的话会不会一直占用内存？

#3

memoize是常见的方式，像SML这些函数式语言都有这个函数。
我觉得，如果达到了占用很多内存的程度，那递归树肯定也是非常大，
已经达到了性能瓶颈，需要改算法了。

#4

看了下 memoize 的实现：

(defn memoize
  [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem args)]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc args ret)
          ret)))))

有点像 decorator 模式，返回一个带“记忆”功能的函数 wrap 了一下原函数，args 作为 key 在 (atom {}) 中缓存函数求值结果 ret。如果返回的函数不被回收掉，那么 mem 这个 atom 会一直占用内存的，搞不好 OutOfMemoryError。

yy下可以自己 hack 一个集成 Google Guava 的 Cache，可以指定缓存条目上限以及 LRU 淘汰时间：

(ns playground.core
  (:import [com.google.common.cache CacheBuilder Cache]
           [java.util.concurrent TimeUnit]))

(def  mem (-> (CacheBuilder/newBuilder) 
          (.maximumSize 1000)
          (.expireAfterAccess 60 TimeUnit/SECONDS)
          .build))

(defn m-memoize [f]
  (fn [& args]
    (if-let [e (.getIfPresent mem args)]
      e
      (let [ret (apply f args)]
        (.get mem args (fn [] ret))))))
#5

这个可能是你想要的：core.memoize

#6

memoize 是会一直占用内存的。