3

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

(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) 所需的时间时，结果却要慢得多（在例如 Clozure CL、CLisp 和 Lispworks 中花费大约 50% 的时间）（忽略 progn，我只是不希望我的屏幕充满数字。）

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

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

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

懒惰的评价摇滚，这是一个很好的观点。我猜在 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)))))
4

2 回答 2

3

插入中间结果的打印。注意p计算q接近尾声。

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

具有讽刺意味的是，这些昂贵的价值没有被使用。这就是为什么 Haskell 不会遇到这个性能问题：未实际计算未使用的值。

于 2012-08-06T15:37:08.650 回答
0

如果不出意外， fib2 有更多条件（在计算参数时）。这很可能会改变代码流的完成方式。条件意味着跳转，意味着管道停顿。

(disassemble #'fib1)查看生成的代码可能会很有启发性（尝试(disassemble #'fib2)看看是否有任何明显的差异）。更改优化设置也可能是值得的，除非您要求对速度进行大量优化，否则通常会有一些优化没有完成。

于 2012-08-06T10:19:15.527 回答