(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», в котором большие значения рассчитываются из меньших значений, а меньшие значения вычисляются снова и снова. Простое решение состоит в том, чтобы просто хранить значение всякий раз, когда оно вычисляется, и проверить, было ли уже рассчитано значение. Это должно быть просто, как вы можете применить эту технику к своему собственному коду.