(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))仅计算一次.

这是一种称为" 动态编程 " 的技术,其中较大的值是从较小的值计算的,较小的值是一遍又一遍地计算的.简单的解决方案是只在计算值时存储一个值,并检查是否已经计算了一个值.如何将此技术应用于您自己的代码应该是直截了当的.