performance - (Lisp) 我可以让它更有效率吗？

Question

计算更改样式问题，我用 lisp 编写了这个递归函数，我想知道是否有人有任何技巧可以提高效率？如果数字太大，它就会开始崩溃，大约需要 3 分钟才能计算出 10 英镑的不同组合!即使给我指明正确的方向也很好，谢谢!

(defun dollars (amount &optional (coins '(5 10 20 50 100 200 500 1000 2000 5000 10000)))
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= (length coins) 0) (> amount 30000)) 0)          
        ((zerop (mod amount 5))
         (+ (dollars (- amount (first coins)) coins)
            (dollars amount (rest coins))))))

Answer 1

让我们来看一个类似的问题，计算斐波那契数列。

(defun fib (n)
  (if (<= 0 n 1)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

随着 n 变大，计算较小斐波那契数的次数呈指数增长。在计算 F(10) 时，F(5) 总共计算了八次不同的时间。在计算F(15)时，F(5)一共计算了89次!我们可以通过在计算后保存一个值来解决这个问题。然后，当我们需要确定一个我们已经计算出的值时，只要查一下就可以了。下面的代码就是这样做的。

(defparameter *calculated* (make-hash-table))

(defun fib (n)
  (or (gethash n *calculated*)
      (setf (gethash n *calculated*)
            (if (<= 0 n 1)
                n
                (+ (fib (- n 1))
                   (fib (- n 2)))))))

当给定一个数字进行计算时，如果代码已经计算过它，则查找它的值，否则代码将计算出该值并存储它。现在当我们计算 F(15) 时，F(5) 只计算一次，因为每隔一次它的值只是在哈希表中查找。这大大加快了速度，因为每个斐波那契数(从 F(0) 到 F(15))只计算一次。

这是一种称为“dynamic programming”的技术，其中较大的值是从较小的值计算出来的，较小的值是一遍又一遍地计算出来的。简单的解决方案是在计算时只存储一个值，并检查是否已经计算了一个值。如何将此技术应用于您自己的代码应该很简单。