放！关于 memoize 和 define something to memoize，区别？

Question

我在下面制作了这个记忆功能，我正在试验它。

(define (make-table)
  (list '*table*))

(define (lookup key table)
  (let ((record (assoc key (cdr table)))) 
    (and record (cdr record))))

(define (insert! key value table)
  (let ((record (assoc key (cdr table))))
    (if record
        (set-cdr! record value)
        (set-cdr! table
                 (cons (cons key value) (cdr table))))))

(define (fib n)
  (display "computing fib of ")
  (display n) (newline)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
             (fib (- n 2))))))

(define (memoize message f)

  (define (dispatch message)
    (cond 
      ((eq? message 'memoize) memo)
      ((eq? message 'unmemoize) fibe)))

  (define memo 
    (let ((table (make-table)))
      (lambda (x)
        (let ((previously-computed-result (lookup x table)))
          (or previously-computed-result
              (let ((result (f x)))
                (insert! x result table)
                result)
               )))))

  (dispatch message) )

你可以忽略'unmemoize) fibee部分。

我很难理解的是为什么下面这两行代码的作用不同。

(set! fib(memoize 'memoize  fib))

和

(define mm (memoize 'memoize fib))

fib 这是这个函数：

(define (fib n)
(cond ((= n 0) 0)
      ((= n 1) 1)
      (else (+ (fib (- n 1))
               (fib (- n 2))))))

调用下面这些函数给我不同的结果，我不明白为什么

(fib 3)
(fib 3)
(mm 3)
(mm 3)

结果：

调用 (fib 3) 两次：

调用 (mm 3 ) 两次和 (mm 2) 一次

如您所见，(mm 3) 和 (fib 3) 的行为不同，当我运行 (mm 2) 我不明白为什么我们不把数字 1 作为 return 但新计算

Answer 1

问题是，当您执行 (define mm (memoize 'memoize fib)) 时，mm 会调用 fib 的记忆版本，但是 fib本身被定义为递归调用自身，fib 是 not memoized。也就是说，当调用 mm 时，只有对 fib 的初始调用会被记忆化。

这可以通过使用 trace 功能来查看。发布的代码似乎不是 Racket，而是 #lang r5rs，它允许使用 (#%require racket/trace) 访问 Racket 的 trace 过程。我们可以使用它来查看对 fib 的调用展开。请注意，我在 fib 的 OP 定义中注释掉了 display 调用以消除输出中的一些噪音：

bad-memo.rkt> (#%require racket/trace)
bad-memo.rkt> (trace fib)
bad-memo.rkt> (fib 5)
>(fib 5)
> (fib 4)
> >(fib 3)
> > (fib 2)
> > >(fib 1)
< < <1
> > >(fib 0)
< < <0
< < 1
> > (fib 1)
< < 1
< <2
> >(fib 2)
> > (fib 1)
< < 1
> > (fib 0)
< < 0
< <1
< 3
> (fib 3)
> >(fib 2)
> > (fib 1)
< < 1
> > (fib 0)
< < 0
< <1
> >(fib 1)
< <1
< 2
<5
5

这会产生 完全相同的轨迹 ，我将在此处省略以保存 space:

bad-memo.rkt> (define mm (memoize 'memoize fib))
bad-memo.rkt> (mm 5)
;; --> same output as `(fib 5)` above

当调用 mm 时，fib 的记忆版本被调用一次，然后 unmemoized fib 被调用多次。

(set! fib (memoize 'memoize fib)) 情况有所不同。这次 memoize returns 是 fib 的记忆版本，并且符号 fib 发生了变异，因此它指的是这个记忆版本！现在每当调用 fib 时，都会调用记忆版本，这包括递归调用：

bad-memo.rkt> (set! fib (memoize 'memoize fib))
bad-memo.rkt> (fib 5)
>(fib 5)
> (fib 4)
> >(fib 3)
> > (fib 2)
> > >(fib 1)
< < <1
> > >(fib 0)
< < <0
< < 1
< <2
< 3
<5
5

在这里，您可以通过比较 fib 设置为记忆版本前后的轨迹来看出差异。

为了进一步阅读，前一段时间。

放！关于 memoize 和 define something to memoize，区别？

Set! on memoize and define something to memoize, difference?

scheme

racket

r5rs