Scheme- Memoization "force" 和 "delay" 速度比较

Question

(define fibo   ; fibonacci
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          ((= n 2) 1)
          (else (+ (fibo (- n 1)) (fibo(- n 2))
     )))))

(time (fibo 20))

(define (fiboN n)   ; fibonacci
    (delay (cond ((= n 0) 0)
          ((= n 1) 1)
          ((= n 2) 1)
          (else (+ (force (fiboN (- n 1))) (force (fiboN(- n 2))))))))

(time force( force (fiboN 20)))

鉴于上面的两个斐波那契函数，我预计第二个会运行更快，因为方案对强制延迟对象应用了记忆。

然而第二个 fiboN 运行更慢。为什么会这样？我对 Scheme 中的自动记忆有误吗？

Answer 1

您将记忆化与延迟 (a.k.a.lazy) 评估混为一谈 - 看看这个 explanation 以了解两者之间的区别概念。

您对 fiboN 的第二次实施当然会延迟，但它不会记忆任何东西 - 当然，一旦我们 force 一个值就不必再次强制执行，但它不会'改变一个事实，即这是一个递归函数，它会为我们已经获得的值一遍又一遍地调用，并且 delaying/forcing 每个值的额外成本将使其比第一个实现慢。

这里有一个确实使用记忆的可能实现，诀窍是将已经计算的值保存在我们可以有效访问它们的地方 - 散列 table 在这个示例：

(define fiboN
  (let ((memo (make-hash '((0 . 0) (1 . 1)))))
    (lambda (n)
      (unless (hash-has-key? memo n)
        (hash-set! memo n (+ (fiboN (- n 1)) (fiboN (- n 2)))))
      (hash-ref memo n))))

而且结果表明这要快得多：

(time (fiboN 100))

cpu time: 0 real time: 1 gc time: 0
354224848179261915075

Scheme- Memoization "force" 和 "delay" 速度比较

Scheme- Memoization with "force" and "delay" speed comparison

scheme

lazy-evaluation

fibonacci

memoization