38

メモ化された再帰関数をClojureで返す関数を作成しようとしていますが、再帰関数に独自のメモ化されたバインディングを表示させるのに問題があります。これは、varが作成されていないためですか？また、letで作成したローカルバインディングでメモ化を使用できないのはなぜですか？

特定の番号で始まるこの少し珍しいフィボナッチ数列メーカーは、私がしたいことの例です。

(defn make-fibo [y]
  (memoize (fn fib [x] (if (< x 2)
             y
             (+ (fib (- x 1))
                (fib (- x 2)))))))

(let [f (make-fibo 1)]
  (f 35)) ;; SLOW, not actually memoized

使用with-local-varsすることは正しいアプローチのように思えますが、それは私にとってもうまくいきません。私は変数を閉じることができないと思いますか？

(defn make-fibo [y]
  (with-local-vars [fib (fn [x] (if (< x 2)
                                  y
                                  (+ (@fib (- x 1))
                                     (@fib (- x 2)))))]
    (memoize fib)))

(let [f (make-fibo 1)]
  (f 35)) ;; Var null/null is unbound!?!

もちろん、閉じたアトムを作成してメモ化を自分で管理するマクロを手動で作成することもできますが、そのようなハッカーなしでこれを実行したいと考えていました。

4

8 に答える 8

21

再バインドにも。の動作にも依存しない、興味深い方法がありdefます。主なトリックは、関数を引数としてそれ自体に渡すことにより、再帰の制限を回避することです。

(defn make-fibo [y]
  (let
    [fib
      (fn [mem-fib x]
         (let [fib (fn [a] (mem-fib mem-fib a))]
           (if (<= x 2)
             y
             (+ (fib (- x 1)) (fib (- x 2))))))
     mem-fib (memoize fib)]

     (partial mem-fib mem-fib)))

それで：

> ((make-fibo 1) 50)
12586269025

ここでは何が起きるのですか：

  • fib再帰関数は新しい引数を取得しましたmem-fib。fib定義されると、これはそれ自体のメモ化されたバージョンになります。
  • fib本体は、呼び出しを再定義する形式でラップされているためlet、呼び出しは次のレベルの再帰fibに渡されます。mem-fib
  • mem-fibメモ化されたものとして定義されますfib
  • ...そしてpartial、上記のメカニズムを開始するための最初の引数として渡されます。

このトリックは、組み込みの再帰メカニズムがない場合に関数の固定小数点を計算するためにYコンビネータが使用するトリックに似ています。

定義されているシンボルを「見る」ことを考えると、def匿名のインプレース再帰メモ化関数を作成する場合を除いて、この方法を採用する実際的な理由はほとんどありません。

于 2012-10-29T14:27:40.893 に答える
19

これはうまくいくようです：

(defn make-fibo [y]
  (with-local-vars
      [fib (memoize
            (fn [x]
              (if (< x 2)
                y
                (+ (fib (- x 2)) (fib (dec x))))))]
    (.bindRoot fib @fib)
    @fib))

with-local-varswith-local-vars新しく作成されたVarのスレッドローカルバインディングのみを提供します。これは、実行がフォームを離れるとポップされます。したがって、の必要性.bindRoot。

于 2010-10-11T16:18:05.920 に答える
18 
(def fib (memoize (fn [x] (if (< x 2)
                              x
                              (+ (fib (- x 1))
                                 (fib (- x 2)))))))
(time (fib 35))
于 2010-10-11T15:54:49.520 に答える
3

最も簡単な解決策は次のとおりです。

(def fibo
  (memoize (fn [n]
             (if (< n 2)
               n
               (+ (fibo (dec n))
                  (fibo (dec (dec n))))))))
于 2014-02-21T18:34:08.297 に答える
2

再帰的にメモ化された関数パターンを複数回使用する場合は、マクロにカプセル化できます。

(defmacro defmemo
  [name & fdecl]
  `(def ~name
     (memoize (fn ~fdecl))))
于 2012-01-13T19:26:41.950 に答える
1

Y-combinatorとClojureのクロスは次のmemoizeとおりです。

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

あなたはこれをマクロシュガーすることができます：

(defmacro defrecfn [name args & body]
  `(def ~name
       (Y-mem (fn [foo#]
                 (fn ~args (let [~name foo#] ~@body))))))

今それを使用するために：

(defrecfn fib [n]
  (if (<= n 1)
      n
      (+' (fib (- n 1))
          (fib (- n 2)))))

user=> (time (fib 200))
"Elapsed time: 0.839868 msecs"
280571172992510140037611932413038677189525N

またはレーベンシュタイン距離：

(defrecfn edit-dist [s1 s2]
  (cond (empty? s1) (count s2)
        (empty? s2) (count s1)
        :else (min (inc (edit-dist s1 (butlast s2)))
                   (inc (edit-dist (butlast s1) s2))
                   ((if (= (last s1) (last s2)) identity inc)
                      (edit-dist (butlast s1) (butlast s2))))))
于 2014-10-20T23:59:38.837 に答える
0

最初のバージョンは実際に機能しますが、アルゴリズムを1回しか実行していないため、メモ化のすべての利点を享受しているわけではありません。

これを試して：

user>  (time (let [f (make-fibo 1)]
          (f 35)))
"Elapsed time: 1317.64842 msecs"
14930352

user>  (time (let [f (make-fibo 1)]
          [(f 35) (f 35)]))
"Elapsed time: 1345.585041 msecs"
[14930352 14930352]
于 2010-10-11T14:15:21.180 に答える
0

Yコンビネータのバリアントを使用して、Clojureでメモ化された再帰関数を生成できます。たとえば、のコードは次のfactorialようになります。

(def Ywrap
  (fn [wrapper-func f]
    ((fn [x]
       (x x))
     (fn [x]
       (f (wrapper-func (fn [y]
                      ((x x) y))))))))

 (defn memo-wrapper-generator [] 
   (let [hist (atom {})]
    (fn [f]
      (fn [y]
        (if (find @hist y)
          (@hist y)
         (let [res (f y)]
           (swap! hist assoc y res)
        res))))))

(def Ymemo 
  (fn [f]
   (Ywrap (memo-wrapper-generator) f)))

(def factorial-gen
  (fn [func]
    (fn [n]
      (println n)
     (if (zero? n)
      1
      (* n (func (dec n)))))))

(def factorial-memo (Ymemo factorial-gen))

これは、 Yコンビネータの実際のアプリケーションに関するこの記事で詳細に説明されています：clojureでの再帰的なメモ化。

于 2016-08-14T19:57:15.947 に答える