performance - 为什么这种简化会使我的函数变慢？

Question

以下函数通过尾递归和平方计算斐波那契数列:

(defun fib1 (n &optional (a 1) (b 0) (p 0) (q 1))
  (cond ((zerop n) b)
    ((evenp n) 
     (fib1 (/ n 2) 
          a 
          b 
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q))))
    (t 
     (fib1 (1- n)
          (+ (* b q) (* a (+ p q)))
          (+ (* b p) (* a q))
          p
          q))))

基本上，它将每个奇数输入减少为偶数，并将每个偶数输入减少一半。例如，

F(21)
    = F(21 1 0 0 1) 
    = F(20 1 1 0 1) 
    = F(10 1 1 1 1) 
    = F(5 1 1 2 3)
    = F(4 8 5 2 3) 
    = F(2 8 5 13 21) 
    = F(1 8 5 610 987) 
    = F(0 17711 10946 610 987)
    = 10946

当我看到这个时，我认为结合偶数和奇数情况可能会更好(因为奇数减一 = 偶数)，所以我写了

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (zerop n) b
     (fib2 (ash n -1) 
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q)))))

希望这会让它更快，因为上面的等式现在变成了

F(21)
    = F(21 1 0 0 1)
    = F(10 1 1 1 1) 
    = F(5 1 1 2 3)
    = F(2 8 5 13 21) 
    = F(1 8 5 610 987) 
    = F(0 17711 10946 1346269 2178309)
    = 10946

然而，当我通过以下代码检查 Fib(1000000) 所需的时间时(忽略程序，我只是不想让我的屏幕充满数字。)

(time (progn (fib1 1000000)()))
(time (progn (fib2 1000000)()))

我只能看到 fib2 可能比 fib1 做更多的 evenp，那为什么它慢那么多？

编辑:我认为 n.m.做对了，我编辑了第二组公式。例如。在上面的 F(21) 示例中，fib2 实际上计算了 p 和 q 中的 F(31) 和 F(32)，这从未被使用过。所以在 F(1000000) 中，fib2 计算 F(1048575) 和 F(1048576)。

Lazy evaluation rocks，这是一个很好的观点。我想在 Common Lisp 中只有像“and”和“or”这样的宏被延迟评估？

以下修改的 fib2(为 n>0 定义)实际上运行得更快:

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (= n 1) (+ (* b p) (* a q))
     (fib2 (ash n -1) 
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q)))))

Answer 1

插入中间结果的打印。在计算结束时注意 p 和 q。

您会注意到 fib2 在最后一步为 p 和 q 计算了更大的值。这两个值解释了所有性能差异。

具有讽刺意味的是，这些昂贵的值并未被使用。这就是 Haskell 不会遇到此性能问题的原因:实际上并未计算未使用的值。