18

私はLisp初心者です。Collat​​z列の項数を計算するための再帰関数をメモしようとしています ( Project Eulerの問題 14 用)。私のコードはまだです：

(defun collatz-steps (n)
  (if (= 1 n) 0
       (if (evenp n) 
           (1+ (collatz-steps (/ n 2)))
           (1+ (collatz-steps (1+ (* 3 n)))))))

(defun p14 ()
  (defvar m-collatz-steps (memoize #'collatz-steps))
  (let 
      ((maxsteps (funcall m-collatz-steps 2))
       (n 2)
       (steps))
    (loop for i from 1 to 1000000
          do 
          (setq steps (funcall m-collatz-steps i))
          (cond 
            ((> steps maxsteps) 
             (setq maxsteps steps)
             (setq n i))
            (t ())))
    n))


(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind 
              (result exists)
            (gethash args cache)
          (if exists
              result
              (setf (gethash args cache)
                    (apply fn args)))))))

memoize 関数は、 On Lispブックで提供されているものと同じです。

このコードは、メモ化されていないバージョンと比較して実際にはスピードアップしません。これは、関数のメモ化されていないバージョンを呼び出す再帰呼び出しが原因であると考えられますが、これは一種の目的を無効にします。その場合、ここでメモ化を行う正しい方法は何ですか? 元の関数へのすべての呼び出しでメモ化されたバージョン自体を呼び出して、特別な m-collat​​z-steps シンボルの必要性をなくす方法はありますか?

編集：コードを修正しました

(defvar m-collatz-steps (memoize #'collatz-steps))

これは私のコードにあったものです。編集の前に、私が誤って入れたもの:

(defvar collatz-steps (memoize #'collatz-steps))

そのエラーを見て別のアイデアが浮かび、この最後の defvar 自体を使用して、再帰呼び出しを次のように変更してみました

       (1+ (funcall collatz-steps (/ n 2)))
       (1+ (funcall collatz-steps (1+ (* 3 n))))

これはメモ化 (約 60 秒から 1.5 秒への高速化) を実行しているように見えますが、元の関数を変更する必要があります。元の機能を変更する必要のない、よりクリーンなソリューションはありますか?

4

8 に答える 8

11

変数名と関数名に別々の名前空間を持つ Common-Lisp を使用していると思います。シンボルによって名前が付けられた関数をメモ化するには、アクセサー `fdefinition' を使用して、その関数バインディングを変更する必要があります。

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

(defun p14 ()
  (let ((mx 0) (my 0))
    (loop for x from 1 to 1000000
          for y = (collatz-steps x)
          when (< my y) do (setf my y mx x))
    mx))
于 2008-11-02T19:11:29.137 に答える
3

以下は、シンボル関数を再バインドする memoize 関数です。

(defun memoize-function (function-name)
  (setf (symbol-function function-name)
    (let ((cache (make-hash-table :test #'equal)))
         #'(lambda (&rest args)
             (multiple-value-bind 
                 (result exists)
                (gethash args cache)
               (if exists
                   result
                   (setf (gethash args cache)
                         (apply fn args)))))))

次に、次のようにします。

(defun collatz-steps (n)
  (if (= 1 n) 0
      (if (evenp n) 
          (1+ (collatz-steps (/ n 2)))
          (1+ (collatz-steps (1+ (* 3 n)))))))

(memoize-function 'collatz-steps)

unmemoize-function の作成はお任せします。

于 2008-11-03T19:46:01.140 に答える
2

このようなもの：

(setf collatz-steps (memoize lambda (n)
  (if (= 1 n) 0
    (if (evenp n) 
        (1+ (collatz-steps (/ n 2)))
        (1+ (collatz-steps (1+ (* 3 n))))))))

IOW: 元の (メモ化されていない) 関数は匿名であり、メモ化した結果に名前を付けるだけです。

于 2008-11-02T05:18:10.627 に答える
2

いくつかのことに注意してください。

(defun foo (bar)
   ... (foo 3) ...)

上記は、それ自体への呼び出しを持つ関数です。

Common Lisp では、ファイル コンパイラは FOO が変更されないと想定できます。後で更新された FOO を呼び出すことはありません。FOO の関数バインディングを変更すると、元の関数の呼び出しは引き続き古い関数になります。

したがって、自己再帰関数のメモ化は、一般的なケースでは機能しません。優れたコンパイラを使用している場合は特にそうではありません。

たとえば、常にシンボルを通過するように回避できます。 (funcall 'foo 3)

(DEFVAR ...) はトップレベルのフォームです。関数内では使用しないでください。変数を宣言した場合は、後で SETQ または SETF で設定します。

あなたの問題については、ハッシュテーブルを使用して中間結果を保存するだけです。

于 2010-03-06T18:36:50.167 に答える
1

あなたが言うように、再帰呼び出しを更新してメモ化されたバージョンを呼び出す方法は他にないため、「元の」関数を変更する必要があります。

幸いなことに、lisp が機能する方法は、呼び出される必要があるたびに名前で関数を見つけることです。これは、関数バインディングを関数のメモ化されたバージョンに置き換えるだけで十分であることを意味します。これにより、再帰呼び出しが自動的に検索され、メモ化によって再入力されます。

huaiyuan のコードは、重要なステップを示しています。

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

このトリックは Perl でも機能します。ただし、C のような言語では、関数のメモ化されたバージョンを個別にコーディングする必要があります。

Lisp の実装の中には、「アドバイス」と呼ばれるシステムを提供するものがあります。これは、関数をそれ自体の拡張バージョンに置き換えるための標準化された構造を提供します。メモ化などの機能のアップグレードに加えて、元のコードを変更せずにデバッグ プリントを挿入する (または完全に停止して継続可能なプロンプトを表示する) ことにより、デバッグに非常に役立ちます。

于 2008-11-21T04:58:06.113 に答える
1

この関数はまさに、Peter Norvig がメモ化の良い候補のように見える関数の例として挙げたものですが、実際にはそうではありません。

メモ化に関する彼の元の論文の図 3 (関数 'Hailstone') を参照してください ("Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems")。

したがって、メモ化のメカニズムが機能するようになったとしても、この場合、実際には速度が向上しないと思います。

于 2010-08-16T15:19:37.923 に答える
0

少し前に、メモ化された状態を追跡するためにクロージャのチェーンを使用する、Scheme 用の小さなメモ化ルーチンを書きました。

(define (memoize op)
  (letrec ((get (lambda (key) (list #f)))
           (set (lambda (key item)
                  (let ((old-get get))
                    (set! get (lambda (new-key)
                                (if (equal? key new-key) (cons #t item)
                                    (old-get new-key))))))))
    (lambda args
      (let ((ans (get args)))
        (if (car ans) (cdr ans)
            (let ((new-ans (apply op args)))
              (set args new-ans)
              new-ans))))))

これは次のように使用する必要があります。

(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

これは、お気に入りのレキシカル スコープの Lisp フレーバーに簡単に移植できると確信しています。

于 2008-11-21T05:13:53.993 に答える
0

私はおそらく次のようなことをします：

(let ((memo (make-hash-table :test #'equal)))
  (defun collatz-steps (n)
    (or (gethash n memo)
    (setf (gethash n memo)
          (cond ((= n 1) 0)
            ((oddp n) (1+ (collatz-steps (+ 1 n n n))))
            (t (1+ (collatz-steps (/ n 2)))))))))

素敵で機能的ではありませんが、それほど面倒ではなく、機能します. 欠点は、テストするのに便利なメモ化されていないバージョンが得られず、キャッシュをクリアすることが「非常に困難」に近いことです。

于 2010-03-06T17:33:29.570 に答える